O (n²) 的三个排序算法

今天复习下最简单的三个排序算法,一个是选择排序,一个是插入排序,一个是冒泡排序,三者时间复杂度都是 O (n²),通过分析来发现三者的优劣,以及对最好的情况和最坏的情况进行分析。 另外,这三中排序算法都是基于比较的排序算法。基于比较的排序算法的执行过程,会涉及两种操作,一种是元素比较大小,另一种是元素交换或移动。所以,如果我们在分析排序算法的执行效率的时候,应该把比较次数和交换(或移动)次数也考虑进去。

一、选择排序 SelectionSort

选择排序是一种简单直观的排序算法,工作原理为:在未排序的序列中找出最小 (大) 元素与第一个位置的元素交换位置,原理如下图所示:

选择排序的静态图:

mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int tmp;
// 寻找 [i,n] 之间的最小值
int minIndex = i;
for (int j = i+1; j < arr.length; j++) {
if(arr [j] < arr [minIndex]){
minIndex = j;
}
}
tmp = arr [i];
arr [i] = arr [minIndex];
arr [minIndex] = tmp;
}
}

稳定性

选择排序是一种不稳定的排序算法。 从图中可以看出来,选择排序每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性。

最好和最坏情况

选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O (n²)

二、插入排序 InsertionSort

首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

静态图展示

mark

mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void execSort(int[] arr) {
int tmp;
for (int i = 1; i < arr.length; i++) {
// 寻找元素 arr [i] 合适的插入位置
for (int j = i; j > 0; j--) {
if(arr [j] < arr [j-1]){
tmp = arr [j];
arr [j] = arr [j-1];
arr [j-1] = tmp;
}else {
// 到这里说明前面的所有元素已经比当前值小了,没有继续比较的必要了
break;
}
}
}
}

换个比较简洁的写法:

1
2
3
4
5
6
7
8
9
10
11
12
// 更简洁的写法:替换上面的 break
public void execSort(int[] arr) {
int tmp;
for (int i = 1; i < arr.length; i++) {
// 寻找元素 arr [i] 合适的插入位置
for (int j = i; j > 0 && arr [j] < arr [j-1]; j--) {
tmp = arr [j];
arr [j] = arr [j-1];
arr [j-1] = tmp;
}
}
}

插入排序的改进

1
2
3
4
5
6
7
8
9
10
public static void insertionSortOptimize(int[] arr){
for (int i = 0; i < arr.length; i++) {
int e = arr [i];
int j; // 用来保存元素 e 应该插入的位置
for (j = i; j > 0 && arr [j-1] > e; j--) {
arr [j] = arr [j-1];
}
arr [j] = e;
}
}

mark

插入排序和选择排序的对比

其实我们很容易发现选择排序的最致命的缺点就是两层 for 循环需要完全走完才能完成排序,而插入排序则不需要。所以选择排序在任何情况下都是比较慢的。插入排序则不同,最坏的情况下(其实就是逆序了)才是 O (n²),如果是已经有序,或者大部分有序,还是非常快的,比如在我自己的电脑上排一亿个有序的数,才 0.035s,这种速度比 n*Log (n) 的排序算法性能还高,至于选择排序的话我等了 1 分钟还没排出来,直接 stop 了。

所以 O (n²) 级别的排序算法并非一无是处! 下面我们看看冒泡排序吧!

稳定性

在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法。

最好和最坏情况

上面已经说过了,如果要排序的数据已经是有序的,我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置,每次只需要比较一个数据就能确定插入的位置。所以这种情况下,最好是时间复杂度为 O (n)

如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,所以最坏情况时间复杂度为 O (n²)。

三、冒泡排序 BubbleSort

冒泡排序也属于一种典型的交换排序,交换排序顾名思义就是通过元素的两两比较,判断是否符合要求,如过不符合就交换位置来达到排序的目的。冒泡排序名字的由来就是因为在交换过程中,类似水冒泡,小(大)的元素经过不断的交换由水底慢慢的浮到水的顶端。

如果用静态图来展示的话就是这个样子:

mark

1
2
3
4
5
6
7
8
9
10
11
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if(arr [j] > arr [j+1]){
int tmp = arr [j];
arr [j] = arr [j+1];
arr [j+1] = tmp;
}
}
}
}

优化版本定义一个标志位用来表示当前第 i 趟是否有交换,如果有,则要进行 i+1 趟,如果没有则说明当前数组已经完成排序,不需要剩下的比较:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void bubbleSortOptimize(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// 用来表示当前第 i 趟是否有交换,
// 如果有则要进行 i+1 趟,如果没有则说明当前数组已经完成排序
boolean flag = true;
for (int j = 0; j < arr.length - i - 1; j++) {
if(arr [j] > arr [j+1]){
int tmp = arr [j];
arr [j] = arr [j+1];
arr [j+1] = tmp;
flag = false;
}
}
if(flag) return;
}
}

其实冒泡排序还有更优化的做法,那就是记录最后一次交换的位置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void bubbleSortOptimizePlus(int[] arr) {
int pos; // 用来记录最后一次交换的位置
int k = arr.length - 1;
for (int i = 0; i < arr.length; i++) {
pos = 0;
// 用来表示当前第 i 趟是否有交换,
// 如果有则要进行 i+1 趟,如果没有则说明当前数组已经完成排序
boolean flag = true;
for (int j = 0; j < k; j++) {
if(arr [j] > arr [j+1]){
int tmp = arr [j];
arr [j] = arr [j+1];
arr [j+1] = tmp;
flag = false;
pos = j;
}
}
if(flag) return;
k = pos;
}
}

排序随机数组的时候,优化效果一般,但是排序几乎有序的数组和本来就有序的数组还是有优化效果的:

mark

第二种优化之后才 0.049 秒,不优化是 22 秒。

稳定性

冒泡排序是稳定排序,在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以 冒泡排序是稳定的排序算法

最好和最坏情况

最好情况下,要排序的数据已经是有序的了,我们只需要进行一次冒泡操作,就可以结束了,所以最好情况时间复杂度是 O (n)。而最坏的情况是,要排序的数据刚好是倒序排列的,我们需要进行 n 次冒泡操作,所以最坏情况时间复杂度为 O (n²)。

四、三种排序总结

mark

一看图就明白了什么排序算法最实用了吧,那就是插入排序。 这三种时间复杂度为 O (n²) 的排序算法中,冒泡排序、选择排序,可能就纯粹停留在理论的层面了,学习的目的也只是为了开拓思维,实际开发中应用并不多,但是插入排序还是挺有用的。