交换排序算法——冒泡排序、快速排序

本文最后更新于：2021年1月8日 晚上

概览：冒泡排序、快速排序算法思想以及C++代码的实现。

交换排序

顾名思义，基于“交换”思想的排序，根据序列中两个关键字的比较结果来对换这两个记录在序列中的位置。

包含冒泡排序和快速排序两种。

冒泡排序

算法思想：从后往前，每次两两比较相邻元素的值，通过交换位置使得值较小的元素排在前面，这样经过一次排序，当前序列中最小的元素排在了最前面。

这称为一趟冒泡，每次冒出待排序序列中最小的那个，直到待排序序列只剩一个为止。

或者从前往后，每次排序使得最大的元素排在最末尾，“沉底🙃”。

注意：若在冒泡排序中的某趟中没有发生交换，那就说明整体已经有序了，这时算法就可以停止运行了。

冒泡排序

图源：拉勾教育
图中为“沉底”的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void swap(int &a, int &b) {
	int tmp = a;
	a = b;
	b = tmp;
}

void BubbleSort(int A[], int n) {
	for (int i = 0; i < n-1; i++) {//n个元素至多会进行n-1趟排序
		bool flag = false;		   //标识这一次排序中是否发生了交换
		for (int j = n-1; j > i; j--) { //从后往前，每次取最小的元素
			if (A[j] < A[j-1]) {
				swap(A[j], A[j-1]);//交换元素
				flag = true;
			}
		}
		if (flag == false)	//若未发生交换
			break;
	}
}

算法分析

  • 空间复杂度：O(1)，需要常量个辅助空间。
  • 时间复杂度：
    • 最好情况下，初始就有序，那就是n个元素进行n-1次比较，没有交换元素，O(n)。
    • 最坏情况下，初始为逆序，
      • 第一趟：对比关键字n-1次，移动3(n-1)次，(swap函数中元素交换三次)
      • 第二趟：对比关键字n-2次，移动3(n-2)次
      • …
      • 第n-1趟：对比关键字1次，移动3次
      • 一共对比$$\frac{n(n-1)}{2}$$ ,一共移动$$\frac{3n(n-1)}{2}$$（等差数列计算）
      • O(n^2).
    • 平均情况下，O(n^2).
  • 冒泡排序是稳定的算法。
  • 算法评价：简单、容易实现，适用于待排序序列比较小或者基本有序的情况。
  • 算法适用：可用于顺序表、链表这样的数据结构。
    • 例如单链表，可以使用“沉底”的方式从表头将最大的元素沉到表尾。
  • 算法特点：每一趟排序都会确定一个元素在序列中的最终位置。

快速排序

算法思想：这是基于分治策略的思想，采用了划分交换排序。选定一个枢轴元素pivot，通过一次划分，将待排序数据分割为两部分，左边都比pivot小，右边都比pivot大。然后对这两部分数据再分别执行上述排序过程，直到任何一个子序列都为空或者只有一个元素为止，这样整个数据就变成了有序序列。

  • 分治：将原问题划分为若干个与原问题相同的子问题；然后递归的求解子问题，当子问题规模足够小的时候就可以直接求解；然后将每个子问题的解组合成原问题的解。

实现方式1.——填坑法

通过移动low和high指针，来交换元素的位置，使得low指针左边的元素都小于pivot，而右边元素都大于pivot。

  1. 初始时刻选择low指向的49作为pivot枢轴元素，则low所指位置为空，high指向最末端的元素。
  2. high指针所指元素大于等于pivot=49，则其向左移动，指向27，由于小于pivot，则要将其与low指针所指位置交换元素。此时high指向空。
  3. 然后移动low指针，low所指元素小于pivot，然后low向右移动，直到找到一个大于pivot的值，将其与high所指位置进行交换。然后low指向了空。
  4. 继续移动high指针，找寻比pivot小的元素，使其到达low即low的左边的位置，即13交换到low所指位置。
  5. low指针来找寻比piovt大的元素，使其移动到high的位置。
  6. high指针向左移动，直到和low指针相遇。这时第一次划分结束，low左边均比pivot要小，high右边均比pivot要大，这两指针所指位置就是pivot应当填充的位置。
步骤 索引0 索引1 索引2 索引3 索引4 索引5 索引6 索引7
1 #|low 38 65 97 76 13 27 49|high
2 27|low 38 65 97 76 13 #|high 49
3 27 38 #|low 97 76 13 65|high 49
4 27 38 13|low 97 76 #|high 65 49
5 27 38 13 #|low 76 97|high 65 49
6 27 38 13 49|low|high 76 97 65 49

针对左半部分，继续进行划分、交换。

  1. 选择0号位置的27作为pivot，low所指元素为空，high指向最末尾的元素。
  2. high指向所指元素小于pivot，与low位置进行交换。
  3. low指针向右移动，寻找比pivot要大的元素，并与high位置的元素进行交换。
  4. high指针向左移动，遇到了low指针，划分结束，所指位置应当填入pivot。
步骤 索引0 索引1 索引2
1 #|low 38 13|high
2 13|low 38 #|high
3 13 #|low 38|high
4 13 27|low|high 38

剩余部分也是同样的方式。

很明显这是一个递归的过程，起始选择表首作为pivot，high指针指向末尾，向左移动寻找比pivot小的元素赋值给A[low]，而low向右移动，寻找比pivot大的元素赋值给A[high]，执行结束的条件是low=high。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Partition(int A[], int low, int high) {
	int pivot = A[low];	//选取枢轴元素
	while (low < high) {
		//寻找比pivot小的元素，比它大的直接忽略
		while (low < high && A[high] >= pivot) high--;
		A[low] = A[high];	//比Pivot小的移动到左侧
        //寻找比pivot大的元素，比它小的直接忽略
		while (low < high && A[low] <= pivot) low++;
		A[high] = A[low];	//比Pivot大的移动到右侧
	}
	A[low] = pivot;	//赋值
	return low;		//返回存放枢轴pivot的位置
}

void QuickSort(int A[], int low, int high) {
	if (low < high) {		//当low<high时才执行
		int pivotpos = Partition(A, low, high);	//划分
		QuickSort(A, low, pivotpos-1);			//左子表
		QuickSort(A, pivotpos+1,high);			//右子表
	}
}

实现方式2 —— 前后指针法

前后指针法比上述填坑法有一些独特的优势，它的指针都是单侧移动，可支持单链表这种只能单向移动指针的数据结构。

  1. 将待排序序列的最左元素记为pivot，创建指针i，j，指针i指向待排序序列A的最左边的元素，指针j指向指针i指向的下一位。
  2. 比较A[j]与pivot，若A[j] >= pivot，指针j后移一位，指针i不动。若A[j] < pivot，交换i+1和j的值，指针i、j同时后移一位。
  3. 当指针j走到数组的末尾时，先执行(2)操作，再交换A[i]与pivot的值。
  4. 通过pivot将原来的序列分割成了两个子序列，然后对两个子序列进行相同的操作。即递归执行。
针对一个序列{6 10 13 5 8 3 2 11}进行前后指针法的划分排序。
步骤 索引0 索引1 索引2 索引3 索引4 索引5 索引6 索引7
1 6 | i 10 | j 13 5 8 3 2 11
2 6 | i 10 13 5 | j 8 3 2 11
3 6 5 | i 13 10 8 | j 3 2 11
4 6 5 | i 13 10 8 3 | j 2 11
5 6 5 3 | i 10 8 13 2 | j 11
6 6 5 3 2 | i 8 13 10 11 | j
7 6 5 3 2 | i 8 13 10 11
8 2 5 3 6 | i 8 13 10 11
  1. 选择6作为pivot，指针i指向6，指针j指向10.
  2. 比较A[j]与pivot，A[j] > pivot，指针j向右移动直到指向5。
  3. 此时A[j] < pivot，交换i+1和j的值，指针i、j同时后移一位。
  4. 比较A[j]与pivot，A[j] > pivot，指针j向右移动直到指向3。
  5. 此时A[j] < pivot，交换i+1和j的值，指针i、j同时后移一位。
  6. 此时A[j] < pivot，交换i+1和j的值，指针i、j同时后移一位。
  7. 此时指针j走到了末尾，A[j] > pivot，指针j后移一位，指针i不动。
  8. 交换A[i]与pivot的值。这样指针i指向的左边元素均小于pivot，右边均大于pivot。
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
void swap(int &a, int &b) {
	int tmp = a;
	a = b;
	b = tmp;
}

//前后指针法
int Part(int A[], int left, int right) {
	int pivot = A[left];
	int pivotpos = left;	//记录pivot和其对应位置
	int i = left;
	int j = left + 1;
	while (j <= right && i<j) {
		if (A[j] < pivot) {
			swap(A[i+1],A[j]);
			i++; j++;
		}
		else {
			j++;
		}
	}
	swap(A[i], A[pivotpos]);//交换位置
	return i;
}

void QuickSort(int A[], int low, int high) {
	if (low < high) {		//当low<high时才执行
		int pivotpos = Part(A, low, high);		//划分
		QuickSort(A, low, pivotpos-1);			//左子表
		QuickSort(A, pivotpos+1,high);			//右子表
	}
}

参考链接：https://www.cnblogs.com/Unicron/p/9465403.html

算法分析

对于序列中的递归调用，实际的处理如下：

这就相当于把n个元素组织成了二叉树，二叉树的层数就是递归调用的层数。

而n个节点的二叉树的最小高度为$\lfloor{log_2{n}}\rfloor + 1$，二叉树的最大高度为n。

所以：时间复杂度和空间复杂度取决于递归层数，空间复杂度=O(递归层数)，时间复杂度=O(n*递归层数)，因为每一层的QuickSort函数处理的元素都不会超过n个。

  • 空间复杂度：最好O(log2_n)，最坏O(n)。

  • 时间复杂度：最好O(n*log2_n)，最坏O(n*n)。

  • 不过平均时间复杂度为：O(nlog2_n)。快速排序是所有内部排序算法之中平均性能最优的算法。

  • 快速排序不稳定。eg: 2 2 1，一次划分之后两个2的先后顺序发生了变化。

  • 算法适用：顺序表或者单链表这样的数据结构。采用前后指针法可实现单链表的快速排序。
  • 算法特点：每次排序中会有元素确定其最终位置。

快速排序的优化

当每次的枢轴把待排序列表分割为长度相近的两个子表时，速度时最快的；而当表本身已经有序或者逆序的时候，速度是最慢的。

因为当每一次选中的枢轴元素将待排序序列分割成了两个很不均匀的部分时，会导致递归的深度加深，最终导致算法效率变低。

一、枢轴元素的选取

尽可能的选择可以将数据序列中分的枢轴元素，例如从序列的头、尾以及中间位置选择三个元素，然后去这三个元素的中间值最为枢轴元素。或者是随机的从当前序列中选取枢轴元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//三数取中法，获取中间值的索引
int GetMidIndex(int A[], int left, int right) {
	int mid = (left + right) / 2;
	if (A[left] <= A[mid]) {
		if (A[mid] <= A[right]) return mid;
		else if (A[mid] <= A[right]) return left;
		else return right;
	}
	else {
		if (A[mid] >= A[right]) return mid;
		else if (A[left] >= A[right]) return right;
		else return left;
	}
}

二、加入插入排序

当排序接近完成的时候，数组会被分的很小，这是可以采用直接插入排序来处理这种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
//改进的快速排序
void QuickSort(int A[], int low, int high) {
	if (low < high) {		//当low<high时才执行
		if (high - low <= 5) {		//当待排序长度小于等于6时，采用直接插入排序
			InsertSort(A,low,high);
		}
		else {
			int pivotpos = Partition(A, low, high);	//划分
			QuickSort(A, low, pivotpos - 1);			//左子表
			QuickSort(A, pivotpos + 1, high);			//右子表
		}
	}
}

函数调用示例

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
using namespace std;

//直接插入排序
void InsertSort(int A[], int begin,int end) {
	int temp;//临时变量，暂存数据
	int i, j;
	for (i = begin+1; i <= end; i++) {		//对A[begin+1]到A[end]上的元素进行插入排序
		if (A[i] < A[i-1]) {		//若待排序元素小于其前面有序序列的最后一个元素
			temp = A[i];
			for (j = i-1; j >= begin && A[j] > temp; j--) {
				A[j+1] = A[j];		//所有大于temp的均向后移动
			}
			A[j+1] = temp;			//对应的插入位置
		}
	}
}

//三数取中法，获取中间值的索引
int GetMidIndex(int A[], int left, int right) {
	int mid = (left + right) / 2;
	if (A[left] <= A[mid]) {
		if (A[mid] <= A[right]) return mid;
		else if (A[mid] <= A[right]) return left;
		else return right;
	}
	else {
		if (A[mid] >= A[right]) return mid;
		else if (A[left] >= A[right]) return right;
		else return left;
	}
}

//交换
void swap(int &a, int &b) {
	int tmp = a;
	a = b;
	b = tmp;
}

//填坑法
int Partition(int A[], int low, int high) {
	int pivotpos = GetMidIndex(A, low, high);
	swap(A[low], A[pivotpos]);	//交换，使得low位置为取得的枢轴值
	int pivot = A[low];
	while (low < high) {
		//寻找比pivot小的元素，比它大的直接忽略
		while (low < high && A[high] >= pivot) high--;
		A[low] = A[high];
		while (low < high && A[low] <= pivot) low++;
		A[high] = A[low];
	}
	A[low] = pivot;	//赋值
	return low;		//返回存放枢轴pivot的位置
}

//改进的快速排序
void QuickSort(int A[], int low, int high) {
	if (low < high) {		//当low<high时才执行
		if (high - low <= 5) {		//当待排序长度小于等于6时，采用直接插入排序
			InsertSort(A,low,high);
		}
		else {
			int pivotpos = Partition(A, low, high);	//划分
			QuickSort(A, low, pivotpos - 1);			//左子表
			QuickSort(A, pivotpos + 1, high);			//右子表
		}
	}
}

int main()
{
	int nums = 0;
	cout << "请输入待排序的数量个数:";
	cin >> nums;
	int *A = (int *)malloc(nums*sizeof(int));
	for (int i = 0; i < nums; i++) {
		cin >> A[i];
	}

	QuickSort(A, 0, nums-1);
	for (int i = 0; i < nums; i++) {
		cout << A[i] << " ";
	}
	free(A);
	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
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

int main()
{
	//rand()会返回一个范围在0到RAND_MAX（32767）之间的伪随机数（整数）。

	cout << "请输入随机数生成的起始范围：";
	int begin = 0;
	cin >> begin;
	if (begin < 0 || begin >32767) begin = 0;

	cout << "请输入随机数生成的终止范围：";
	int end = 32767;
	cin >> end;
	if (end > 32767) end = 32767;

	cout << "请输入要产生的随机数的数量：";
	int num;
	cin >> num;

	srand(time(0));//设置随机数种子，若随机种子相同，则每次产生的随机数也相同
	int times = 0;
	int randnum = 0;
	while (times < num) {
		randnum = rand() % (end - begin + 1) + begin;
		cout << randnum << " ";
		times++;
	}
}