在之前的文章中,我们说了两个原地排序算法:插入排序和冒泡排序。分析两个算法的原理,也用代码实现了两个算法。最后,我们也从两个算法入手,引出了评价算法性能的两个重要指标:是否是原地排序算法和算法稳定性。今天我们再来说一种原地排序算法:** 选择排序**。
为了,我们能够更好地与之前文章中的两个算法作比较,我们还是还是将上一篇文章关于排序算法复杂度的图片祭出。
选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。
话不多说,我们先来从数组:4,6,5,2,1,3,来看选择排序的原理分析图。
可以看到,上图的原理分析和我们在文章开始描述的一样,分为已排序和未排序区间。且每次都是从未排序区间中选出最小的数值放到已排序区间的末尾。
public static void chooseSort(int[] arr) {
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length - 1; i++) {
int min = arr[i];
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
// 找出未排序区间中最小的值
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
}
// 放到已排序区间的末尾
if (min != arr[i]) {
arr[minIndex] = arr[i];
arr[i] = min;
}
System.out.println(Arrays.toString(arr));
}
}
我们来看看输出:
即使在最好的情况下,选择排序也会有一个嵌套循环,也就是选择排序的最好时间复杂度为O(n2),幸运的是,选择排序的最坏时间复杂度也是O(n2)。
和插入排序与冒泡排序算法文章类似,在文章末尾,我们还是照常来分析分析选择排序算法。
先来回顾一下,什么原地排序算法。原地排序算法是指:数组排序前后,不占用额外内存空间。
答案显而易见,选择排序排序前后只有位置的交换,并没有占用额外存储空间,所以选择排序算法是原地排序算法。
同样的,回顾一下,什么是稳定算法。稳定算法是指:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。
选择排序是一种不稳定的排序算法。我们可以从上面的图片中看出,选择排序每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性。
比如说:5,8,5,2,9 这样一组数据,使用选择排序算法来排序的话,第一次找到最小元素 2,与第一个 5 交换位置,那第一个 5 和中间的 5 顺序就变了,所以就不稳定了。正是因此,相对于冒泡排序和插入排序,选择排序就稍微逊色了。
简单总结一下,本文讲了一个不稳定的原地排序算法:选择排序。从示意图一步一步的分析选择排序,引出选择排序算法算法复杂度。
选择排序、插入排序和冒泡排除这三种排序算法,实现代码都非常简单,对于小规模数据的排序,用起来非常高效。但是在大规模数据排序的时候,这个时间复杂度还是稍微有点高,所以我们更倾向于时间复杂度为 O(nlogn) 的排序算法。(归并排序和快速排序)