写在前面：
从这一讲开始，我们整理一下常见的十大排序算法，可以按照它们的时间复杂度进行大致的分类。今天先来讲讲平均时间复杂度为 O(n^2^) 的四个排序算法。
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2^) | O(n) | O(n^2^) | O(1) | 稳定 |
| 选择排序 | O(n^2^) | O(n^2^) | O(n^2^) | O(1) | 不稳定 |
| 插入排序 | O(n^2^) | O(n) | O(n^2^) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) | O(nlog^2^n) | O(nlog^2^n) | O(1) | 不稳定 |
冒泡排序
冒泡排序正如其名，这个算法像是泡泡一样往上升，具体步骤如下：
- 将第一个元素与第二元素作比较，如果前者大于后者则交换。按照这个规则从第一个元素一直遍历到最后一对元素比较完为止。
- 从第二个元素开始按上面规则往后遍历，然后作比较进行交换，每次都至少能将一个值放到后面排好序。
- 不断的重复上述过程，直到没有元素交换为止。
为了方便理解，我们还是来看图：
第一步：比较第一个元素与第二个元素，不存在逆序，后移一位。
第二步：比较第二个元素和第三个元素，不存在逆序，后移一位。
第三步：比较第三个元素和第四个元素，不存在逆序，后移一位。
第四步：比较第四个元素和第五个元素，存在逆序，交换两者，后移一位。
第五步：比较第五个元素和第六个元素，存在逆序，交换两者，后移一位。
第六步：比较第六个元素和第七个元素，存在逆序，交换两者，后移一位。
第七步：比较第七个元素和第八个元素，存在逆序，交换两者，后移一位。
第八步：比较第八个元素和第九个元素，存在逆序，交换两者，后移一位。
第九步：比较第九个元素和第十个元素，存在逆序，交换两者，后移一位。
至此，第一趟排序完成， 我们得到了最大值 9 ，也就是说该值已经固定下来了，接下里只用对 9 之前的元素进行排序即可。
第二趟排序：
第三趟排序：
第四趟排序：
第五趟排序：
第六趟排序：
第七趟排序：
至此，序列已经有序，不用再进行交换操作，输出序列即可。
这里代码我提供了三种思路，都是用冒泡排序实现升序操作：
- 第一种：就是上面提到的一个简单的冒泡排序，只加了一个是否还有交换的判断条件作为优化。
- 第二种：我不仅有是否交换判断条件，还设置了一个变量去保存最后交换的位置下标，这样下一趟排序最多遍历到最后交换的位置即可，因为后面没有交换的地方就已经是有序的了。
- 第三种：递归法，其实就和第一种方法一样，只是换成了递归的操作。
#include <bits/stdc++.h>
using namespace std;
//简单版冒泡排序
void bubble(int a[], int size) {
int flag = 1;
for (int i = 0; i < size - 1; i++) {
for (int j = 1; j <= dis && flag; j++) {
flag = 0;
if (a[j] < a[j - 1]) {
swap(a[j], a[j - 1]);
flag = 1;
}
}
}
}
//冒泡排序（堆优化版）
void bubbleSort(int a[], int size) {
int k, dis = size - 1; //记录最后一次交换的位置
int pos; //判断序列是否已经有序
for (int i = 0; i < size - 1; i++) {
pos = 0;
for (int j = 1; j <= dis; j++) {
//将大的数字往后移
if (a[j] < a[j - 1]) {
swap(a[j], a[j - 1]);
k = j - 1; //下次循坏直接从最后一次交换的位置开始
pos = 1; //序列仍然在进行排序
}
}
dis = k;
//如果已经成有序序列，直接退出
if (pos == 0) {
return;
}
}
}
//递归
void Bubblesort(int *arr, int n, bool change) {
if (!change || n == 1) {
//输出
return;
} else {
change = false;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
change = true;
}
}
Bubblesort(arr, n - 1, change);
}
}
int main() {
int a[10] = { 21, 343, 122, 84, 5, 117, 4, 35, 90, 666 };
int size = 10;
bubbleSort(a, size);
for (int i = 0; i < size; i++) {
cout << a[i] << " ";
}
return 0;
}选择排序
选择排序就是我每一趟排序都找到一个值，放在我当前的所在位置，具体步骤如下：
- 首先从下标为 0 开始，遍历一遍数组并找到最小的值，把它放到下标为 0 的位置。
- 然后从下标为 1 开始，遍历后续数组并找到后面元素中最小的值，把它放到下标为 1 的位置。
- 以此类推，直到最后一趟排序结束。
直接上图：
第一趟排序：找到最小值 2 ，放在下标为 0 的位置。
第二趟排序：找到最小值 3 ，放到下标为 1 的位置。
第三趟排序：找到最小值 5 ，已经在下标为 3 的位置了。
第四趟排序：
第五趟排序：
第六趟排序：
第七趟排序：
#include <bits/stdc++.h>
using namespace std;
//选择排序
void insert_sort(int arr[], int size) {
int minIndex;
for (int i = 0; i < size - 1; i++) {
minIndex = i;
for (int j = i + 1; j < size; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
swap(arr[i], arr[minIndex]);
}
}
int main() {
int arr[7] = { 3, 44, 5, 27, 2, 50, 48};
int size = 7;
insert_sort(arr, size);
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
return 0;
}插入排序
插入排序的每趟排序都会将当前的元素与其前面的元素进行排序，步骤如下：
- 从第一个元素开始，因为第一个元素之前没有元素，所以直接认为它是有序的了。
- 找到下一个元素并拿出来，对前面已经排好序的元素进行从后往前的遍历，如果遍历的元素要大于拿出来的元素，则往后移一位。直到遍历的元素小于取出元素或者已经遍历到最开头，遍历结束并将拿出来的元素插入该位置之后。
- 重复上述步骤，直至最后一趟排序结束。
直接上图，我们下面演示将会把数组下标为 0 的位置作为哨兵位，用来放取出的元素：
第一趟排序：第一个元素已经有序，故不用排序。
第二趟排序：第二个元素放到下标为 0 的哨兵位，从后往前遍历前面排好序的元素，发现比前面元素要大，直接放回下标为 1 的位置。
第三趟排序：取出第三个元素放到哨兵位，与前面元素进行比较，插入到对应位置。
第四趟排序：
第五趟排序：
第六趟排序：
第七趟排序：
至此，排序结束，该序列已经有序，直接输出即可。
#include <bits/stdc++.h>
using namespace std;
//这里的数组是从1开始算，下标0是哨兵位，len是元素总数量
void insert_sort(int arr[], int len) {
int i, j;
for (i = 2; i <= len; i++) {
if (arr[i - 1] > arr[i]) {
//将取出的元素放到哨兵位
arr[0] = arr[i], arr[i] = arr[i - 1];
//同样不用担心数组越界问题，因为最多只会遍历到哨兵位就退出来了
for (j = i - 2; arr[0] < arr[j]; j--)
arr[j + 1] = arr[j];
arr[j + 1] = arr[0];
}
}
}
int main() {
int arr[8] = {0, 2, 3, 1, 8, 5, 11, 4}; //从下标为1开始存储元素
int size = 7;
insert_sort(arr, size);
for (int i = 1; i <= size; i++)
cout << arr[i] << " ";
return 0;
}希尔排序
希尔排序是插入排序的一种更高效的改进版本，算法步骤如下：
- 选择一个间隔距离 k ，对元素间隔距离为 k 的序列进行排序，如果存在逆序则进行交换操作。
- 缩小 k ，再次进行排序操作。
- 重复上述操作，直至 k 小于 1 时停止排序。
直接上图：
第一趟排序：
我们将间隔 k 设置为数组总长度的一半即 10 / 2 = 5 ，然后对以 k 为间隔的元素进行第一组排序。发现第 1 个元素与第 6 个元素不存在逆序，且 5 + 5 = 10 > 9 超过数组最大下标，则进行第二组排序，以此类推。
至此第一趟希尔排序结束，运气比较好，对应的组内元素都是正序，没有进行交换操作。那么我们将间隔 k 除以 2 即 k / 2 = 2 ，对以间隔为 2 的元素进行第一组排序：
这时候就出现逆序了，所以交换两个元素位置，继续往后走。
同样发现 4 比 5 要小，故直接交换。继续比较发现 4 已经比 2 要大了，故继续往后走。
8 + 2 = 10 > 9 即已经超过最大数组下标，故进行第二组排序。
发现 3 比 11 要小，故交换元素继续往前比较。
发现 3 比 8 也要小，故继续交换元素往前比较。结果 3 不大于其之前元素了，故继续往后走。
发现 6 比 11 要小，故交换元素继续往前比较。
发现 6 比 8 也小，继续交换元素往前比较。结果 6 已经比其之前元素 3 要大，故继续往后。
发现已经无法往后走了，故第二趟希尔排序结束。将 k 继续除以 2 即 k / 2 = 1 ，进行第三趟排序：
第三趟希尔排序结束，将 k 除以 2 即 k / 2 = 0 小于 1 ，故排序结束，输出序列即可。
#include <bits/stdc++.h>
using namespace std;
//希尔排序
void shellSort(int arr[], int size) {
//不断地改变间隔大小，再进行排序
for (int gap = size / 2; gap > 0; gap /= 2) {
//从每组的第一个元素开始
for (int i = 0; i < gap; i++) {
//对增量为gap的元素进行直接插入排序
for (int j = i + gap; j < size; j += gap) {
int temp = arr[j];
int k = j - gap;
while (k >= 0 && arr[k] > temp) {
arr[k + gap] = arr[k]; //将arr[i]前且比temp值大的元素向后移动
k -= gap;
}
arr[k + gap] = temp;
}
}
}
}
int main() {
int arr[10] = { 2, 3, 1, 8, 5, 11, 4, 3, 9, 6 };
int size = 10;
shellSort(arr, size);
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
return 0;
}如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~
