【数据结构与算法】排序（上篇）

🐱作者：一只大喵咪1201
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！

前面已经学习了很多类型的数据结构，接下来本喵介绍一下排序。

排序：

• 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

常见的排序有很多，如下图中所示：

接下来本喵会详细的讲解这几种排序。

📇插入排序

📊直接插入排序

基本思想

现有一组数据15,27,47,3,26,36 ，将它们按照升序排列。

• 在数组中划分出一个小数组下标为[0，end]
• 将end+1指向的元素与小数组中的元素逐个比较
• 当end+1指向的元素比前面数组中的某一个元素小的时候，将end+1指向的元素插入到这个元素之前
• 如此重复，直到end指向倒数第二个元素
  

下面动图展示了排序的整个过程。

• 蓝色表示的是end+1指向的元素
• 绿色表示的是end指向的元素
• 紫色表示的是复制end指向的元素
• 整个过程就是，end从0开始，end+1存入临时变量temp中，并且指向的元素与[0，end]范围内的元素从后往前比较，当end指向的元素比end+1指向的元素大的时候，用end的元素覆盖end+1的元素，end向前移动直到0。
• 再将end从1开始，重复上诉过程，再将end从2开始，直到end指向倒数第二个元素时，这组数字就被按照升序排好了。

代码实现：

void InsertSort(int* a, int n)
{
	//插入值的最后一个是在倒数第一个
	for (int i = 0; i < n - 1 - 1; i++)
	{
		int end = i;//设置小数组区间
		int temp = a[end + 1];//记录待插入值
		while (end >= 0)
		{
			//插入值比有序小数组中最大值小
			if (a[end] > temp)
			{
				//小数组中的数整体向后移动
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				//当插入值大于等于小数组中某一个值停止循环
				break;
			}
		}
		//插入值
		a[end + 1] = temp;
	}
}
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

从结果中看到，已经按升序排列了。

注意：

• 小数组的左边下标始终是0，有边下标是逐渐增加的，最多只能增加到倒数第二个元素的下标
• 每个小数组进行一次插入排序，排序后的小数组是有序的

时间复杂度和空间复杂度：

1. 时间复杂度

我们知道，一个算法的时间是复杂度是按照最坏情况来算的，我们要实现的是将一组数按照升序排列，那么最坏的情况就是这组数是降序排列的。

比如：9 8 7 6 5 4 3 2 1

接下来看用直接插入法将这组数按照升序排列的时间复杂度是多少

• 插入8时，移动一次，插入7时移动俩次，插入6时移动3次，依次类推，插入最后一个数时需要移动N-1次
• 一共需要移动1/2N(N-1)次
• 该算法的时间复杂度是O(N²)

如果是一组数据已经是升序排列了，那么该算法的时间复杂度是多少呢？

• 此时不需要移动，只需要进行N-1次比较，所以时间复杂度是O(N)

所以说，在元素集合越接近有序，直接插入排序算法的时间效率越高。

2. 空间复杂度

该算法并没有开辟临时的额外空间，所以空间复杂度是O(1)。

📊希尔排序

• 希尔排序法又称缩小增量法。
• 希尔排序法的基本思想是：先选定一个整数n，把待排序文件中所有距离为n的记录分在同一组内，并对每一组内的记录进行排序。然后，取 n=n/3重复上述分组和排序的工作。
• 当到达=1时，所有记录在统一组内排好序。

本喵接下来详细讲解一下。

有这样一组数 9 1 2 5 7 4 8 6 3 5，将这组数按照升序排列。

希尔排序有俩部分，

1. 预排序

预排序的目的是让这组数接近有序。

我们取间隙距离gap=3。

按照3的间距，可以将这组数据分为3组，

• 红线指向的为一组，是9 5 8 5
• 绿线指向的为一组，是1 7 6
• 蓝线指向的是一组，是2 4 3

将这三组数据分别用直接插入法进行排序

三组分别插入排序后如上图中的样子，然后将三组放在一起看

虽然说仍然不是按照升序排列，但是相对于最开始的数据来说，已经变的比较有序了，这个过程就叫做预排序。

来看下预排序的代码实现

{
	//gap为3，一共10个元素，最多分三组
	for (int j = 0; j < 3; j++)
	{
		int gap = 3;
		//插入排序，只是步长变为了gap
		for (int i = j; i < n - gap; i += gap)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}
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

可以看到，预排序的结果和我们分析的一致。

注意：

• 最外的循环次数就是数据分组的个数，由于一共10个元素，gap=3，所以最多分10/3=3组，也就循环三次，就可以将上面提到的红绿蓝三种颜色线指向的组进行预排序
• 具体进行插入排序时，逻辑和上面的直接插入排序是一样的，只是步长不再是1，而是变成了gap。

我们看到，这样是有三次循环的，可以将代码简化为俩层循环，只需要将做如下修改

此时预排序并不是一组一组的进行插入排序，而是齐头并进的排序。

• 绿色的数据就是i为下标时指向的数据，淡紫色的数据是待插入的数据
• i从0开始到n-gap直接，当i位于哪一组时，就用插入排序排哪一组，此时就是三组一起进行的，而不是一组一组单独进行排序的。

在预排序完成以后，此时数据是相对有序的，我们知道，直接插入排序对比较有序的数据进行排序是效率很高的，所以对此时预排序后的数据进行直接插入排序。

2. 直接插入排序

此时的gap是为1的，和直接插入排序的逻辑一样，步长也为1。

代码实现：
为了使预排序后的结果更加有序，我们将间隙gap逐渐减小进行多次预排序，代码如下

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//间距每次缩小三倍，保证间距最小为1
		//插入排序，只是步长变为了gap
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}
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

注意：

• 间距gap越大，大的数据就会越快跳到后面，小的数据也会越快跳到前面，但是不是很接近有序。
• 间距gap越小，大的数据就会越慢跳到后面，小的数据也会越慢跳到前面，而且更接近有序
• gap/3+1中的加1是为了保证最后一次排序的间距是1。

时间复杂度和空间复杂度：

1. 时间复杂度

以本喵目前的数学知识是算不出来的，只能分析一个大概。

希尔排序的时间复杂度非常难计算，根据这些大佬的计算，我们知道它的时间复杂度是O(N^1.3)

所以说，希尔排序是直接插入排序的的优化。

2. 空间复杂度

在排序的过程中同样没有开辟出新的临时空间，所以空间复杂度是O(1)

对比测试

void TimeCompare()
{
	int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	assert(a1);
	int* a2 = (int*)malloc(sizeof(int) * N);
	assert(a2);

	//生成N个随机数
	int i = 0;
	for (i = 0; i < N; i++)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}

	//直接插入排序
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	//希尔排序
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);

	free(a1);
	free(a2);
}

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

随机生成十万个数字，分别用直接插入排序和希尔排序将它们按照升序排列，通过看它们所消耗的时间来看这俩个排序的效率。

• 直接插入排序用时7634ms，希尔排序用时22ms，可以看到，希尔排序的效率比直接插入排序的效率高的多。

📇选择排序

📊选择排序

基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

有这样一组数 9 1 2 5 7 4 8 6 3 5，将这组数按照升序排列。

将其稍微优化一下，每次找出数据中的最小和最大的，将最小的放在前面，大的放在后面。

• begin和end是数组的下标，begin增加，end减小逐渐缩小数组
• 淡蓝色框中的是数组中的最大值，放在数组的最后面
• 淡黄色框中的是数组中的最小值，放在数组的最前面

代码实现：

//选择排序
void SelectSort(int* a, int n)
{
	//设置数组区间下标
	int begin = 0;
	int end = n - 1;
	//左下标小于又下标时，循环继续
	while (begin < end)
	{
		//假设最小值和最大值的下标都是数组首元素
		int min = begin;
		int max = begin;
		//寻找真正的最大值和最小值
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[min])
			{
				min = i;
			}
			if (a[i] > a[max])
			{
				max = i;
			}
		}
		//最小值和数组首元素交换
		Swap(&a[min], &a[begin]);
		//当最大值是数组首元素时
		if (max == begin)
			max = min;//将真正的最大值下标给max
		//最大值和数组最后一个元素交换
		Swap(&a[max], &a[end]);
		begin++;
		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

注意：

• 假设数组的第一个元素就是最大的元素
• 在将最小的元素和首元素交换以后，最大的元素去了原本最小的位置，数组首元素变成了最小的元素
• 在将最大元素和数组最后一个元素交换的时候，实质上就是将数组首元素与最后一个元素交换
• 但是在上一步交换的时候，数组首元素已经成为了最小的元素，所以这次交换是错误的交换
• 所以需要在红色框内，将第一次交换后数组最大元素的真正位置给到max，在第二次交换才能得到正确的结果。

时间复杂度和空间复杂度：

1. 时间复杂度

在选择排序中，无论数据是什么样的，都会发生交换

可以看到，选择排序的时间复杂度是O(N²)，它和数据是否有序没有关系，固定就是O(N²)

2. 空间复杂度

在整个过程中没有开辟临时空间，所以空间复杂度是O(1)。

📊堆排序

堆排序的具体实现原理本喵在文章二叉树——堆中详细讲解了它的实现原理，这里就不再讲解，我们只和选择排序作比较。

void TimeCompare()
{
	int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	assert(a1);
	int* a2 = (int*)malloc(sizeof(int) * N);
	assert(a2);
	srand((unsigned int)time(NULL));

	//生成N个随机数
	int i = 0;
	for (i = 0; i < N; i++)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}

	//直接插入排序
	int begin1 = clock();
	SelectSort(a1, N);
	int end1 = clock();

	//希尔排序
	int begin2 = clock();
	HeapSort(a2, N);
	int end2 = clock();

	printf("SelectSort:%d\n", end1 - begin1);
	printf("HeapSort:%d\n", end2 - begin2);

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

可以看到，同一组数据进行升序排列，堆排序的效率比选择排序的效率高很多。

📇交换排序

• 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
• 交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

📊冒泡排序

有这样一组数 9 1 2 5 7 4 8 6 3 5，将这组数按照升序排列。

本喵这里仅展示了一趟，按照上面的逻辑进行n-1趟就是冒泡排序。

当然，为了提高效率，我们要加一些控制条件，在它已经排好，但是没有达到n-1趟的时候停下来。

代码实现：

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int exchange = 1;
		int j = 0;
		for (j = 0; j < n -i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				exchange = 0;
			}
		}
		if (exchange)
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

注意：

• 由于每进行一趟排序，就将一个数放在了它该在的位置上
• 所以每进行一次，需要排序的数据就少一个

时间复杂度和空间复杂度：

1. 时间复杂度

同样是一个等差数列，所以该算法的时间复杂度是O(N²)，当已经有序的时候，只需要比较N次，所以时间复杂度是O(N)

2. 空间复杂度

没有开辟临时的变量，所以空间复杂度的O(1)。

📊快速排序

快速排序是Hoare于1 962年提出的一种二叉树结构的交换排序方法，

• 其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

光看概念肯定是一脸懵的，接下来本喵详细给大家讲解一下。

有这样一组数 6 1 2 7 9 3 4 5 10 8，将这组数按照升序排列。

快排的每一趟排列有三种方法：

1. hoare版本

这个版本是hoare大佬提出来的，我们来看看它是怎么实现的。

• 首先需要选定一个值作为key，这里为了编程时方便，我们选择最左边的值作为key

过程描述：

• 左喵指向key处，右喵指向最右边的值
• 左喵不动，右喵开始向左移动寻找比key小的值，找到以后停下来不动
• 次数左喵开始向右移动寻找比key大的值，找到以后停下来
• 将次数左喵和右喵指向的值左交换
• 交换后继续左喵不动，右喵向左移动寻找比key小的值，找到后再保持不动，让右喵向右移动找比key大的值，找到后俩喵指向的值交换
• 如此重复，知道左喵撞上右喵后，将key与相撞位置的值交换
• 此时便完成了一趟

这一趟结束后达到了什么效果呢？我们可以看到，比key大的值都在key的右边，比key小的值都在key的左边，也就是说，次数的key已经处于最终的位置了，后续的排列并不会改变key的值。

每进行一趟hoare排序就排好一个值。

注意

这里一定是左喵撞上右喵，因为永远都是右喵移动完以后等着左喵移动。

这一趟hoare排序的代码实现：

//hoare版本的一趟排序
void PartSortHoare(int* a, int left, int right)
{
	//设定key值
	int keyi = left;
	//不相撞进入循环
	while (left < right)
	{
		//找左边比key小的
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//找右边比key大的
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		//确保没有相撞
		if (left < right)
			Swap(&a[left], &a[right]);//交换
	}
	//将key值和相撞位置的值交换
	Swap(&a[left], &a[keyi]);
}
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

与上面动图中分析一致。

注意：

• 在找比key小和比key大的值的时候，也要确保没有相撞，所以要加上left
• 必须加等号，否则会出现死循环，如果没有等号时，当右喵指向的值等于key，此时右喵停下来，左喵移动，左喵指向的值也等于key时也停下来并交换，此时交换过后俩喵指向的值都和key相同，也不会再移动，所以就会陷入死循环
• 在交换之前要确保没有相撞，因为不知道循环结束是在什么情况下结束的。

2. 挖坑法

同样是这一组数 6 1 2 7 9 3 4 5 10 8，将这组数按照升序排列。

• 首先选定key值，存放在临时变量key里，为了编程方便，我们选第一个数为key值

• 第一个数为key值，左喵所指向的粉色位置就形成一个坑
• 左喵不动，右喵向左移动寻找比key小的值，找到后停下来，并且将该值复制到左喵所指向的坑值，右喵指向的位置成为新的坑
• 右喵不动，左喵向右移动寻找比key大的值，找到后听下来，并且将该值复制到右喵所指向的坑值，左喵指向的位置成为新的坑
• 如下反复，知道左喵撞上右喵，将key中的key值赋值到相撞的位置
• 此时一趟排序便完成了

这一趟结束后达到了什么效果呢？我们可以看到，比key大的值都在key的右边，比key小的值都在key的左边，也就是说，次数的key已经处于最终的位置了，后续的排列并不会改变key的值。

每进行一趟挖坑排序就排好一个值。

这一趟挖坑法代码的实现：

//挖坑法版本的一趟排序
void PartSortHole(int* a, int left, int right)
{
	//选定key
	int key = a[left];
	//选坑
	int hole = left;
	while (left < right)
	{
		//选比key小的
		while (left < right && a[right] >= key)
		{
			right--;
		}

		if (left < right)
		{
			//选出来后填坑
			a[hole] = a[right];
			//形成新的坑
			hole = right;
		}
		//选比key大的
		while (left < right && a[left] <= key)
		{
			left++;
		}
		if (left < right)
		{
			//选出来后填坑
			a[hole] = a[left];
			//形成新的坑
			hole = left;
		}
	}
	//最后的坑中放入key值
	a[hole] = key;
}
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

和我们分析的结果是一致的。

挖坑法和hoare法其实是差不多的，只是一个是复制，一个是交换。

3. 前后指针版本

同样是这一组数 6 1 2 7 9 3 4 5 10 8，将这组数按照升序排列。

• 首先将第一个元素选为key值

• 将前指针pre指向第一个元素，后指针cur指向第二个元素
• 俩个指针同时向后移动，当后指针cur指向的元素比key值大的时候，前指针pre停下来不动，后指cur针继续向后移动
• 当后指针cur指向的值比key小的时候，后指针cur停下来，前指针pre向后移动一位，指向比key大的这个元素，前侯之子指向的元素进行交换
• 后指针cur继续向后移动寻找比key小的值，找到后停下来，前指针pre向后移动一位将指向的比key大的值和cur指向的值交换。
• 如此重复，直到后指针cur越界后，将key值和前指针pre指向的值交换。
• 如此一趟排序便完成了。

这一趟结束后达到了什么效果呢？我们可以看到，比key大的值都在key的右边，比key小的值都在key的左边，也就是说，次数的key已经处于最终的位置了，后续的排列并不会改变key的值。

每进行一趟挖坑排序就排好一个值。

这一趟前后指针法代码的实现：

//前后指针法的一趟排序
void PartSortPointer(int* a, int left, int right)
{
	//选定key值
	int keyi = left;
	//给前后指针赋值
	int pre = left;
	int cur = left + 1;

	while (cur <= right)
	{
		//cur指向的值小于key的值
		if (a[cur] < a[keyi])
		{
			pre++;//pre指向比key大的值
			Swap(&a[cur], &a[pre]);//交换
		}
		cur++;//cur移动
	}
	//将key值和pre交换
	Swap(&a[pre], &a[keyi]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

和我们分析的一致。

注意

• 此时当pre指向的值和cur指向的值相等的时候，还会发生交换，同一个数进行交换没有意义，所以我们可以进行优化
  改为

	if (a[cur] < a[keyi] && ++pre != a[keyi])
	{
		//pre指向比key大的值
		Swap(&a[cur], &a[pre]);//交换
	}
1
2
3
4
5

🖇递归实现快排

我们已经学习了三种进行一趟的排序了，接下来用这些方法实现整个数组的升序排列。

同样是这一组数 6 1 2 7 9 3 4 5 10 8，将这组数按照升序排列。

基本思想

• 如上图，类似一个二叉树的结构
• 将第一层进行一趟排序，此时key值已经排好了
• 将key左边的区间和key值右边的区间再进行一趟排序，它们各自的key值也排好了
• 如此重复分割，按照二叉树的前序遍历的逻辑
• 当递归完成后，每一个key值就已经排好了，整个数组也就排好了。

由于在递归中会用到每一趟排序后的key值，所以我们需要让上面的三种一趟排序的方法返回key值

按照前序遍历的规则我们来将这组数据进行升序排列，代码实现：

//快速排序
void QuickSort(int* a, int left, int right)
{
	//返回条件
	if (left >= right)
		return;

	//获取排好的key值
	int keyi = PartSortHoare(a, left, right);
	//int keyi = PartSortHole(a, left, right);
	//int keyi = PartSortPointer(a, left, right);
	
	//递归
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

结果是升序排列。

注意：

返回条件：

• 看二叉树的中返回的情况

如上图中，返回的叶子节点情况有俩种：

1. 只有一个数字

• 此时该数字在数组中的左右下标是相等的

2. key值左边或者右边没有数字

• 如果是key值右边没有数字时，递归时传入的左右下标是key+1和right，此时key和right相等的，所以就会导致left大于right。
• 如果是key值左边没有数字时，递归传入的左右下标是left和key-1，此时key和right是相等的，所以就会导致left大于right。

所以返回条件就是left大于等于right。

• 进行一趟的排序，三种方法中选一种就可以

• 递归时，采用前序遍历的逻辑

时间复杂度

1. key值选中位数

• 假设每次key选的都是中位数，次数算出来最多移动的次数是NlogN + 1/2 * (logN)²，忽略掉小的项，所以此时的时间复杂度是O(NlogN)

2. key值选最左边的数
   

• 假设每次key选的都是最左边的数字，次数算出来就是1/2 * (N + 1)*N，是等差数列前N项的和，忽略掉小项后，时间复杂度是O(N²)

通过上诉分析，我们可以看到，不同key的选取，算法的时间复杂度是天差地别的，所以我们需要对我们每一趟排序算法的取值进行优化。

优化取key值

优化key值的选取有很多种办法，有的随机选key值的，也有选中位数的，这里我们采用选中位数的办法。

将选中位数为key值封装成一个函数

//选取中位数
int GetMidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;//假设中间位置值是中位数

	//left < mid
	if (a[left] < a[mid])
	{
		//left < mid < right
		if (a[mid] < a[right])
			return mid;
		//right < left < mid
		else if (a[right] < a[left])
			return left;
		//left < right < mid
		else
			return right;
	}
	//left >= mid
	else
	{
		//left >= mid > right
		if (a[mid] > a[right])
			return mid;
		//right > left >= mid
		else if (a[right] > a[left])
			return left;
		//left > right > mid
		else
			return 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

• 这里的中位数并不是严格意义上的中位数，而是为了确保key值不在最左或者最右的中位数。

我们在实现每一趟的排序时，为了写代码方面，key值都是选的最左边的，此时我们用这个函数找到中位数，然后将中位数和最数组最左边的数据进行交换，我们之前的逻辑就可以直接使用。

这样就可以直接使用我们原来的逻辑。

小区间优化

• 高度是N层，一共有2^N-1个数
• 最后一层的数据个数是2^N-1个，接近总个数的%50
• 倒数第二层的数据个数是2^N-2个，接近总个数的%25
• 倒数第三层的数据个数是2^N-3个，接近总个数的%12.25
• 后三层的数据个数接近总个数的%87.25

在排序到倒数第三层的时候，数据已经非常接近有序了，继续用递归的方法不仅效率不高，还会因为函数调用占用很多的栈空间，可能导致栈溢出。

我们前面学习的插入排序对这种接近有序的数据排序的效率是非常高的，所以我们将后三层的数据使用插入排序。

代码实现：

	//后三层采用插入排序
	if (right - left <= 8)
		InsertSort(a + left, right - left + 1);
1
2
3

将这段代码插入到快速排序中

这样就将插入排序和快排结合了起来，效率会更高。

• 因为2³的结果是8，所以我们的控制条件是数组中的数据个数小于等于8，此时下面还有三层没有递归，将它们使用插入排序来排列。

🖇非递归实现快排

递归就要建立多层函数栈帧，由于栈区的内存是有限的，所以当处理的数据量非常大达到时候，递归实现的快排就会发生栈溢出的错误，为了避免这个问题，可以使用非递归实现快排，使用堆区的空间来实现，因为堆区相对于栈区大了不止一点。

基本思想

• 通过观察递归版本的代码我可以发现，递归使用的是仅仅是key的值，那我们就可以模拟递归的执行过程，采用循环的方式来实现快排
• 栈这个结构就可以很好的模拟递归的实现过程

仍然是这一组数 6 1 2 7 9 3 4 5 10 8

递归的过程就是：

• 第一层从key处分为俩个子区间
• 第二次从俩个数组的key处再分为子区间

那么我们就用一个栈来模拟一下这个过程

• 入栈第一组下标，最左边和最右边的，然后再出栈，利用一趟排序求出key值下标
• 根据key值下标将上一组分成的俩个数组，按照先入右边那一组下标，再入左边那组的下标的顺序入栈俩组下标
• 出栈，利用一趟排序求出的key的下标继续重复上面的过程入栈出栈
• 直到栈为空，此时就将这组数据排列好了

代码实现：
先创建一个结构体用于存放数组的左右下标：

typedef struct Index
{
	int left;
	int right;
}Index;
1
2
3
4
5

//非递归快排
void QuickSortNonR(int* a, int left, int right)
{
	ST st;//创建栈
	StackInit(&st);//初始化栈

	Index pointer = { left,right };//创建第一组下标

	StackPush(&st, pointer);//第一组下标入栈

	//栈为空时停止循环
	while (!StackEmpty(&st))
	{
		//拿栈顶中的左右下标
		pointer = StackTop(&st);
		StackPop(&st);
		int left = pointer.left;
		int right = pointer.right;

		//将左右下标范围内的数组进行一趟排序后得到key值下标
		int keyi = PartSortHoare(a, left, right);

		//分割后子数组个数为零，则不压栈
		if (keyi + 1 < right)
		{
			//先压栈右边子数组的左右下标
			pointer.left = keyi + 1;
			pointer.right = right;
			StackPush(&st, pointer);
		}
		if (keyi - 1 > left)
		{
			//再压栈左边子数组的左右下标
			pointer.left = left;
			pointer.right = keyi - 1;
			StackPush(&st, pointer);
		}
	}
	//销毁栈
	StackDestroy(&st);
}
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

注意：

• 第一组坐标必须先入进去，栈才有得操作
• 在求得key值下标的同时就进行了一趟排序
• 压栈时必须先压左边子数组的左右下标，再压右边子数组的左右下标才符合递归的过程。

篇幅有限，排序算法先讲解这么几种，后序会继续给大家讲解其他几种排序算法。