选择排序Java详细推演和实现-数据结构和算法-09-排序

选择排序

简单选择排序法(Simple Selection Sort)就是通过n-i次关键字间的比较，从 n-i+1个记录中选出关键字最小的记录，并和第i (l〈i 简单选择排序的逻辑很好理解，关键点在于，全部比较后找出最小值然后交换

选择排序推演

自己不想画推演了，盗用一个图

选择排序实现

package com.my.data.structure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 选择排序
 */
public class SelectionSort {
    public static List<Integer> allList = new ArrayList(
            Arrays.asList(9, 1, 5, 8, 3, 7, 4, 6, 2));

    public static void swap(List<Integer> useList, int a, int b) {
        int temp = useList.get(a);
        useList.set(a, useList.get(b));
        useList.set(b, temp);
    }

    public static void selectSort() {
        List<Integer> list = new ArrayList<>();
        list.addAll(allList);
        int min = 0;
        for (int i = 0; i < list.size(); i++) {
            min = i;
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(min)   > list.get(j))
                    min = j;
            }
            if (min != i) swap(list, i, min);
        }
        System.out.println(list.toString());
    }

    public static void main(String[] args) {
        selectSort();
    }

}

时间复杂度

从简单选择排序的过程来看，它最大的特点就是交换移动数据次数相当少，这样 也就节约了相应的时间。分析它的时间复杂度发现，无论最好最差的情况，其比较次 数都是一样的多，第i趟排序需要进行n-i次关键字的比较,此时需要比较 n-1+n-2……+1=n(n-1)/2。而对于交换次数而言，当最好的时候，交换为0次，最差的时候，也就初始降序时，交换次数为n-1次，基于最终的排序时间是比较与交换的次数总和，因此，总的时间复杂度依然为0(n^2)。
应该说，尽管与冒泡排序同为0(n^2)，但简单选择排序的性能上还是要略优于冒泡 排序。