算法渣-排序-选择

没有一身好内功，招式再多都是空;算法绝对是防身必备，面试时更是不可或缺；跟着算法渣一起从零学算法

定义

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

算法

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

1. 初始状态：无序区为R[1..n]，有序区为空
2. 第1趟排序
   在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
   ……
3. 第i趟排序
   第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

演示

实现

static void selectSort(int []array) {
    for (int i=0;i<array.length-1;i++) {
        int min  = i;
        for (int j = i+1;j<array.length;j++){
            if(array[min] > array[j]) {
                min = j;
            }
        }
        if( min != i) {
            int tmp = array[i];
            array[i] = array[min];
            array[min] = tmp;
        }

    }
}

复杂度

比较次数：T = （n-1)）+ （n -2）+（n - 3）…. + 1; T = [n*(n-1) ] / 2；

交换次数：

最好的情况全部元素已经有序，则交换次数为0；

最差的情况，全部元素逆序，就要交换 n-1 次；

空间复杂度

最优的情况下（已经有顺序）复杂度为：O(0)

最差的情况下（全部元素都要重新排序）复杂度为：O(n );

平均的时间复杂度：O(1)

Best	Average	Worst	Memory	Stable
n²	n²	n²	1	No

VS 插入排序

插入排序特别的相似

复杂度一样，但是插入排序和读入（初始）的数据有关，最优情况只有O(n)；而选择排序不论如何，永远都是O(n^2)

插入排序是边读边排，每当读入一个新的数时，目前的数组一定是排好序的。而选择排序不同，它必须是读完所有的数据之后才能开始排序的。

那么选择排序的缺点就是，万一数据量很大，比方说一百万个，光读就慢了，还要排序，那就更慢了。如果这两个耗时的步骤可以并行一起做的话，显然插入排序肯定就会快一些。