冒泡排序
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复
n 次，就完成了 n 个数据的排序工作。
例子
假设要对一组数据排序（数组）：4，5，6，3，2，1
冒泡过程（由小到大排序，每次冒泡实质就是拿出最大的元素放到数组末尾）：
第一次冒泡：
1、拿 4 和 5 对比，4 < 5 所以不做元素互换操作，此时数组为
4，5，6，3，2，1
2、拿 5 和 6 对比，5 < 6 所以不做元素互换操作，此时数组为
4，5，6，3，2，1
3、拿 6 和 3 对比，6 > 3 所以将 6 和 3 位置互换，此时数组为
4，5，3，6，2，1
4、拿 6 和 2 对比，6 > 2 所以将 6 和 2 位置互换，此时数组为
4，5，3，2，6，1
5、拿 6 和 1 对比，6 > 1 所以将 6 和 1 位置互换，此时数组为
4，5，3，2，1，6
经过这次冒泡，元素 6 的位置就是最终排序后的位置了。
第二次冒泡的过程中，因为数组最后一个元素已经是最大的元素，因此我们只需要对开头的
5 个元素排序即可。
第二次冒泡，此时数组为 4，5，3，2，1，6 ：
1、拿 4 和 5 对比，4 < 5 所以不做元素互换操作，此时数组为
4，5，3，2，1，6
2、拿 5 和 3 对比，5 > 3 所以交换这两个元素的位置，此时数组为
4，3，5，2，1，6
3、拿 5 和 2 对比，5 > 2 所以交换这两个元素的位置，此时数组为
4，3，2，5，1，6
4、拿 5 和 1 对比，5 > 1 所以交换这两个元素的位置，此时数组为
4，3，2，1，5，6
到此，第二次冒泡结束（因为数组末尾的元素在第一次冒泡的时候已经确定的了），经过这次冒泡，倒数第二个元素也确定了下来。
我们一共有 6 个元素，所以还需要进行 4
次冒泡操作才能得到最后的排序结果。
冒泡排序优化
因为我们在冒泡过程中，实际上是对比相邻的两个元素，如果
$arr[$i] > $arr[$i + 1]，那么交换这两个元素的位置。
也就是说，如果一次冒泡过程中，完全没有发生数据交换，说明数组里面的数组都是从小到大有序的。这个时候我们就可以直接退出冒泡过程了。
PHP 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| $array = [1, 5, 3, 7, 9, 4, 20, 100, 55, 67, 66];
function bubble_sort($arr)
{
$n = count($arr);
if ($n == 1) return $arr;
$flag = true;
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
$flag = false;
}
}
if (!$flag) break;
}
return $arr;
}
var_export(bubble_sort($array));
|
问题
- 冒泡排序是否是原地排序算法？
冒泡的过程中，只有相邻数据位置互换，不需要开辟新的空间来进行操作，所以是原地排序算法。
- 冒泡排序是否是稳定的算法？
冒泡过程中，我们只在 $arr[$j] > $arr[$j + 1]
的时候，才互换位置，相等的两个元素，位置不会变动，所以是稳定的算法。
- 冒泡排序的时间复杂度是多少?
最好的情况下，数组已经有序，只需要进行一次冒泡即可，时间复杂度是
O(n)。
最坏的情况下，完全逆序，冒泡过程总遍历次数为
(n - 1) + (n - 2) + ... + 1，也就是
n*(n-1)/2，所以时间复杂度是 O(n²)。
插入排序
先看一个简单的问题。一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，我们只要遍历数组，找到数据应该插入的位置将其插入即可。我们可以通过这种方法保持集合中的数据一直有序。
插入排序的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
在插入排序中，我们会将数据列表划分为两个部分，一部分是有序区间，另一部分是无序区间。插入排序的过程就是，遍历无序区间里面的每一个元素，在有序区间里面遍历找到一个合适的位置进行插入，直到无序区间的数据全部插入到有序区间里面，这个时候数据列表就完全有序了。
初始状态下，一般会将第一个元素 $arr[0]
视作有序区间，然后 $arr[1...n-1] 为无序区间，我们会遍历
$arr[1...n-1]
中的每一个元素，拿来插入到有序区间中，直到遍历完无序区间的全部数据。
例子
假设要对一组数据排序（数组）：4，5，6，3，2，1，按顺序排序。
开始的时候，我们的有序区间是 $arr[0...0]，无序区间是
$arr[1...n-1]。
第一次遍历，我们拿到无序区间的第一个元素
5($arr[1])，将其与 4 对比，5 >
4，所以位置不变，因为有序区间只有一个元素，所以此次遍历结束。但是此时有序区间已经是
$arr[0...1]，无序区间是 $arr[2...n-1]。
第二次遍历，我们拿到无序区间的第一个元素
6($arr[2])，我们将其与有序区间的最后一个元素，也就是
5 对比，发现 6 比 5
大，是有序区间最大的元素，所以此次遍历结束。但是此时有序区间已经是
$arr[0...2]，无序区间是 $arr[3...n-1]。
我们这里是从有序区间的最后一个元素开始对比，但从有序区间第一个元素开始对比也是可以的。只是操作上稍有不同，如果从第一个元素开始对比，在我们找到合适的位置的时候，需要先将有序区间剩余的元素往后挪动即可。但是需要注意这种情况下对结果稳定性的影响，也就是说，这种情况下，我们比较的时候需要使用
>= 或 <=
这种包含相等情况的也进行位置互换操作。这样才能保证排序结果的稳定性。
如此遍历，直到无序区间的元素被全部遍历完毕。
PHP 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| function insertion_sort($arr)
{
$n = count($arr);
if ($n <= 1) return $arr;
// 0~$i-1 为有序区间
// $i~$n-1 为无序区间
for ($i = 1; $i < $n; $i++) {
$value = $arr[$i];
// 查找插入的位置
for ($j = $i - 1; $j >= 0; $j--) {
if ($arr[$j] > $value) {
$arr[$j + 1] = $arr[$j]; // 数据移动
} else {
break;
}
}
// 到这里的时候说明: 1. $arr[$j] <= $value(找到了插入的位置) 或 2. $j = -1 (循环终止，$value 是目前有序区间最小的数)
$arr[$j + 1] = $value; // 插入数据
}
return $arr;
}
var_export(insertion_sort($array));
|
问题
- 插入排序是原地排序算法吗？
在插入排序的过程中，我们并不需要额外的存储空间，所以空间复杂度为
O(1)，也就是说，插入排序是一个原地排序算法。
- 插入排序是稳定的排序算法吗?
在插入排序中，对于值相同的元素，我们并不交换位置，可以保持原有的前后顺序不变，所以是稳定的排序算法。
- 插入排序的时间复杂度是多少？
最好的情况下，如果数据已经是有序的，我们并不需要移动任何数据，每次只需要比较一次就能确定插入的位置。这种情况下，时间复杂度是
O(n)。注意这里是从尾到头遍历已经有序的数据。
最坏的情况下，数据是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，需要移动数据的次数为
O(n²)，所以最坏情况时间复杂度为 O(n²)。
我们在数组中插入一个数据的平均时间复杂度是
O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行
n 次插入操作，所以平均时间复杂度为 O(n²)。
选择排序
选择排序和插入排序有点类似，在排序的过程中，数据也被划分成有序区间和无序区间。但是选择排序是每次从未排序的区间里面选择最小的元素，将其放到已排序区间的末尾。
PHP 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| function selection_sort($arr)
{
$n = count($arr);
if ($n <= 1) return $arr;
for ($i = 0; $i < $n - 1; $i++) {
$min = $arr[$i];
$minIndex = $i;
for ($j = $i; $j < $n; $j++) {
if ($arr[$j] < $min) {
$min = $arr[$j];
$minIndex = $j;
}
}
$arr[$minIndex] = $arr[$i];
$arr[$i] = $min;
}
return $arr;
}
var_export(selection_sort($array));
|
问题
- 选择排序是原地排序算法吗？
在选择排序的过程中，只需要两个变量来存储最小元素的值和最小元素的下标，不需要其他额外的空间，所以是原地排序算法。
- 选择排序是稳定的算法吗？
由于每次选择排序会将最小元素跟未排序区间第一个元素互换，这个互换过程会改变原有数据的顺序，所以是不稳定的算法。
- 选择排序的时间复杂度是多少?
选择排序所需时间为 n + (n - 1) + ... + 1，即
n(n + 1)/2，所以时间复杂度是 O(n²)。
冒泡和插入时间复杂度一样，为什么插入排序更受欢迎？
因为每一次循环过程中，冒泡排序需要 3
个赋值操作，而插入排序只需要一个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| // 冒泡排序中数据的交换操作：
if (a[j] > a[j + 1]) { // 交换
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
flag = true;
}
// 插入排序中数据的移动操作
if (a[j] > value) {
a[j + 1] = a[j]; // 数据移动
} else {
break;
}
|
所以，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是
O(n²)，但是如果我们希望把性能优化做到机智，那肯定首选插入排序。插入排序的算法思路也有很大的优化空间
=> 希尔排序。
小结
冒泡排序、插入排序、选择排序对比
| 冒泡排序 |
是 |
是 |
O(n) O(n²) O(n²) |
| 插入排序 |
是 |
是 |
O(n) O(n²) O(n²) |
| 选择排序 |
是 |
否 |
O(n²) O(n²) O(n²) |
这三种时间复杂度为 O(n²)
的排序算法中，冒泡排序、选择排序，可能就纯粹停留在理论的层面了，学习的目的也只是为了开拓思维，实际开发中应用并不多，但是插入排序还是挺有用的。有些编程语言的排序函数实现原理会用到插入排序算法。
这三种排序算法，实现代码都非常简单，对于小规模数据的排序，用起来非常高效。但是在大规模数据排序的时候，这个时间复杂度还是稍微有点高，所以更倾向于使用时间复杂度为
O(nlogn) 的排序算法。