选择排序(Selection Sort)
LanyuanXiaoyao's Blog ヽ(✿゚▽゚)ノ

选择排序(Selection Sort)

2017-03-10

概念

选择排序是一种简单直观的排序算法,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕.
顾名思意,就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来, 顺序放入新数组,直到全部拿完.
再简单点,对着一群数组说,你们谁最小出列,站到最后边,然后继续对剩余的无序数组说,你们谁最小出列,站到最后边,再继续刚才的操作,一直到最后一个,继续站到最后边,现在数组有序了.
优点
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

步骤

  1. 遍历整个序列,找到最小的元素,记录这个元素的下标,然后把它和序列中的第一个元素交换.
  2. 然后除了第一个元素外的剩下的元素看作一个序列,然后重复步骤1
  3. 持续步骤1和步骤2直到只剩下最后一个元素的时候,序列就有序了.
  4. 选择排序就好像构建了一个新的序列,每次都在待排序的序列中挑选最小的按顺序放在新序列中.
  5. 这就是选择排序

举例

例1

假定有一个数组[5, 7, 4, 10, 9],我们要把这个数组按从小到大排列

  1. 我们先遍历整个数列找到最小的数,在这个例子中是4
  2. 然后我们把这个找到的最小的数和排第一位置的数交换位置,也就是变成了[4, 7, 5, 10, 9]
  3. 然后我们可以发现,最小的数已经放在了第一位.
  4. 接下里我们该找第二小的数什么数了,所以我们第二轮遍历在剩下的[7, 5, 10, 9]中找到最小的数,然后和第二个位置的数交换.
  5. 重复这个步骤,直到每一个数都被排序
  6. 如果恰好在剩下的数列中最小的数就是在第一位,那么就不用执行交换的操作.

例2

先说看每步的状态变化,后边介绍细节,现有无序数组[6 2 4 1 5 9]

  1. 第一趟找到最小数1,放到最前边(与首位数字交换)
    交换前:| 6 | 2 | 4 | 1 | 5 | 9 |
    交换后:| 1 | 2 | 4 | 6 | 5 | 9 |
  2. 第二趟找到余下数字[2 4 6 5 9]里的最小数2,与当前数组的首位数字进行交换,实际没有交换,本来就在首位
    交换前:| 1 | 2 | 4 | 6 | 5 | 9 |
    交换后:| 1 | 2 | 4 | 6 | 5 | 9 |
  3. 第三趟继续找到剩余[4 6 5 9]数字里的最小数4,实际没有交换,4待首位置无须交换
  4. 第四趟从剩余的[6 5 9]里找到最小数5,与首位数字6交换位置
    交换前:| 1 | 2 | 4 | 6 | 5 | 9 |
    交换后:| 1 | 2 | 4 | 5 | 6 | 9 |
  5. 第五趟从剩余的[6 9]里找到最小数6,发现它待在正确的位置,没有交换
    排序完毕输出正确结果[1 2 4 5 6 9]

解析 第一趟找到最小数1的细节
当前数组是| 6 | 2 | 4 | 1 | 5 | 9 |
先把6取出来,让它扮演最小数
当前最小数6与其它数一一进行比较,发现更小数就交换角色
当前最小数62比较,发现更小数,交换角色,此时最小数是2,接下来2与剩余数字比较
当前最小数24比较,不动
当前最小数21比较,发现更小数,交换角色,此时最小数是1,接下来1与剩余数字比较
当前最小数15比较,不动
当前最小数19比较,不动,到达末尾
当前最小数1与当前首位数字进行位置交换,如下所示
交换前:| 6 | 2 | 4 | 1 | 5 | 9 |
交换后:| 1 | 2 | 4 | 6 | 5 | 9 |
完成一趟排序,其余步骤类似

代码实现

代码实现是按照选择排序的原理,将序列分为两部分,前面的是排好序的,后面的是待排序的,每次找到待排序中最小的元素,就交换到前面相应位置上.

protected int[] Sort(int[] num) {
    for (int i = 0; i < num.length - 1; i++) {
        int index = i;
        for (int j = i + 1; j < num.length; j++) {
            if (num[j] < num[index]) {
                index = j;
            }
        }
        if (index != i) {
            int temp = num[i];
            num[i] = num[index];
            num[index] = temp;
        }
    }
    return num;
}

复杂度及稳定性

时间复杂度 $O(n^2)$

选择排序的交换操作介于$0$和$(n-1)$,比较操作介于$0$和${n(n-1)}\over2$之间,赋值操作介于$0$和$3(n-1)$.
选择排序的比较次数和序列的初始状态无关,也就是即使数列是有序的,总的比较次数还是$N=(n-1)+(n-2)+…+1=\frac{n(n-1)}2$.而交换次数是$O(n)$,最好的情况是数列是有序的,交换次数为$0$,最坏的情况是序列是逆序的,交换次数为$n-1$,交换次数比冒泡排序较少,由于交换所需CPU时间比比较所需的CPU时间多,$n$值较小时,选择排序比冒泡排序快.
原地操作几乎是选择排序的唯一优点,当空间复杂度要求较高时,可以考虑选择排序;实际适用的场合非常罕见.

空间复杂度 $O(1)$

因为是一个原地排序,只需要一个辅助变量用于交换即可

稳定性

由于在直接选择排序中存在着不相邻元素之间的互换,因此,直接选择排序是一种不稳定的排序方法。
实际上选择排序的稳定性要看具体代码

优化

选择排序可优化的地方不多,常用的一种优化方案在于,常规选择排序一轮只找一个最小值,那我们可以一轮同时找最大值和最小值,并把它们分别交换到第一位和最后一位,这样我们待排序的剩余序列就会大幅减少.

protected int[] Sort(int[] num) {
  for (int i = 0; i < num.length / 2; i++) {
    int min = i, max = num.length - 1 - i;
    for (int j = i; j < num.length - i; j++) {
      if (num[j] < num[min])
        min = j;
      else if (num[j] > num[max])
        max = j;
      }
      if (min != i) {
        int temp = num[min];
        num[min] = num[i];
        num[i] = temp;
      }
      if (max == i) { // 由于最大值可能处于最小值的位置上,所以需要做一个判断
        max = min;
      }
      if (max != num.length - 1 - i) {
        int temp = num[max];
        num[max] = num[num.length - 1 - i];
        num[num.length - 1 - i] = temp;
      }
    }
    return num;
}

实际测试

可以看到优化后的选择排序在数据量小的时候优势并不明显,只有在数据规模较大的情况下才比原始选择排序要快.

数据规模 原始选择排序 优化方案
1000 0~16 0~16
10000 28 34
100000 2707 1941
1000000 281315 210817

评论