前言
冒泡排序有一个很显著的缺点:元素两两比较,交换次数太多,所需时间太长。
在现实生活中,冒泡排序也不常用。例如,在体育课/军训,体育老师/教官正指挥学生们按照身高从矮到高的顺序排队,那么你认为老师/教官会使用冒泡排序整理队伍吗?很显然,不会。
需要知道:频繁的数组元素交换意味着更多的内存读写操作,会严重影响代码运行效率。
选择排序(Selection sort
),是一种简单直观的排序方法。因其每一轮排序都找到了当前的最小值,这个最小值就是被选中的数字,将其交换至本轮首位。这就是“选择排序”名称的由来。
排序思路
- 第一次在待排序序列中找到最小元素,存放到序列的起始位置;
- 再从剩余的未排序元素中继续寻找最小元素,然后放到已排序的序列的末尾;
- 以此类推,直到所有元素均排序完毕。
也就是说,双重循环遍历数组,每经过一轮比较,找到最小元素的下标,将其交换至首位。
代码实现
public static void Sort1(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
// minIndex = array[minIndex] < array[j] ? minIndex : j;
if (array[minIndex] > array[j]) {
// 记录最小值的下标
minIndex = j;
}
}
// 将最小元素交换至首位
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
异同
与冒泡排序相比,相同点:都是两层循环,时间复杂度都为 O(n^2)
;都只使用有限个变量,空间复杂度 O(1)
。
不同点:冒泡排序在比较过程中就不断交换;而选择排序增加了一个变量保存最小值 / 最大值的下标,遍历完成后才交换,减少了交换次数。
所以,选择排序比冒泡排序更具有优势;但这不意味着可以完全取代它。因为还有一个重要的不同点:冒泡排序法是稳定的,而选择排序法是不稳定的。
排序算法的稳定性
什么是排序算法的稳定性?
假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[a] = r[b],且 r[a] 在 r[b] 之前,而在排序后的序列中,r[a] 仍在 r[b] 之前,则称这种排序算法是稳定的;否则称为不稳定的。也就是说,当数列包含多个值相等的元素时,经过选择排序后,原有的顺序可能会被打乱。
稳定性的意义
其实它只在一种情况下有意义:当要排序的内容是一个对象的多个属性,且其原本的顺序存在意义时,如果我们需要在二次排序后保持原有排序的意义,就需要使用到稳定性的算法。
例如,如果要对一组商品排序,商品存在两个属性:价格和销量。当我们按照价格从高到低排序后,要再按照销量对其排序,这时,如果要保证销量相同的商品仍保持价格从高到低的顺序,就必须使用稳定性算法。
当然,算法的稳定性与具体的实现有关。在修改比较的条件后,稳定性排序算法可能会变成不稳定的。如冒泡算法中,如果将“左边的数大于右边的数,则交换”这个条件修改为“左边的数大于或等于右边的数,则交换”,冒泡算法就变得不稳定了。
同样地,不稳定排序算法也可以经过修改,达到稳定的效果。最简单的做法:新开一个数组,将每轮找出的最小值依次添加到新数组中,选择排序算法就变成稳定的了。
二元选择排序
选择排序算法也是可以优化的,既然每轮遍历时找出了最小值,何不把最大值也顺便找出来呢?这就是二元选择排序的思想。
使用二元选择排序,每轮选择时记录最小值和最大值,可以把数组需要遍历的范围缩小一倍。
public static void Sort2(int[] array) {
int minIndex, maxIndex;
// i 只需要遍历一半
for (int i = 0; i < array.length / 2; i++) {
minIndex = i;
maxIndex = i;
for (int j = i + 1; j < array.length - i; j++) {
if (array[minIndex] > array[j]) {
// 记录最小值的下标
minIndex = j;
}
if (array[maxIndex] < array[j]) {
// 记录最大值的下标
maxIndex = j;
}
}
// 如果 minIndex 和 maxIndex 都相等,那么他们必定都等于 i,且后面的所有数字都与 array[i] 相等,此时已经排序完成
if (minIndex == maxIndex) {
break;
}
// 将最小元素交换至首位
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
// 如果最大值的下标刚好是 i,由于 array[i] 和 array[minIndex] 已经交换了,所以这里要更新 maxIndex 的值。
if (maxIndex == i) {
maxIndex = minIndex;
}
// 将最大元素交换至末尾
int lastIndex = array.length - 1 - i;
temp = array[lastIndex];
array[lastIndex] = array[maxIndex];
array[maxIndex] = temp;
}
}
使用 minIndex 记录最小值的下标,maxIndex 记录最大值的下标。每次遍历后,将最小值交换到首位,最大值交换到末尾,就完成了排序。由于每一轮遍历可以排好两个数字,所以最外层的遍历只需遍历一半即可。
二元选择排序中有一句很重要的代码,它位于 交换最小值
和 交换最大值
的代码中间:
if (maxIndex == i) {
maxIndex = minIndex;
}
这个判断代码处理了一种特殊情况:如果最大值的下标等于 i,也就是说 arr[i] 就是最大值,由于 arr[i] 是当前遍历轮次的首位,它已经和 arr[minIndex] 交换了,所以最大值的下标需要跟踪到 arr[i] 最新的下标 minIndex。
二元选择排序的效率
在二元选择排序算法中,数组需要遍历的范围缩小了一倍。但无法将选择排序的效率提升一倍——虽然二元选择排序最外层的遍历范围缩小了,但 for 循环内做的事情翻了一倍。
实测会发现二元选择排序的速度确实比选择排序的速度快一点点,它的速度提升主要是因为两点:
- 在选择排序的外层 for 循环中,i 需要加到
arr.length - 1
,二元选择排序中 i 只需要加到arr.length / 2
; - 在选择排序的内层 for 循环中,j 需要加到
arr.length
,二元选择排序中 j 只需要加到arr.length - i
。
在二元选择排序中,我们可以做一个剪枝优化,当 minIndex == maxIndex
时,说明后续所有的元素都相等,就好比班上最高的学生和最矮的学生一样高,说明整个班上的人身高都相同了。此时已经排序完成,可以提前跳出循环。通过这个剪枝优化,对于相同元素较多的数组,二元选择排序的效率将远远超过选择排序。
和选择排序一样,二元选择排序也是不稳定的。
动画演示
演示动画来自于visualgo
复杂度分析
选择排序使用两层循环,时间复杂度为 O(n^2); 只使用有限个变量,并没有用到额外的数据结构,空间复杂度为 O(1)。二元选择排序虽然比选择排序要快,但治标不治本,二元选择排序中做的优化无法改变其时间复杂度,二元选择排序的时间复杂度仍然是 O(n^2);空间复杂度为 O(1)。
参考
LeetCode
程序员小灰
菜鸟教程