java 实现排序算法之「选择排序」

Author Avatar
ikook 8月 11, 2017
  • 在其它设备中阅读本文章

java 实现排序算法系列

继冒泡排序算法之后,选择排序终于和大家见面了。为什么冒泡排序之后要说选择排序呢,是因为它俩是最相似的两种排序算法,血缘关系最为接近。

还是那句话,本人能力拙劣,有不当之处还请不吝赐教,可关注我公号后台留言,见底部二维码。

选择排序

选择排序(Selection sort)是一种简单直观的排序算法,它也是一种交换排序算法,和冒泡排序有一定的相似度。可以把它看做是冒泡排序算法的一种改进算法。

算法思路

假设要给有 n 个元素的数组 arr[] 排序。注意,在数组中第一个元素的下标为 0

n = 1:

无需排序

n > 1:
  • 将第一个元素和第二个元素进行比较,如果 arr[0] 大于 arr[1],那么 arr[0] 一定不是最小元素。这里我们暂时不交换元素,而是设置临时变量 a,用来存储较小变量 arr[1] 的下标。然后将目前较小元素 arr[a] 继续和第三个元素比较,如果 arr[a] 大于 arr[2],则修改 a 的值为 arr[2] 的下标,再接着往下比较;如果不大于 arr[2],则将 arr[a] 和第四个元素比较,如前者大,则修改 a 的值为 arr[3] 的下标。以此类推,直到与最后一个元素比较,则 a 的值肯定是最小值的下标。

  • 如果 a 的值不为 0(即不是元素 arr[0] 的下标),则交换下标为 0 和 a 的元素,即将 arr[a] 和 arr[0] 进行交换。

  • 至此,第一趟排序完成,将最小值找出来了,然后进行第二趟排序。重复上述过程,从第二个元素(即 arr[1])开始比较。第一个元素已经是最小元素了,不参与比较。

  • 重复步骤直到剩下最后一个元素,即 arr[n-1],可以肯定这个值为最大值。

  • 排序完成,不够直观?见下面示例动画。

注: 红色表示当前最小值,黄色表示已排序序列,蓝色表示当前位置。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对 n 个元素进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

需要注意的是,上述过程只是每次找最小值的办法。实际上也可以每次找最大值,思路是一样的。

选择排序的示意图(图片来自维基百科):


代码实现

设要给数组 arr[] 排序,它有 n 个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void selectionSort(int[] arr) {
int min, temp, len = arr.length;
for (int i = 0; i < len - 1; i++) {
min = i;//未排序序列中最小数据数组下标
for (int j = i + 1; j < len; j++) { //在未排序元素中继续寻找最小元素,并保存其下标
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
temp = arr[min]; //将最小元素放到已排序序列的末尾
arr[min] = arr[i];
arr[i] = temp;
}
}
}

算法复杂度

选择排序需要进行 n-1 轮比较。很显然,比较次数 O(n^2),比较次数与关键字的初始状态无关,总的比较次数 N = (n-1) + (n-2) + … + 1 = n x (n-1) / 2。

交换次数 O(n),最好情况是,已经有序,交换 0 次;最坏情况是,逆序,交换 n-1 次。交换次数比冒泡排序较少,由于交换所需 CPU 时间比比较所需的 CPU 时间多,n 值较小时,选择排序比冒泡排序快。

选择排序的赋值次数:最坏情形下需要交换 n-1 次,对于上面的代码,需要赋值 3(n-1) 次。而最佳情况下,则需要 0 次。如果假定平均分布,大约需要 3n/2。

冒泡排序可以在最佳情况下有 O(n) 复杂度,那么选择排序行不行呢? 很遗憾,不行。选择排序每次只找最小值,但它并不能知道其他值是否有序排列。因此,选择排序在最优、最坏、平均情况下的时间复杂度均为 O(n^2),空间复杂度(额外空间)为 O(1).

算法稳定性

对于选择排序的稳定性是存在一定争议的。但在本例中,最小值和另一个值相同的时候我们并不需要交换它们,选择排序是稳定排序。其实排序算法中,有些稳定算法可以变换成不稳定算法,而不稳定排序算法又有很多办法可以变成稳定的,这在《算法》第四版中有所提及。所以,没有严格意义上的稳定与不稳定排序。

算法适用场景

选择排序实现也比较简单,并且由于在各种情况下复杂度波动小,因此一般是优于冒泡排序的。在所有的完全交换排序中,选择排序也是比较不错的一种算法。但是,由于固有的 O(n^2) 复杂度,选择排序在数据量较大的时候显得力不从心。因此,它适用于简单数据排序。


ikook
2017.08.11


欢迎关注我的公众号:ikook