数据结构与算法专栏 —— C++实现

写在前面：
从这一讲开始，我们整理一下常见的十大排序算法，可以按照它们的时间复杂度进行大致的分类。今天先来讲讲平均时间复杂度为 O(n²) 的四个排序算法。

冒泡排序

冒泡排序正如其名，这个算法像是泡泡一样往上升，具体步骤如下：

1. 将第一个元素与第二元素作比较，如果前者大于后者则交换。按照这个规则从第一个元素一直遍历到最后一对元素比较完为止。
2. 从第二个元素开始按上面规则往后遍历，然后作比较进行交换，每次都至少能将一个值放到后面排好序。
3. 不断的重复上述过程，直到没有元素交换为止。

为了方便理解，我们还是来看图：

第一步：比较第一个元素与第二个元素，不存在逆序，后移一位。

第二步：比较第二个元素和第三个元素，不存在逆序，后移一位。

第三步：比较第三个元素和第四个元素，不存在逆序，后移一位。

第四步：比较第四个元素和第五个元素，存在逆序，交换两者，后移一位。

第五步：比较第五个元素和第六个元素，存在逆序，交换两者，后移一位。

第六步：比较第六个元素和第七个元素，存在逆序，交换两者，后移一位。

第七步：比较第七个元素和第八个元素，存在逆序，交换两者，后移一位。

第八步：比较第八个元素和第九个元素，存在逆序，交换两者，后移一位。

第九步：比较第九个元素和第十个元素，存在逆序，交换两者，后移一位。

至此，第一趟排序完成， 我们得到了最大值 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;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

选择排序

选择排序就是我每一趟排序都找到一个值，放在我当前的所在位置，具体步骤如下：

1. 首先从下标为 0 开始，遍历一遍数组并找到最小的值，把它放到下标为 0 的位置。
2. 然后从下标为 1 开始，遍历后续数组并找到后面元素中最小的值，把它放到下标为 1 的位置。
3. 以此类推，直到最后一趟排序结束。

直接上图：

第一趟排序：找到最小值 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

插入排序

插入排序的每趟排序都会将当前的元素与其前面的元素进行排序，步骤如下：

1. 从第一个元素开始，因为第一个元素之前没有元素，所以直接认为它是有序的了。
2. 找到下一个元素并拿出来，对前面已经排好序的元素进行从后往前的遍历，如果遍历的元素要大于拿出来的元素，则往后移一位。直到遍历的元素小于取出元素或者已经遍历到最开头，遍历结束并将拿出来的元素插入该位置之后。
3. 重复上述步骤，直至最后一趟排序结束。

直接上图，我们下面演示将会把数组下标为 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;
}
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

希尔排序

希尔排序是插入排序的一种更高效的改进版本，算法步骤如下：

1. 选择一个间隔距离 k ，对元素间隔距离为 k 的序列进行排序，如果存在逆序则进行交换操作。
2. 缩小 k ，再次进行排序操作。
3. 重复上述操作，直至 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;
}
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
30
31
32

如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~

【下一讲】C++实现排序 - 02 归并排序、快速排序和堆排序