选择排序 | 是熊是猫溜溜

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

主要思想

每次在未排序的数组中，找到最大或者最小的元素，放到已排序数组的末尾，依次进行，直到数组全部有序。

原数据：

1	[9] [8] [9] [7] [1] [3] [5]

第一步，在原始数组中找到最小元素[1]，起始位置的[9]进行交换，结果如下。

1	[1] [8] [9] [7] [9] [3] [5]

第二步，在剩余未排序数组中找到最小元素[3]与[8]进行交换，结果如下。

1	[1] [3] [9] [7] [9] [8] [5]

第三步，在剩余未排序数组中找到最小元素[5]与索引三处的[9]进行交换，结果如下。

1	[1] [3] [5] [7] [9] [8] [9]

第四步，在剩余未排序数组中找到最小元素[7]，其已经处在正确位置。

1	[1] [3] [5] [7] [9] [8] [9]

第五步，在剩余未排序数组中找到最小元素[8]，前面的[9]进行交换，结果如下。

1	[1] [3] [5] [7] [8] [9] [9]

第六步，在剩余未排序数组中找到最小元素[9]，其已经处在正确位置。

1	[1] [3] [5] [7] [8] [9] [9]

排序完毕，数组已经有序。

时间与空间复杂度

从第一步就可以明显看出，两个[9]交换了次序，因此插入排序是不稳定的排序算法。其时间复杂度计算公式如下。可以看到选择排序最好的情况下时间复杂度为2^n，最坏的情况下时间复杂度为2^n，空间复杂度为O(1)，平均时间复杂度为2^n。

$$
(n-1) + (n-2) + … + 1 = \frac{n * (n-1)}{2}
$$

代码实现

less函数与exch函数参见文章排序算法序言。

public static void insertion(Comparable[] c){
    int N = c.length;
    for(int i = 1; i < N; i++){
        for(int j = i; j > 0 && less(c[j], c[j-1]); j--){
            exch(c, j, j-1);
        }
    }
}