选择排序·SelectionSort

选择排序（Selection sort）是一种简单直观的排序算法。

它的工作原理是：

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置；

然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。

以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

算法原理

重复遍历未排序部分,将最小元素移至已排序末尾

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

实例演示

// 第一次选择
array:  [6] [3] [9] [4] [7] [1] [5] [2] [8] [0];tmp:  0
             | array[1]<array[tmp];tmp=1;
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0];      1
                 | array[2]>array[tmp];
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0];      1
                     | array[3]>array[tmp];
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0];      1
                         | array[4]>array[tmp];
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0];      1
                             | array[5]<array[tmp];tmp=5;
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0];      5
                                 | array[6]>array[tmp];
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0];      5
                                     | array[7]>array[tmp];
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0];      5
                                         | array[8]>array[tmp];
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0];      1
                                             | array[9]<array[tmp];tmp=9;
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0];      9
        // 遍历结束，交换位置
        [0] [3] [9] [4] [7] [1] [5] [2] [8] [6]
// 第一次选择结束

// 第二次选择
array:  [0] [3] [9] [4] [7] [1] [5] [2] [8] [6];tmp:  1
                 | array[2]>array[tmp];
        [0] [3] [9] [4] [7] [1] [5] [2] [8] [6];      1
                     | array[3]>array[tmp];
        [0] [3] [9] [4] [7] [1] [5] [2] [8] [6];      1
                         | array[4]>array[tmp];
        [0] [3] [9] [4] [7] [1] [5] [2] [8] [6];      1
                             | array[5]<array[tmp];tmp=5;
        [0] [3] [9] [4] [7] [1] [5] [2] [8] [6];      5
                                 | array[6]>array[tmp];
        [0] [3] [9] [4] [7] [1] [5] [2] [8] [6];      5
                                     | array[7]>array[tmp];
        [0] [3] [9] [4] [7] [1] [5] [2] [8] [6];      5
                                         | array[8]>array[tmp];
        [0] [3] [9] [4] [7] [1] [5] [2] [8] [6];      5
                                             | array[9]>array[tmp];
        [0] [3] [9] [4] [7] [1] [5] [2] [8] [6];      5
        // 遍历结束，交换位置
        [0] [1] [9] [4] [7] [3] [5] [2] [8] [6]
// 第二次选择排序

…

// 第N-1次冒泡
array:  [0] [1] [2] [3] [4] [5] [6] [7] [8] [9];tmp   8
                                             | array[9]>array[tmp]
        [0] [1] [2] [3] [4] [5] [6] [7] [8] [9];      8
        // 遍历结束，交换位置
        [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
// 第N-1次冒泡结束

算法分析

时间复杂度

空间复杂度

稳定性

不稳定排序

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第 n-1 个元素，第 n 个元素不用选择了，因为只剩下它一个最大 的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列 5 8 5 2 9，我们知道第一 遍选择第 1 个元素 5 会和 2 交换，那么原序列中两个 5 的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

代码实现

参考