数据结构初阶最终讲：排序

这一讲是数据结构初阶的最后一讲了，当然也是很有难度的一讲，是对于排序算法的总篇章，当然，会有其它更好的排序算法，但是对于初阶的数据结构来说，先学习这些就足够了

1.排序的概念及其运用

1.1什么是排序

排序，顾名思义，就是对一串数据，按照某个特定的顺序，将这一串数据进行有序排列的方法

1.2排序的运用

排序在我们日常生活中的使用十分广泛

当我们在网上购物，筛选自己心仪的产品时，就使用到了排序：

当我们在考试完后看自己的成绩排名时，也会用到排序：

1.3常见排序算法

下面是一些常见的排序算法，这一讲会将这些排序算法逐一实现

2.冒泡排序

冒泡排序对于教学来说很有意义，至少是我所学过的第一个排序算法，但是使用起来非常麻烦，它的时间复杂度为O(n^2)，是一个非常大的复杂度值了

//冒泡排序
void BubbleSort(int* arr, int n)
{
	//冒泡排序十分经典，而且使用很少，所以不再讲解，这里只会作为一个对比
	for (int i = 0; i < n-1; i++)
	{
		int def = 0;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				def = 1;
			}
		}
		//当没有一个数据交换时，表示已经排序完了，直接退出即可
		if (def == 0)
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.直接插入排序

上面是害怕大图会看不清，所以分成了三个小图，下面放大图：

我们会惊奇地发现，这个算法竟然和我们打扑克牌时整牌的操作一样！（至少和我是一样的）：

下面我们来使用代码实现这个思路：

//直接插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.堆排序

之前我们已经实现过堆排序了，所以这里也不再详细说明堆排序，直接将代码拿过来：

链接: 堆排序链接

//交换函数
void Swap(HeapDataType* x, HeapDataType* y)
{
	HeapDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

//堆的向上排序
void ADJustUp(HeapDataType* arr, int child)
{
	int father = (child - 1) / 2;
	while (child > 0)
	{
		//建大堆：>
		//建小堆：<
		if (arr[child] < arr[father])
		{
			Swap(&arr[child], &arr[father]);
			child = father;
			father = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//堆的向下排序
void ADJustDown(HeapDataType* arr, int father, int n)
{
	int child = father * 2 + 1;
	while (child < n)
	{
		//大堆：寻找左右孩子中最大的那个孩子
		//小堆：寻找左右孩子中最小的那个孩子
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child += 1;
		}
		//如果目标数据小/大的话，将最大的那个孩子与目标数据进行交换
		if (arr[father] < arr[child])
		{
			Swap(&arr[father], &arr[child]);
			father = child;
			child = father * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//堆排序
void HeapSort(int* arr, int sz)
{
	//首先需要一个数据一个数据地拿出来，创建一个堆
	for (int i = 0; i < sz; i++)
	{
		ADJustUp(arr, i);
	}

	//向下调整算法建堆
	int n = (sz - 1 - 1) / 2;
	for (int i = n; i >= 0; i--)
	{
		ADJustDown(arr, i, sz);
	}

	//先交换数据
	int end = sz;
	while(end > 1)
	{
		Swap(&arr[0], &arr[end - 1]);
		end--;
		//然后对堆中第一个数据进行向下排序
		ADJustDown(arr, 0, end);
	}
}
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

5.测试代码：排序性能对比

已经有了三种排序代码，哪一种排序的效率是最高的才是我们最想要看到的，所以我们需要一个测试排序性能的代码：

// 测试排序的性能对⽐
void TestOP()
{
	//-------------------1.----------------------
	//1,这里代表着生成十万个数据，方便后序进行排序
	//a1、a2、a3分别指代不同的排序方法
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	/*int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);*/
	int* a4 = (int*)malloc(sizeof(int) * N);
	/*int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);*/
	int* a7 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		/*a2[i] = a1[i];
		a3[i] = a1[i];*/
		a4[i] = a1[i];
		/*a5[i] = a1[i];
		a6[i] = a1[i];*/
		a7[i] = a1[i];
	}
	//-------------------1.----------------------
	//-------------------2.----------------------
	//2.clock是一个C语言中的函数，可以返回从程序开始运行到系现在所用的时间
	//用begin2 - begin1就可以得出算法运行的时间了
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	/*int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();*/

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	/*int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();*/

	int begin7 = clock();
	BubbleSort(a7, N);
	int end7 = clock();
	//-------------------2.----------------------
	//-------------------3.----------------------
	//3.最后将得出的时间进行打印并且销毁空间即可
	printf("InsertSort:%d\n", end1 - begin1);
	/*printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);*/
	printf("HeapSort:%d\n", end4 - begin4);
	/*printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);*/
	printf("BubbleSort:%d\n", end7 - begin7);
	free(a1);
	/*free(a2);
	free(a3);*/
	free(a4);
	/*free(a5);
	free(a6);*/
	free(a7);
	//-------------------3.----------------------
}
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

拥有了检测排序性能的函数之后，我们就可以直观地看出不同排序算法之间的效率差异了：

时间单位为毫秒，可以看出，冒泡排序竟然用了15秒！真是夸张，所以冒泡排序还是不足以应对生活中的排序的

5.1直接插入排序时间复杂度分析

//直接插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		//当外层循环一次时，内层循环最坏要交换i+1次，也就是下面的那样：
		//i        0  1  2  3  4  5  ...  n-1
		//循环次数 1  2  3  4  5  6  ...  n
		//循环次数是等差数列，求和并分析可以得出它的时间复杂度为O(n^2)
		//但是这个最坏情况是很难达到的，而冒泡排序两层循环，而且一一对比，为什么效率低很容易理解
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}
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

直接插入排序的时间消耗已经很不错了，但是还有一个人不满足，他想要优化插入排序，让插入排序更块，它就是希尔排序，我们来看：

6.希尔排序

然后是大图：

代码实现：

//希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while(gap > 1)
	{
		//当gap为3时，gap/3=1，所以刚循环一次就跳出循环，显然是不合理的，所以这里要+1
		gap = gap / 3 + 1;
		//注意：这里要考虑for循环中i的结束条件为什么是i<n-gap而不是i<n
		//当i = n-gap时，end+gap = n，此时已经发生了越界，所以i应该小于n-gap
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}
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

此时我们再来看一下运行时间：

竟然是11秒，比堆排序花费的时间还少了，是不是很振奋！！！

6.1希尔排序时间复杂度分析

对于希尔排序的时间复杂度的求解到目前仍然是一个相对困难的事，但是它的时间复杂度大约是n的1.3次方，这是由大量数据平均得来的：

现在我们进行简单的推导：

7.选择排序

7.1初步思路

初步实现思路就是选择最小的数据，将最小的数据往前移

代码实现：

//选择排序
void SelectSort(int* arr, int n)
{
	//这里的i就能够充当begin的作用，所以不用创建变量begin
	for (int i = 0; i < n; i++)
	{
		int mini = i;
		//先寻找最小的数据的下标
		for (int j = i+1; j < n; j++)
		{
			if (arr[j] < arr[mini])
			{
				mini = j;
			}
		}
		//找到最小的元素之后，交换
		Swap(&arr[mini], &arr[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

7.2选择排序优化

7.2.1初步实现

上一个实现思路的时间复杂度为o(n^2)，非常的不好，所以我们要进行优化：再创建一个指针，保存最大的数据，将小数据和大数据一起排列：

代码实现：

//选择排序--优化后--初步实现
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		//寻找最大和最小的数据
		for (int i = begin+1; i < n; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		//然后将大小数据插入到合适的位置
		Swap(&arr[begin++], &arr[mini]);
		Swap(&arr[end--], &arr[maxi]);
	}
}
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

然而，当我们对数据进行排序时，我们会发现：出错了！！！为什么呢？我们来探讨一下：

7.2.2出错点1

查找时应该在begin–end范围内查找，而不是begin–n范围

//选择排序--优化后
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		//寻找最大和最小的数据
		//更改点1：查找范围出错，i<n ---> i<end
		for (int i = begin+1; i < end; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		//然后将大小数据插入到合适的位置
		Swap(&arr[begin++], &arr[mini]);
		Swap(&arr[end--], &arr[maxi]);
	}
}
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

7.2.3出错点2

代码实现：

//选择排序--优化后
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		//寻找最大和最小的数据
		//更改点1：查找范围出错，i<n ---> i<end
		for (int i = begin+1; i < end; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		//出错点2：考虑maxi==begin的情况
		if (maxi == begin)
		{
			maxi = mini;
		}
		//然后将大小数据插入到合适的位置
		Swap(&arr[begin++], &arr[mini]);
		Swap(&arr[end--], &arr[maxi]);
	}
}
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

7.2.4出错点3

这个出错点和第一个出错点的位置一样，i的范围应该包括end，i<end是错的，只能是i<=end

代码更正：

//选择排序--优化后
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		//寻找最大和最小的数据
		//更改点1：查找范围出错，i<n ---> i<end
		//出错点3：i应该<=end
		for (int i = begin+1; i <= end; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		//出错点2：考虑maxi==begin的情况
		if (maxi == begin)
		{
			maxi = mini;
		}
		//然后将大小数据插入到合适的位置
		Swap(&arr[begin++], &arr[mini]);
		Swap(&arr[end--], &arr[maxi]);
	}
}
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

7.2.5选择排序优化最终代码

//选择排序--优化后
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;
		//寻找最大和最小的数据
		//更改点1：查找范围出错，i<n ---> i<end
		//出错点3：i应该<=end
		for (int i = begin+1; i <= end; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		//出错点2：考虑maxi==begin的情况
		if (maxi == begin)
		{
			maxi = mini;
		}
		//然后将大小数据插入到合适的位置
		Swap(&arr[begin++], &arr[mini]);
		Swap(&arr[end--], &arr[maxi]);
	}
}
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

7.3选择排序时间复杂度分析

选择排序外循环每次循环一次，内循环都要走一遍，所以它的时间复杂度为O(n^2)，时间复杂度太差，所以一般不用这个排序，只是让我们了解这个排序，并且直到这个排序算法并不理想，接着我们看一下排十万个数据的时间吧：

可以看出，当冒泡排序时间才为4秒时，选择排序就排了3秒，所以说不好用，下面我们就要讲一个排序的"神"算法–快速排序，也就是我们熟知的快排

8.快速排序–Hoare版本

看起来十分难懂啊，我们不用管这些，让我画图进行理解：

8.1.1代码的初步实现

//快速排序
//寻找基值的函数，返回基值的下标
int _QuickSort(int* arr, int left, int right)
{
	int key = 0;
	while (left <= right)
	{
		//找出比基值大的数据
		while(arr[left] < arr[key])
		{
			//当找到的数据比基值小时，往后找，直到找到比基值大的数据
			left++;
		}
		//找出比基值小的数据
		while (arr[right] > arr[key])
		{
			//当找到的数据比基值大时，往前找，直到找到比基值小的数据
			right--;
		}
		//然后将大小数据进行交换
		Swap(&arr[left], &arr[right]);
	}
	//最后将基值赋值到right，right就成为了基值下标
	Swap(&arr[key], &arr[right]);
	return right;
}

//与其他排序方法不同，这里应该传入数组、排序区域的左区间、排序区域的右区间
void QuickSort(int* arr, int left, int right)
{
	//递归结束条件
	//当left和right重合时，表示此时只有一个结点，退出递归
	if (left >= right)
	{
		return;
	}

	//寻找基值
	int key = _QuickSort(arr, left, right);

	//递归寻找基值
	QuickSort(arr, left, key-1);
	QuickSort(arr, key + 1, right);
}
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

8.1.2错误点1

第五行代码我们竟然就已经出错了，做题一定要仔细！

//快速排序
//寻找基值的函数，返回基值的下标
int _QuickSort(int* arr, int left, int right)
{
	//错误点1：key应该等于left，指向的是排序数组中的第一个数据，而不是整个数组中的第一个数据
	int key = left;
1
2
3
4
5
6

8.1.3错误点2

仍然是第五行，而且还是特别明显的错误：

//快速排序
//寻找基值的函数，返回基值的下标
int _QuickSort(int* arr, int left, int right)
{
	//错误点1：key应该等于left，指向的是排序数组中的第一个数据，而不是整个数组中的第一个数据
	int key = left;
	//错误点2：left指向的位置应该是key位置之后的数据，而不是指向key这个位置
	++left;
1
2
3
4
5
6
7
8

8.1.4错误点3

这是一个注意点，因为错误率很高：

//快速排序
//寻找基值的函数，返回基值的下标
int _QuickSort(int* arr, int left, int right)
{
	//错误点1：key应该等于left，指向的是排序数组中的第一个数据，而不是整个数组中的第一个数据
	int key = left;
	//错误点2：left指向的位置应该是key位置之后的数据，而不是指向key这个位置
	++left;
	//注意点3：当left=right时，仍然要进入循环
	while (left <= right)
1
2
3
4
5
6
7
8
9
10

8.1.5错误点4

while (left <= right)
{
	//错误点4：假设待排序数组中的所有数据都比基值数据大，left会一直向后++，会发生越界情况，所以这边的判断需要加上一个条件
	//找出比基值大的数据
	while (left<=right && arr[left] < arr[key])
	{
		//当找到的数据比基值小时，往后找，直到找到比基值大的数据
		left++;
	}
	//错误点4：和上边的错误点4一样
	//找出比基值小的数据
	while(left<=right && arr[right] > arr[key])
	{
		//当找到的数据比基值大时，往前找，直到找到比基值小的数据
		right--;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8.1.6错误点5

这也是一个注意点

//错误点4：假设待排序数组中的所有数据都比基值数据大，left会一直向后++，会发生越界情况，所以这边的判断需要加上一个条件
//找出比基值大的数据
//注意点5：假设所有数据都为6，如果这里的判断条件为arr[left] <= arr[key]的话，left会一直向后++，right一直向前--，
//        导致基值不变，造成死循环，所以这边的判断条件不能为=
while(left<=right && arr[left] < arr[key])
{
	//当找到的数据比基值小时，往后找，直到找到比基值大的数据
	left++;
}
//错误点4：和上边的错误点4一样
//找出比基值小的数据
//注意点5：和上边注意点5相同
while(left<=right && arr[right] > arr[key])
{
	//当找到的数据比基值大时，往前找，直到找到比基值小的数据
	right--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

8.1.7错误点6

在交换时要加上前置条件，否则会出现下面的情况：

//错误点6：交换时要加上前置条件
if(left<=right)
{
	//然后将大小数据进行交换
	Swap(&arr[left], &arr[right]);
}
1
2
3
4
5
6

8.1.8错误点7

//错误点6：交换时要加上前置条件
if(left<=right)
{
	//然后将大小数据进行交换
	//错误点7：交换完之后要注意改变left和right，在思路图中想到了，但是没有实现在代码上
	Swap(&arr[left++], &arr[right--]);
}
1
2
3
4
5
6
7

8.2Hoare版本快排最终代码

//快速排序
//寻找基值的函数，返回基值的下标
int _QuickSort(int* arr, int left, int right)
{
	//错误点1：key应该等于left，指向的是排序数组中的第一个数据，而不是整个数组中的第一个数据
	int key = left;
	//错误点2：left指向的位置应该是key位置之后的数据，而不是指向key这个位置
	++left;
	//注意点3：当left=right时，仍然要进入循环
	while (left <= right)
	{
		//错误点4：假设待排序数组中的所有数据都比基值数据大，left会一直向后++，会发生越界情况，所以这边的判断需要加上一个条件
		//找出比基值大的数据
		//注意点5：假设所有数据都为6，如果这里的判断条件为arr[left] <= arr[key]的话，left会一直向后++，right一直向前--，
		//        导致基值不变，造成死循环，所以这边的判断条件不能为=
		while (left<=right && arr[left] < arr[key])
		{
			//当找到的数据比基值小时，往后找，直到找到比基值大的数据
			left++;
		}
		//错误点4：和上边的错误点4一样
		//找出比基值小的数据
		//注意点5：和上边注意点2相同
		while (left<=right && arr[right] > arr[key])
		{
			//当找到的数据比基值大时，往前找，直到找到比基值小的数据
			right--;
		}
		//错误点6：交换时要加上前置条件
		if(left<=right)
		{
			//然后将大小数据进行交换
			//错误点7：交换完之后要注意改变left和right，在思路图中想到了，但是没有实现在代码上
			Swap(&arr[left++], &arr[right--]);
		}
	}
	//最后将基值赋值到right，right就成为了基值下标
	Swap(&arr[key], &arr[right]);
	return right;
}

//与其他排序方法不同，这里应该传入数组、排序区域的左区间、排序区域的右区间
void QuickSort(int* arr, int left, int right)
{
	//递归结束条件
	//当left和right重合时，表示此时只有一个结点，退出递归
	if (left >= right)
	{
		return;
	}

	//寻找基值
	int key = _QuickSort(arr, left, right);

	//递归寻找基值
	QuickSort(arr, left, key-1);
	QuickSort(arr, key + 1, right);
}
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

8.3快速排序空间复杂度分析

函数递归每调用一次就会创建一次函数栈帧，每次return循环结束之后就会销毁函数栈帧，而快排在调用时的作用如图：

每一次递归就会将原数组分为两半，所以求空间复杂度，就是求这个二叉树的深度，也就是log2N，所以快速排序的空间复杂度为log2N

8.4快速排序时间复杂度分析

8.4.1最优情况（平均情况）

对于一个具有n个数据的数组来说，每一层需要交换的数据为n个，而深度为longN，所以总的排序工作量为NlogN，时间复杂度也就是O(NlogN)

8.4.2最坏情况

如果每次分区都极度不均衡，也就是每次基值都是数组中最大的数据或最小的数据，此时快速排序的时间复杂度就退化为O(n^2)

8.5观察快速排序的排序时间

快速排序在排序中是最快的，所以我们一定会很期待快排的发挥：

可以看出，在十万个数据中，快排只需要4ms，这次我们增大数据量，将数据增加到100万：

对于100万个数据，快速排序只用了39ms，相当快速，这时希尔排序只是个意外【笑哭】

9.快速排序–挖坑法

挖坑法为查找基值提供了一个新的思路，我们来看：

代码实现：

int _QuickSort(int* arr, int left, int right)
{
	//先在第一个值的位置挖坑
	int hole = left;
	//将第一个坑中的值保存下来
	int key = arr[left];
	while (left < right)
	{
		//先让right向前走
		//错误点1：此时要加上=，当数组中的数据全为6时，如果不加等号的话right的值不会改变，程序会死循环
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		//填坑挖新坑
		arr[hole] = arr[right];
		hole = right;
		//再让left向后走
		//错误点1：看上边错误点1
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	return hole;
}

//与其他排序方法不同，这里应该传入数组、排序区域的左区间、排序区域的右区间
void QuickSort(int* arr, int left, int right)
{
	//递归结束条件
	//当left和right重合时，表示此时只有一个结点，退出递归
	if (left >= right)
	{
		return;
	}

	//寻找基值
	int key = _QuickSort(arr, left, right);

	//递归寻找基值
	QuickSort(arr, left, key-1);
	QuickSort(arr, key + 1, right);
}
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

10.快速排序–lomuto前后指针

代码实现：

//Lomuto法
int _QuickSort(int* arr, int left, int right)
{
	int key = left;
	int prev = left;
	int pcur = left +1;
	while (pcur < right)
	{
		if (arr[pcur] < arr[key] && ++prev!=pcur)
		{
			Swap(&arr[pcur], &arr[prev]);
		}
		pcur++;
	}
	Swap(&arr[key], &arr[prev]);
	return prev;
}

//与其他排序方法不同，这里应该传入数组、排序区域的左区间、排序区域的右区间
void QuickSort(int* arr, int left, int right)
{
	//递归结束条件
	//当left和right重合时，表示此时只有一个结点，退出递归
	if (left >= right)
	{
		return;
	}

	//寻找基值
	int key = _QuickSort(arr, left, right);

	//递归寻找基值
	QuickSort(arr, left, key-1);
	QuickSort(arr, key + 1, right);
}
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

11.快速排序–非递归版本

上面我们实现的快速排序都是在递归的基础上实现的，下面我们接触一个新的非递归实现快排的方法：

代码实现：

//快速排序--非递归版本
void QuickSortNoneD(int* arr, int left, int right)
{
	Stack s;
	Init(&s);

	//先将右值和左值入栈
	StackPush(&s, right);
	StackPush(&s, left);

	//当栈为空时，结束循环
	while (s.top != 0)
	{
		//先从栈中取左值和右值
		left = StackPrint(&s);
		StackPop(&s);
		right = StackPrint(&s);
		StackPop(&s);

		//然后在左值--右值这一块空间中寻找基值--lomuto指针法
		int keyi = left;
		int prev = left;
		int pcur = left +1;
		while (pcur <= right)
		{
			if (arr[pcur] < arr[keyi] && ++prev != pcur)
			{
				Swap(&arr[pcur], &arr[prev]);
			}
			pcur++;
		}
		Swap(&arr[keyi], &arr[prev]);
		//此时基值为prev

		//然后再次入栈，先让右数组入栈，再让左数组入栈
		//1.当只有一个数据时不用入栈
		//2.当数组的指向越界时不用入栈
		//左数组：[left, prev-1]
		//右数组：[prev+1, right]
		if (prev + 1 < right)
		{
			StackPush(&s, right);
			StackPush(&s, prev + 1);
		}
		if (left < prev - 1)
		{
			StackPush(&s, prev - 1);
			StackPush(&s, left);
		}
	}

	Destory(&s);
}
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

此时再使用100万个数据进行检测：

快速排序依旧很强势！！！

12.归并排序

其实就是先递归，然后排序

代码实现：

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
	//递归结束条件：left>=right
	if (left >= right)
	{
		return;
	}

	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//递归完成，开始向上排序
	int begin1 = left, end1 = mid;

	int begin2 = mid + 1, end2 = right;
	//对数组进行排序，谁小谁插入到新的数组中
	//错位点1：这里的i应该指向left，不能指向0
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];
		}
	}
	//退出循环只有两种可能：
	//1.begin1的数组为空
	//错误点2：这里应该为while，不能是if
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}
	//2.begin2的数组为空
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	//最后要将tmp中的数据赋值到arr数组中
	//错误点3：这里j应该初始化为left，不能为0
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}

void MergeSort(int* arr, int n)
{
	//开辟新的数组空间来存储排序好的数据
	int* tmp = (int*)malloc(sizeof(int) * n);

	//递归进行排序
	_MergeSort(arr, 0, n - 1, tmp);

	free(tmp);
}
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

对100万数据进行排序的结果：

毋庸置疑是一个非常好用的排序方法！！！

12.1归并排序时间复杂度分析

对于归并排序，假设有N个数据，那么递归的深度为logN，而每一层递归都是要将这一层的数据进行排序，所以它的时间复杂度为NlogN

12.2归并排序空间复杂度分析

归并排序使用过程中开辟了一个数组的空间，所以它的空间复杂度为O(N)

13.非比较排序–计数排序

之前所使用的所有排序算法都是通过数据之间的比较，从而将大数和小数区分出来的，现在我们要掌握一种不需要比较就能够进行排序的算法

代码实现：

//非比较排序
void CountSort(int* arr, int n)
{
	//先确定数组中的最大值和最小值
	int max = arr[0];
	int min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}

	//然后通过最大值和最小值来开辟空间
	int capacity = max - min + 1;
	int* tmp = (int*)malloc(capacity * sizeof(int));
	//将开辟的空间初始化为0
	memset(tmp, 0, capacity * sizeof(int));

	//将原数组中每个数据出现的次数存储到开辟数组中
	for (int i = 0; i < n; i++)
	{
		tmp[arr[i] - min]++;
	}

	//通过开辟数组记录的数据实现排序
	int index = 0;
	for (int i = 0; i < capacity; i++)
	{
		while (tmp[i]--)
		{
			arr[index++] = i + min;
		}
	}
}
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

然后我们让这个排序算法来排100万个数据：

仅仅用了1ms！！！但是这个算法有致命的缺点：
1.无法对小数进行排序
2.对于整数的排序在特殊情况下空间浪费多

13.1非比较函数时间复杂度分析

//非比较排序--时间复杂度分析--O(N)
void CountSort(int* arr, int n)
{
	int max = arr[0];
	int min = arr[0];
	//O(N)
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}

	int capacity = max - min + 1;
	int* tmp = (int*)malloc(capacity * sizeof(int));
	memset(tmp, 0, capacity * sizeof(int));
	//O(N)
	for (int i = 0; i < n; i++)
	{
		tmp[arr[i] - min]++;
	}
	//此处虽然是两层循环，但是作用是遍历开辟数组，对arr数组进行赋值
	//所以此处的时间复杂度还是O(N)
	int index = 0;
	for (int i = 0; i < capacity; i++)
	{
		while (tmp[i]--)
		{
			arr[index++] = i + min;
		}
	}
}
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

14.排序算法复杂度以及稳定性分析

总结：

分析：

到这里，所有排序已经讲完，之后将要学习C++的内容，也是成功地脱离新手村了，希望自己能够坚持下来！！！