排序--选择排序

版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/e45b7c94ebab

概念

简单选择排序是选择类的排序，算法原理：第i次排序（1≤ i ≤n-1），从待排序的n-i+1个记录中， 进行n-i次关键字比较，从n-i+1个记录中选出最小的，并和第i-1个记录进行交换。

演示

比如我们待排序的数组是 {9, 1, 5, 8, 3, 7, 4, 6, 2}
第1趟排序，1最小，与第0个位置9进行交换： 1 9 5 8 3 7 4 6 2
第2趟排序，2最小，与第1个位置9进行交换： 1 2 5 8 3 7 4 6 9
第3趟排序，3最小，与第2个位置5进行交换： 1 2 3 8 5 7 4 6 9
第4趟排序，4最小，与第3个位置8进行交换： 1 2 3 4 5 7 8 6 9
第5趟排序，5最小，第4个位置是5无须交换： 1 2 3 4 5 7 8 6 9
第6趟排序，6最小，与第5个位置7进行交换： 1 2 3 4 5 6 8 7 9
第7趟排序，7最小，与第6个位置8进行交换： 1 2 3 4 5 6 7 8 9
第8趟排序，8最小，第7个位置是8无须交换： 1 2 3 4 5 6 7 8 9

其实就是每一趟排序将当前未排序序列中的最小的记录与未排序序列的最前端的位置进行交换。

Java实现

// 定义接口
interface Sorter {
    /**
     * 将数组按升序排序
     */
    int[] sort(int[] arr);

    /**
     * 交换数组arr中的第i个位置和第j个位置的关键字
     */
    default void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
//选择排序
class SelectionSorter implements Sorter {

    @Override
    public int[] sort(int[] arr) {
        selectSort(arr);
        return arr;
    }

    private void selectSort(int[] arr) {
        int i, j, min;
        int len = arr.length;
        for (i = 0; i < len - 1; i++) {
            min = i; // min记录最小值的下标
            for (j = i + 1; j < len; j++) { // 循环i之后的数据
                if (arr[j] < arr[min]) // 发现有小于当前最小值的关键字
                    min = j; // 将该下标赋值给min
            }
            if (i != min) // 如果i和min不等，在i之后的数据中找到了最小值，则需要arr[i]于arr[min]进行交换
                swap(arr, i, min);
        }
    }
}

复杂度

时间复杂度：
对于比较次数而言，无论最好最差情况，其比较次数都是一样的：第i趟排序需要进行n-i次比较，此时比较次数=(n-1)+(n-2)+...+1 = n*(n-1)/2；
对于交换次数而言，其最好情况为顺序表，交换次数为0次；最差情况为逆序表，交换次数为n-1次，那么平均情况则为(n-1)/2次交换；
由于时间复杂度取决于比较次数和交换次数总和，故而交换排序的时间复杂度为O(n^2)。
因为相较于冒泡排序，选择排序的交换次数要少，所以选择排序的性能要优于冒泡排序。

空间复杂度：
最好情况=最坏情况=平均情况=O(1)