经典排序算法

插入排序

空间复杂度O(1)，平均时间复杂度O(n^2)。最好情况：时间复杂度——O(1)，最坏情况：时间复杂度——O(n^2)

插入排序适用于链表。

插入排序是建立在已有序的序列基础上，刚开始序列只有一个元素，因此，需要比较n-1个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。在往前找的过程中，比要插入元素大的都往后挪。若遇见相等的，那么插入元素把想插入的元素放在相等元素的后面。

插入排序的流程可形象地看成：手里有一副打乱的扑克牌，自左到右开始第二张扑克牌依次往前插入。

因此，插入排序算法是稳定的。

#include 
#include 

using namespace std;

void insertionSort(vector<int>& a, int n) {
	int i, j, temp;
	for (i = 1; i < n; i++) {      // 将各元素插入已排好序的序列中
		if (a[i] < a[i - 1]) {     // 若a[i]关键字小于前驱
			temp = a[i];           // 用temp暂存a[i]
			for (j = i - 1; j >= 0 && a[j] > temp; j--) { // 检查所有前面已排好序的元素
				a[j + 1] = a[j];   // 所有大于temp元素的都向后挪
			}
			a[j + 1] = temp;       // 复制到插入位置
		}
	}
}
int main()
{
	vector<int> num = { 9, 1, 5, 6, 2, 3 };

	insertionSort(num, num.size());

	for (int i = 0; i < num.size(); i++) {
		cout << num[i] << " ";
	}
	cout << endl;

	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

输出结果

1 2 3 5 6 9
1

将a[0]作为哨兵，使用带哨兵的直接插入排序代码如下

#include 
#include 

using namespace std;

// 直接插入排序，带哨兵
void insertionSort(vector<int>& a, int n) {
	int i, j;
	for (i = 2; i <= n; i++) {      // 将各元素插入已排好序的序列中
		if (a[i] < a[i - 1]) {     // 若a[i]关键字小于前驱
			a[0] = a[i];           // 用temp暂存a[i]
			for (j = i - 1; a[j] > a[0]; j--) { // 检查所有前面已排好序的元素
				a[j + 1] = a[j];   // 所有大于temp元素的都向后挪
			}
			a[j + 1] = a[0];       // 复制到插入位置
		}
	}
}

int main()
{
	vector<int> num = { 0, 9, 1, 5, 6, 2, 3 };

	insertionSort(num, num.size()-1);

	for (int i = 1; i < num.size(); i++) {
		cout << num[i] << " ";
	}
	cout << endl;

	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

输出结果

1 2 3 5 6 9
1

希尔排序

空间复杂度O(1)，时间复杂度O(n^1.3)。算法不稳定。

希尔排序是对插入排序的改进，将序列分成几组。对各个组进行插入的时候并不是先对一个组进行排序完再对另一个组进行排序，而是轮流对每个组进行插入排序。

希尔排序不是排序稳定的算法，虽然插入排序是稳定的，但是希尔排序在插入的时候是跳跃性插入的，有可能破坏稳定性。

#include 
#include 

using namespace std;

//希尔排序
void ShellSort(vector<int>& a, int n) {
	int d, i, j;
	// a[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
	for (d = n / 2; d >= 1; d = d / 2) { // 步长变化
		for (i = d + 1; i <= n; i++) {
			if (a[i] < a[i - d]) {       // 需要将a[i]插入有序增量子表
				a[0] = a[i];             // 暂存在a[0]
				for (j = i - d; j > 0 && a[0] < a[j]; j -= d) {
					a[j + d] = a[j];     // 记录后移，查找插入的位置
				}
				a[j + d] = a[0];         // 插入
			}//if
		}
	}
}

int main()
{
	vector<int> num = { 0, 49, 38, 65, 97, 76, 13, 27, 49 };

	ShellSort(num, num.size()-1);

	for (int i = 1; i < num.size(); i++) {
		cout << num[i] << " ";
	}
	cout << endl;

	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

输出结果

13 27 38 49 49 65 76 97
1

冒泡排序

空间复杂度O(1)，平均时间复杂度O(n^2)。算法稳定。冒泡排序适用于链表。

以下代码，从后往前将小的元素往前调(即排好序后为升序排序)，从最后一个元素开始依次比较相邻元素，若是逆序，则对这两个元素进行交换，一轮结束后则一个元素归位，总共n-1轮。

当相邻两个元素相等时，不会发生交换，因此冒泡排序算法是稳定排序算法。

#include 
#include 

using namespace std;

//冒泡排序
void BubbleSort(vector<int>& a, int n) {
	for (int i = 0; i < n - 1; i++) {
		bool flag = false;                // 表示本趟冒泡是否发生交换的标志
		for (int j = n - 1; j > i; j--) { // 一趟冒泡过程
			if (a[j - 1] > a[j]) {        // 若为逆序
				swap(a[j - 1], a[j]);     // 交换
				flag = true;
			 }
		}
		if (flag == false) return;
	}
}

int main()
{
	vector<int> num = { 49, 38, 65, 97, 76, 13, 27, 49 };

	BubbleSort(num, num.size());

	for (int i = 0; i < num.size(); i++) {
		cout << num[i] << " ";
	}
	cout << endl;

	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

输出结果

13 27 38 49 49 65 76 97
1

快速排序

算法思想： 在待排序表$L[\mathrm{1...}n]$中任取一个元素pivot作为枢轴，（或基准，通常取首元素），通过一趟排序表划分为独立的两部分$L[\mathrm{1...}k-1]$和$L[k+\mathrm{1...}n]$，使得$L[\mathrm{1...}k-1]$中的所有元素小于pivot，$L[k+\mathrm{1...}n]$中的所有元素大于等于pivot，则pivot放在了其最终位置$L(k)$上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

时间复杂度：O(n*递归层数)，空间复杂度：O(递归层数)

#include 
#include 

using namespace std;

int Partition(vector<int>& a, int low, int high) {
	int pivot = a[low];       //第一个元素做枢轴
	while (low < high) {      //用low,high搜索枢轴最终位置
		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;
}

void QuickSort(vector<int>& a, int low, int high) {
	if (low < high) {  // 递归跳出条件
		int pivotpos = Partition(a, low, high);  //划分
		QuickSort(a, low, pivotpos - 1);         //划分左子表
		QuickSort(a, pivotpos + 1, high);        //划分右子表
	}
}

int main()
{
	vector<int> num = {49, 38, 65, 97, 76, 13, 27, 49 };

	QuickSort(num, 0, num.size() - 1);

	for (int i = 0; i < num.size(); i++) {
		cout << num[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

结果

13 27 38 49 49 65 76 97
1

选择排序

每一趟在待排序元素中选取关键字最小的元素加入有序子序列。总共必须进行n-1趟处理。可用于顺序表，也可用于链表。算法不稳定。时间复杂度：O(n^2)，空间复杂度：O(1)

#include 
#include 

using namespace std;

void SelectSort(vector<int>& a, int n) {
	for (int i = 0; i < n - 1; i++) {       //一共进行n-1趟
		int min = i;                        //记录最小元素位置
		for (int j = i + 1; j < n; j++) {   //在a[i...n-1]中选择最小的元素
			if (a[j] < a[min])
				min = j;                    //更新最小元素位置
		}
		if (min != i) swap(a[i], a[min]);   //封装的swap()函数共移动元素3次
	}
}
int main()
{
	vector<int> num = { 49, 38, 65, 97, 76, 13, 27, 49 };

	SelectSort(num, num.size());

	for (int i = 0; i < num.size(); i++) {
		cout << num[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

结果

13 27 38 49 49 65 76 97
1

堆排序

什么是堆？若n个关键字序列$L[\mathrm{1...}n]$满足下面某一条性质，则称为堆(Heap)

• 若满足：$L(i)\ge L(2i)$且$L(i)\ge L(2i+1)$，$(1\le i\le n/2)$ —— 大根堆
• 若满足：$L(i)\le L(2i)$且$L(i)\le L(2i+1)$，$(1\le i\le n/2)$ —— 小根堆

如何基于堆进行排序？先将数组构造成大根堆，然后每一趟将堆顶元素加入有序子序列(与待排序序列中的最后一共元素交换)，并将交换后的待排序序列再次调整为大根堆(小元素不断下坠)。因此，每次从大根堆的堆顶元素放到末尾。基于大根堆得到的是递增序列。

堆排序时间复杂度：$O(nlo{g}_{2}n)$，空间复杂度：O(1)。堆排序是不稳定的。

#include 
#include 

using namespace std;

void HeadAdjust(vector<int>& a, int k, int len);

void BuildMaxHeap(vector<int>& a, int len) {
	for (int i = len / 2; i > 0; i--) {  // 从后往前调整所有非终端节点
		HeadAdjust(a, i, len);
	}
}

//修改以k为根的子树调整为大根堆
void HeadAdjust(vector<int>& a, int k, int len) {
	a[0] = a[k];                                 //a[0]暂存子树的根节点  
	for (int i = 2 * k; i <= len; i *= 2) {      //沿key较大的子结点向下筛选
		if (i < len && a[i] && a[i] < a[i + 1])  
			i++;                                 //取key较大的子结点下标
		if (a[0] >= a[i]) break;                 //筛选结束
		else {
			a[k] = a[i];                         //将a[i]调整到双亲结点上
			k = i;                               //修改k值，以便继续向下筛选
		}
	}
	a[k] = a[0];                                 //被筛选结点的值放入最终位置
}

//堆排序的完整逻辑
void HeapSort(vector<int>& a, int len) {
	BuildMaxHeap(a, len);                        //初始建堆
	for (int i = len; i > 1; i--) {              //n-1趟的交换和建堆过程
		swap(a[i], a[1]);                        //堆顶元素和堆底元素交换
		HeadAdjust(a, 1, i - 1);                 //把剩余待排序元素整理成堆
	}
}

int main()
{
	vector<int> num = { 0, 49, 38, 65, 97, 76, 13, 27, 49 };

	HeapSort(num, num.size() - 1);

	for (int i = 1; i < num.size() - 1; i++) {
		cout << num[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

结果

13 27 38 49 49 65 76 97
1