选择排序

十大经典排序算法

选择排序（Selection sort）的原理是每次在未排序的序列中找到最小的元素，放到已排序的序列后面，然后再从剩余未排序的元素中继续寻找最小元素，继续放到已排序的序列后面。重复上面的步骤，直到所有的元素都选择完为止，如下图所示。

只要按照上面的步骤写就可以了，最开始的时候默认已排序的序列为空，然后逐步从后面选择剩余最小的元素。

public void selectSort(int[] nums) {
    int length = nums.length;
    for (int i = 0; i < length - 1; i++) {
        int minIndex = i;// 剩余序列中最小元素的下标。
        // 查找剩余序列中最小元素的下标。
        for (int j = i + 1; j < length; j++) {
            if (nums[j] < nums[minIndex])
                minIndex = j;
        }
        // 如果有最小元素就交换。
        if (i != minIndex)
            swap(nums, i, minIndex);
    }
}

稳定性分析

选择排序是从剩余部分选择最小的和前面的交换，会破坏相同元素的相对位置，所以他是不稳定的。比如数组 [3,4,3,1] ，第一步从数组中选择最小的元素和数组的第一个元素交换，比如最小元素 1 和第一个 3 进行交换，那么第一个 3 就跑到第二个 3 的后面了，他们的相对顺序改变了。为了区分两个 3 ，这里第二个 3 用 third 表示，我们来看下。

原始数据：【3，4，third，1】
第一步 ：【1，4，third，3】
第二步 ：【1，third，4，3】
第三步 ：【1，third，3，4】

我们看到排序之前和排序之后两个 3 的位置的确发生了变化，所以选择排序是不稳定的。

时间复杂度：O(n^2)
稳定性：不稳定

相关链接