【数据结构第四讲（排序算法）】我不信教不会你

大家好啊✨
先简单介绍一下自己💎
本人目前大二在读，专业是计算机科学与技术。
写博客的目的是督促自己记好每一章节的笔记，同时也希望结交更多同仁，大家互相监督，一起进步！☀️

👀在这篇博客中，将会进行七种（直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序）排序算法的讲解。
👀过程中包括基本概念、代码实现、动图演示，还会有OJ题来帮助大家更好地理解。
👀我的宗旨就是将所有知识点一网打尽🔥🔥🔥
👀内容有点多，大家一定要耐心看完。切记，学习如逆水行舟，不进则退.在学习的路上一定要坚持！坚持！再坚持！
如果大家看完觉得有所收获，不妨关注点赞收藏方便以后回顾，也当做给博主的小小鼓励了~❤️

一、🔭排序的概念及其运用

1.1💻排序概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中， r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中， r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2💻排序运用

排序在我们的生活中可谓是无处不在
就连我们的父母也总是拿我们的成绩去跟比人家的孩子比😤
下面是两个生活中的排序例子：

1.3💻常见的排序算法

在上面，我们看到了几种排序例子，那么他们是按照什么规律，或者说是什么套路排序的呢？
在本篇文章中，我们重点介绍七种常见的排序算法！

二、🔭常见排序算法的实现

2.1💻插入排序

2.1.1💻基本思想

直接插入排序是一种简单的插入排序，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想

每拿到一张牌，就将它们变成有序，拿到下一张牌后，就将其与前面的每一张牌比较，再将其插入其中，使它们有序。

2.1.2💻直接插入排序

直接插入排序说白了就是在几个有序的数字中间插入一个数，使它们仍然保持有序，再接着插入下一个数，以此类推。当插入最后一个数之后，整个数组也就是有序的了。
下面来看个例子：👇👇👇

当插入第i(i>=1 )个元素时，前面的array[0],array[1 ],…,array[i-1 ]已经排好序，此时用array[i]的排
序码与array[i-1 ],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移 。

下面再用一个动图帮助大家理解：

下面我们先来看直接插入排序的单趟排序的实现：

void InsertSort(int* a, int n)
{//a为给定待排序整形数组的首元素地址
	//假设[0,end]有序
	int end;
	int tmp = a[end + 1];
	while (end >= 0)
	{
		if (a[end] > tmp)
		{
			a[end + 1] = a[end];
			end--;
		}
		else
		{
			//考虑到end减到-1的情况，都将tmp插在end后面，故直接break
			break;
		}
	}
	a[end + 1] = tmp;
}

下面对以上代码的几个重点进行说明：
①由于插入时，需要将前面的元素依次向后挪动，所以要用一个tmp变量将插入的值保存起来，避免被覆盖。
②上述循环结束有两种情况（当待插入值与前面区间的元素比较过程中，前面和后面元素分别比自己小、比自己大时，循环就结束，例如上面动图的27）
（当所有元素都比较完，end变为-1时，则需要将所有元素后移，再将插入值放在下表为0的位置上，入上面动图中的2）
既然这两种情况都表示循环结束，我们不妨在出现第一种情况时直接终止循环，然后在循环外面插入待插入值，这种做法符合上述两种情况。

下面再来看全趟排序的代码（其实大家应该都想到了，就是加一层循环的事）

void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)//注意最后end只需到n-2的位置
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				//考虑到end减到-1的情况，都将tmp插在end后面，故直接break
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void TestInsertSort()
{
	int a[] = { 3,2,5,4,7,9,8,1,6,0 };
	InsertSort(a, sizeof(a) / sizeof(int));
	Print(a, sizeof(a) / sizeof(int));
}
int main()
{
	TestInsertSort();
	return 0;
}

注意上面代码中的end是指倒数第二个元素，故循环结束条件为"i<n-1"。

运行结果如下：

那么直接插入排序的时间复杂度是多少呢？

给定数组是逆序为最坏情况，时间复杂度为O(N^2)，给定数组为顺序为最好情况，时间复杂度为O(N)（每次比较都只需比较一次即可）。

直接插入排序的特性总结：
1 . 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度： O(N^2)
3. 空间复杂度： O(1 )，它是一种稳定的排序算法
4. 稳定性：稳定

2.1.3💻希尔排序（缩小增量排序）

上面的直接插入排序挺简单的，但是希尔排序就没有那么简单了，但也不要担心，相信博主，相信自己，不成问题！💥

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

希尔排序分为两个步骤：
①先进行预排序，使数组接近有序（例如3 5 1 6 8 9 2 7 4 0被预排序为0 1 2 3 4 7 6 5 8 9 ）
②再进行直接插入排序，使其完全有序。

有很多人不理解为什么要这样，其实预排序可以很大程度地降低时间复杂度，后面会让大家有更直观的感受😇
那么到底怎么进行预排序呢？

先选定一个数字间隔gap，然后每隔gap个间隔的数据为一组，对每一组进行直接插入排序，之后再重新分组，直至数组完全有序。

这样做的目的是让大的数更快地移动到后面，让小的数更快地移动到前面。
并且可见gap越大，预排序结束之后越不接近有序，gap越小，越接近有序。当gap为1时，就是直接插入排序。
下面是一趟希尔排序的代码：

void ShellSort(int* a, int n)
{
	int gap;
	int end;
	int tmp = a[end + gap];
	while (end >= 0)
	{
		if (a[end] > tmp)
		{
			a[end + gap] = a[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	a[end + gap] = tmp;
}

其实说白了就是把直接插入排序里的a[end+1]改成a[end+gap]，其实是不难理解的。

下面我们来思考一个问题，gap到底取什么值合适呢❓❓❓
关于gap的取值，要注意以下两个点：
①gap不能是定值，因为数组的长度不是固定的，可能非常小也可能非常大，所以gap的取值一定是根数组长度相关的，并且每次排序都会发生变化。
②gap最后一次一定是1，这样才能保证数据最后是完全有序的。

所以我们不妨用循环来改变gap的值，下面是全趟希尔排序的代码：

void ShellSort(int* a, int n)
{
	int gap = n;
	//把间隔为gap的多组数据同时排
	while (gap > 1)
	{
		gap = gap / 3 + 1;//lon3n
		for (int i = 0; i < n - gap; i++)
		{
			//gap很大时，O(N),很小时，已经接近有序了，O(N)
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

这里还需要说明一下，有些人认为循环内gap的变化应该是gap=gap/2，但有一些人认为应该除3，只需要在后面+1保证gap最后为1就行。

希尔排序的时间复杂度为O(N*logN)，如果采用gap除2的方式，那么logN就是以2为底的，如果是除3，就是以3为底。

还需要知道一点，希尔排序并没有确定的时间复杂度，上面给出的结论只是大致估算的结果。

那可能还会有小伙伴认为，希尔排序要排那么多次，怎么保证它比直接插入排序效率更高呢？

大家不要慌，当然有办法证明了！
先给大家看一段用于测试不同排序算法效率的代码：👇👇👇

void TestOP()
{
	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];
	}
	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(a6, N);
	int end7 = clock();

	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);
}

可能大家不知道上面这段代码是什么意思，其实就是计算每一个算法执行的时间，当执行以上程序的时候，就会很直观地看到每种算法的效率差别。
下面我们就执行一下，看一看直接插入排序和希尔排序的效率区别（这里我先手动屏蔽无关代码，并且保证两个算法的测试用例相同，大小都为十万个数据，就不放出来给大家看了，直接上运行截图）

可见差距之大啊！并且数据越多，差距就会越明显！

希尔排序的特性总结：
1 . 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计.
4. 稳定性：不稳定

2.2💻选择排序

2.2.1💻基本思想

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

2.2.2💻直接选择排序

在元素集合array[i]–array[n-1 ]中选择关键码最大(小)的数据元素。
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换。
在剩余的array[i]–array[n-2]（array[i+1 ]–array[n-1 ]）集合中，重复上述步骤，直到集合剩余1个元素

直接选择排序比较简单，我们直接上代码：

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int mini = begin;
		int maxi = end;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[mini])
				mini = i;
			if (a[i] > a[maxi])
				maxi = i;
		}
		Swap(&a[begin], &a[mini]);
		//如果begin和maxi重叠，则需要调整位置
		if (begin == maxi)
			maxi = mini;
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;
	}
}

但是要注意极值与边界重合的情况，上面的代码中已经标记过了，这里就不再赘述了。

另外，直接选择排序是一个很差的排序，它的效率甚至比直接插入排序低很多，而且就算是有序的情况，时间复杂度仍为O(N^2)
我们直接来比一下，还是上面那段比较效率的代码，还是十万个数据：

还真是不比不知道，一比吓一跳啊！

直接选择排序的特性总结：
1 . 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度： O(N^2)
3. 空间复杂度： O(1 )
4. 稳定性：不稳定

2.2.3💻堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

堆排序主要借助二叉树的层序遍历（将每一层按照从左到右的顺序存储在一个数组中）以及向上或向下调整算法，将待排序数组构建成一个二叉树的样子，依次排序建（大或小）堆的排序算法。

如果要用堆排序，首先要进行的操作就是建堆（将待排序数组想象成一个大堆或小堆的结构）然后从根开始，将父亲和作业孩子中最大（或最小）的那个比较，孩子大于（或小于）父亲就交换，然后再向下比较调整。

但是能使用向上或向下调整的前提是根节点的左右子树是大堆或小堆，这就又需要进行向上或向下调整了，可是这不就变成死循环了吗？

稍安勿躁，稍后就为大家提供解决办法，我们现在先假设有一个满足左右孩子都是大堆的待排序数组，然后让我们用向下调整算法建一个大堆。

（下面的代码实现的爷是建大堆，其实两个堆代码的区别就是调整两个比较符号的区别，其他不变）

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;//默认是左孩子
	while (child < n)
	{
		//选出左右孩子中大的那一个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);//交换孩子和父亲
			parent = child;//调整下标，继续向下调整
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
	void HeapSort(int* a, int n)
{
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
}

运行截图如下：

接下来解决死循环的问题：

要保证左右子树都为大堆，我们不妨从数的尾部开始依次向上调整，这样就能保证每次调整的那棵树的左右子树都满足条件。
但是，没必要从叶子结点开始，因为叶子结点本来就是一个大堆（左右子树为空），所以只要从倒数第二层开始即可！

那么，再来思考一个问题，如果要完成升序排序，应该建小堆还是大堆呢❓❓❓
答案是升序建大堆，降序建小堆。
如果排升序建小堆，建完之后，第一个数据（堆顶数据）就是最小的那个，也就不用再动了，再往后调整剩下的就行。
但是，把第二个数据当做新的堆顶的时候，剩下的树的父子关系就全乱了，就不再满足左右子树都是小堆的条件了。所以升序建大堆，降序反之。

那么，建完大堆之后怎么办呢？
答案是将最后一个数据与堆顶数据交换，然后将除最后一个数据之外的所有数据重新向下调整，直至完全升序。

代码如下：

void HeapSort(int* a, int n)
{
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

运行结果如下：

那么建堆的时间复杂度是多少呢？

堆排序的特性总结：
1 . 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(1 )
4. 稳定性：不稳定

2.3💻交换排序

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

2.3.1💻冒泡排序

冒泡排序大家应该都很熟悉了，这里就说的简单一点。


原始的冒泡排序代码：

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; i < n - i - 1; j++)
		{
			if (a[j + 1] < a[j])
			{
				Swap(&a[j + 1], &a[j]);
				exchange = 1;
			}
		}
	}
}

但是这样的代码有一个弊端，当数据本来就是有序的时候，它仍会一个一个地比较，这样就白白浪费了时间，所以我们应该判断一下数据是否有序，若有序，就终止比较。
最终代码：

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;
		for (int j = 0; i < n - i - 1; j++)
		{
			if (a[j + 1] < a[j])
			{
				Swap(&a[j + 1], &a[j]);
				exchange = 1;
			}
		}
		if (!exchange)
			break;
	}
}

冒泡排序的特性总结：
1 . 冒泡排序是一种非常容易理解的排序
2. 时间复杂度： O(N^2)
3. 空间复杂度： O(1 )
4. 稳定性：稳定

2.3.2💻快速排序

2.3.2.1💻挖坑法

快速排序是Hoare于1 962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

下面来看第一次分割的动态图：

上面的过程就是先选定左边的6为基准值，然后两个指针分别在两边开始往中间挪动。如果右边的找到比6小的数，就将其放在基准值的坑位，然后自己形成一个新的坑位，而左边则找比6大的数。当两个指针相遇时，就将6放在相遇的位置。
此时，6左边的数字全比6小，右边的全比6大，而在后续的排序中，6就不用再挪动了，因为它已经在正确位置了。

接下来来看代码实现：

void QuickSort1(int* a, int n)
{
	int right = 0;
	int left = n - 1;
	int begin = left;
	int end = right;
	int pivot = begin;
	int key = a[pivot];
	while (begin < end)
	{
		//右边找小，放在左边，自己形成新的坑位
		while (begin < end && a[end] >= key)//保证两个指针不能错过，相遇即停下来
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;
		//左边找大，放在右边
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;
}

上面只是一趟排序的代码，那我们怎么将剩下的也变成有序呢❓❓❓
答案是：分治递归，分别再对6左右两边的数字进行上述重复操作，直至整体有序（两边的区间均只剩一个值）。

void QuickSort(int* a, int left, int right)
{
	if(left>=right)
		return;
	int begin = left;
	int end = right;
	int pivot = begin;
	int key = a[pivot];
	while (begin < end)
	{
		//右边找小，放在左边，自己形成新的坑位
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;
		//左边找大，放在右边
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;
	QuickSort(a,left,pivot-1);
	QuickSort(a,pivot+1,right);
}

void TestQuickSort()
{
	int a[] = { 3,2,5,4,7,9,8,1,6,0 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	Print(a, sizeof(a) / sizeof(int));
}

运行结果如下：

2.3.2.2💻左右指针法

左右指针法和挖坑法本质是一样的，但是它还是有一点小小的变形的，一起来看看吧！

跟挖坑法不同的是，这里的两个指针同时向中间挪动，当两边都找到目标值（左边找到大的数，右边找到小的数）时，将这两个数交换，再接着找下一组可以交换的数，相遇时，就将其与基准值，若比基准值小，就交换。

直接看代码：

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	int keyi = begin;
	while (begin < end)
	{
		while (begin < end && a[begin] <= a[keyi])
			begin++;
		while (begin < end && a[end] >= a[keyi])
			end--;
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[keyi]);
}

2.3.2.3💻前后指针版本

前后指针顾名思义就是定义一个在前，一个在后的指针，前面的指针依次向前走，若指到的值小于基准值，则后一个指针也向前走，若大于基准值，则后面的指针不动，当前面的指针再次指向小于基准值的数时，就将两个指针指向的数字交换，再分别向前走。

来看代码：

void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
		return;
	int keyi = left;
	int prev = left, cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			Swap(&a[cur], &a[prev]);
			prev++;
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
}

2.3.2.4💻快速排序优化

那么，快排的时间复杂度是多少呢？->O(N*logN)
最坏情况是有序的情况，这样即使不用排，但依然会遍历每一个数，其次调用递归将其分为两个区间，粗略计算就是logN次，像二叉树一样。

那该怎么对最坏情况进行优化呢？
说明：这里只用第一种快排为例，其他的两种方法是一样的。

我们可以用一个三数取中的方法，在每一个区间里，选出一个不是最大也不是最小的数，将它与边界值对换，这样就不会出现最坏情况了。

//针对最坏情况优化：三数取中
int GetMid(int* a, int left, int right)
{
	int mid = (left + right) >> 1;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left] > a[right])
			return left;
		else
			return right;
	}
	else//a[left] >= a[mid]
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] < a[right])
			return left;
		else
			return right;
	}
}
void QuickSort(int* a, int left, int right)
{
	if(left>=right)
		return;
	int index = GetMid(a, left, right);
	Swap(&a[left], &a[index]);
	int begin = left;
	int end = right;
	int pivot = begin;
	int key = a[pivot];
	while (begin < end)
	{
		//右边找小，放在左边，自己形成新的坑位
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;
		//左边找大，放在右边
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;
	QuickSort(a,left,pivot-1);
	QuickSort(a,pivot+1,right);
}

那还能不能再进一步优化呢？😕
大家思考一下，当递归进行到一定程度（剩下的子区间很小）时，还有没有必要继续进行递归呢？
其实是没必要的，因为递归效率并不高，所以我们不妨考虑当快排快要结束时，调用一种其他的排序方式，将剩下的小部分未排序好的区间排好。

那选哪种排序方式来进行小区间优化呢？当然是希尔排序当仁不让啊，它无非是效率最高的。

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
		return;
	int index = GetMid(a, left, right);
	Swap(&a[left], &a[index]);
	int begin = left;
	int end = right;
	int pivot = begin;
	int key = a[pivot];
	while (begin < end)
	{
		//右边找小，放在左边，自己形成新的坑位
		while (begin < end && a[end] >= key)//前面的条件调试得出
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;
		//左边找大，放在右边
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;
	if (pivot - 1 - left > 10)//小区间优化
		QuickSort1(a, left, pivot - 1);
	else
		InsertSort(a + left, pivot - 1 - left + 1);
	if (right - (pivot + 1) > 10)
		QuickSort1(a, pivot + 1, right);
	else
		InsertSort(a + pivot + 1, right - (pivot + 1) + 1);
}

关于这样到底优化了多少，小伙伴们也可以用上面给出的代码测一下优化前后程序执行所用的时间，就会发现…优化程度当然是非常大的了😄

快速排序的特性总结：
1 . 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度： O(N*logN)

2.4💻归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

说白了，归并算法分为两步
归----利用递归将待排序数组依次拆分，直至最后，这样的目的是保证每一个子序列都是有序的（拆成只有一个元素，当然是有序的了）
并----像LeetCode原题“合并两个有序数组”一样，依次将这些数组合并即可

补充：因为需要创建子数组，所以需要开辟n个额外的空间，最后再将这些数据拷贝回原数组，所以归并排序的空间复杂度为O(N)。
来看代码：

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left <= right)
		return;
	//子区间递归
	int mid = (right + left) / 2;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);
	//将两个有序区间合并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	//将数据拷贝回原数组
	for (int i = left; i <= right; i++)
	{
		a[i] = tmp[i];
	}
}

void MergeSort(int* a, int n)
{
	//开辟n个区间
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

void TestMergeSort()
{
	int a[] = { 3,2,5,4,7,9,8,1,6,0 };
	MergeSort(a, sizeof(a) / sizeof(int));
	Print(a, sizeof(a) / sizeof(int));
}

归并排序的特性总结：
1 . 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度： O(N*logN)
3. 空间复杂度： O(N)
4. 稳定性：稳定

三、🔭排序算法复杂度及稳定性分析

四、🔭总结

本篇博客主要介绍了七种排序方法，时间复杂度分析和每种排序的效率对比都在了。
不得不说，写这么一篇博客还是挺累的，朋友们看完如果感觉有收获的话，就点点赞和收藏给博主一点小鼓励吧！💖
博主也在学习中，如有不严谨之处，希望各位不吝指出，我们一起加油，一起进步！

文章来源地址https://www.toymoban.com/news/detail-675011.html

到了这里，关于【数据结构第四讲（排序算法）】我不信教不会你的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！