史上最详细的八大排序讲解（错过绝对后悔系列）建议先收藏再观看！—— 数据结构

😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️Take your time ! 😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️
💥个人主页：🔥🔥🔥🔥大魔王🔥🔥🔥🔥
💥所属专栏：🔥魔王的修炼之路–数据结构🔥
如果你觉得这篇文章对你有帮助，请在文章结尾处留下你的点赞👍和关注💖，支持一下博主。同时记得收藏✨这篇文章，方便以后重新阅读。

文章目录

• 前言
• 一、插入排序
• • 🚀直接插入排序
  • • 介绍
    • 实现
    • 直接插入排序特性总结
  • 🚀希尔排序
  • • 介绍
    • 代码
    • 希尔排序特性总结
    • 总结
• 二、选择排序
• • 🤩选择排序
  • • 介绍
    • 实现
    • 选择排序特性总结
  • 🤩堆排序
  • • 介绍
    • 实现
    • 堆排序特性总结
• 三、交换排序
• • ❄️冒泡排序
  • • 介绍
    • 实现
    • 冒泡排序特性总结
  • ❄️快速排序
  • • ☃️hoare版本
    • • 介绍
      • 实现
    • ☃️挖坑法
    • • 介绍
      • 实现
    • ☃️前后指针版本
    • • 介绍
      • 实现
    • ☃️快速排序非递归
    • • 介绍
      • 实现
    • ☃️快速排序优化
    • • 随机取key
      • 三数取中
      • 三路划分
      • 小区间优化
    • ☃️快速排序特性总结
• 四、归并排序
• • 😈归并排序递归
  • • 介绍
    • 实现
  • 😈归并排序非递归
  • • 介绍
    • 实现
  • 😈归并排序特性总结
• 五、比较排序总结
• 六、非比较排序
• • 介绍
  • 实现
  • 计数排序特性总结
• 七、总代码
• • Stack.h
  • Stack.c
  • Sort.h
  • Sort.c
  • test.c
• 总结

前言

对于初学者，我们最熟悉的排序应该就是冒泡排序了吧，这是每个初学者都要经历的当时的“难题”，我们可能也偶尔听说过快排，但并不清楚它的原理，但是因为生活中的各种需求，仅仅两个排序并不能适合所有情况，下面将讲解很具有实用价值的八大排序，建议先收藏哈，以免下次找不到。

• 在学习这些排序之前，我们需要先直到一个非常重要的思想，对于那些比较复杂的代码，如果不好控制，我们可以先写出单抗，也就是其中的一个普通情况，如果普通情况不好写，那就写一个比较容易写的特殊情况，然后再对其进行修改，改成我们要实现的代码。

一、插入排序

🚀直接插入排序

介绍

直接插入排序，顾名思义就是直接插入，从第二个数开始，依次往前找，找到合适的后，插入进去，然后排第三个数，依次排，排到最后，虽然它的时间复杂度是O(N^2)，但是是这个复杂度里比较好的，因为如果运气好的话，很快就遇到比自己大的数，那么合适的位置就找到了，再前面的那些数就不用比较了。

实现

//直接插入排序
void InsertSort(int* arr, int n)
{
	int end = 0;
	for (end = 0; end < n - 1; end++)
	{
		int end_ = end;
		int tmp = arr[end_ + 1];
		while (end_ >= 0)
		{
			if (arr[end_] > tmp)
			{
				arr[end_ + 1] = arr[end_];
				--end_;
			}
			else
			{
				break;
			}
		}
		arr[++end_] = tmp;
	}
}

🚀直接插入排序思想：每次挨个比较，如果比自己大，就去数组的下一个位置，直到遇到比自己小的，然后放在比自己小的位置的后面就好了。注意交换有两种可能：一种是遇到了比自己小的，另一种是直到最小的数（下标为0）都比自己大，所以控制好这两种情况，别把第二种情况忽略然后越界了。

直接插入排序特性总结

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

🚀希尔排序

介绍

希尔排序是插入排序的优化版本，对于很多很多的数据，如果每次都要挨个往前比较大小，那么其实浪费了很多的时间，所以我们让他们先分成很大的组，也就是说每次每组的比较都跳了很多的数，然后逐渐缩小间隔，它们会逐渐有序，这些都叫做预排序，是为了在最后一次gap = 1，也就是直接插入排序时让数组接近有序，这样会省下很多的时间。

代码

希尔排序（四层循环）
//void ShellSort(int* arr,int n)
//{
//	int end = 0;
//	int gap = n;
//	while (gap >= 1)
//	{
//		gap /= 2;
//		int m = 0;
//		for (m = 0; m < gap; m++)//这里多的一层
//		{
//			for (end = m; end < n - gap; end += gap)
//			{
//				int end_ = end;
//				int tmp = arr[end_ + gap];
//				while (end_ >= 0)
//				{
//					if (arr[end_] > tmp)
//					{
//						arr[end_ + gap] = arr[end_];
//						end_ = end_ - gap;
//					}
//					else
//					{
//						break;
//					}
//				}
//				arr[end_ + gap] = tmp;
//			}
//		}
//	}
//}

//希尔排序（三层循环），与四层没差距，所以时间复杂度是看次数，而不是几层循环。
void ShellSort(int* arr, int n)
{
	int end = 0;
	int gap = n;
	while (gap >= 1)
	{
		//gap = (gap / 3)+1
		gap /= 2;
		int m = 0;
		for (end = m; end < n - gap; end++)
		{
			int end_ = end;
			int tmp = arr[end_ + gap];
			while (end_ >= 0)
			{
				if (arr[end_] > tmp)
				{
					arr[end_ + gap] = arr[end_];
					end_ = end_ - gap;
				}
				else
				{
					break;
				}
			}
			arr[end_ + gap] = tmp;
		}
	}
}

🚀希尔排序思想：当数据量过大时，为了提高直接插入排序的效率（防止每次都挨个比较），先设立gap间隔，gap从很大慢慢变到1（这时就是直接插入排序），这个过程中的排序称为预排序，使得应该交换位置但是相差很远的数只比较了少数次（跨度大）就能比较上，然后交换位置，然后不断这样子，每次gap减小时数组都更加接近有序，很好的优化了最后一次直接插入排序，使得最后一次的直接插入排序很少出现让一个数到达相应位置要比较很多次的情况。

实现中三层循环和四层循环的区别：
四层循环是把分成的这些组一组一组的比，比完这一组然后比下一组。
三层循环是直接不分了，每组都先比第一次，然后每组都再比第二次，注意跨度是一样的，因为它们还是只跟自己组里的比。

实现中三层循环和四层循环的时间复杂度比较：
时间复杂度是一样的，虽然循环的层数不一样，所以我们在分析时间复杂度时不要单纯的数有几个循环，我们要比较的是次数。

• gap:（除1和0）任何数/2最后都为1：gap/2；gap/3+1也可以。这两个是最常用的修改gap的方式。

希尔排序特性总结

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
   会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度：它及其不容易计算，因为我们在计算时间复杂度时是按照最坏情况来进行评定的，但是希尔排序每次循环让gap逐渐变为1的那些预排序又是在优化最后一次直接插入排序的数据，让它们尽可能比较的次数少，而且每次改变依次gap，数据都会优化一次，所以我们不能根据最坏情况(N^2)来评定希尔排序的时间复杂度，特别难推导，所以我们记着比较接近的就行了：接近N×logN（其实比N*logN大一点，大不是绝对的，是当数据量到达一定程度后才大的），但这不是确定的结果。最准确为O(N^1.3)。
4. 稳定性：不稳定

总结

1. 先进行一系列预排序，最后一次是直接插入排序。
2. 直接插入排序的优化，分为gap组，并且让gap不断缩小再次按照重新分成的组重新排，为最后一次的直接插入排序（弄一个gap不断缩小的循环，直到gap == 1执行后结束循环）省下了大量时间。
3. 两种希尔排序虽然差了一次循环，但是效率是一样了，所以看时间复杂度不能只数循环有几个来确定哪个更优，要比的是次数。
4. （除1和0）任何数/2最后都为1：gap/2；gap/3+1也可以。这两个是最常用的修改gap的方式。

二、选择排序

🤩选择排序

介绍

这是一个很垃圾的排序，不管怎样都是O(N^2)，因为它每次都是遍历一遍然后选出最小或最大放在最前面或者最后面，直到待排序数组排序完，不过由它升级出来的堆排序效率还可以，下面会说。

实现

单向选择排序：每次只记录最小或最大
//void SelectSort(int* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		int mini = i;
//		for (int j = i + 1; j < n; j++)
//		{
//			if (arr[mini] > arr[j])
//			{
//				mini = j;
//			}
//		}
//		int tmp = arr[mini];
//		arr[mini] = arr[i];
//		arr[i] = tmp;
//	}
//}

//双向选择排序：每次记录最小和最大（记得第二次在交换时要判断是否第一次把第二次要操作的下标的值给修改了，单向选择排序不会出现这种情况）
void SelectSort(int* arr, int n)
{
	int begini = 0;
	int endi = n - 1;

	while (begini < endi)
	{
		int maxi = begini;
		int mini = begini;

		for (int i = begini; i <= endi; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}

		Swap(&arr[begini++], &arr[mini]);
		if (maxi == begini - 1)
		{
			maxi = mini;
		}
		Swap(&arr[endi--], &arr[maxi]);
	}
}

🤩选择排序思想：就是每次都遍历一遍数组，记录最值下标，让他们与首下标的值进行交换，然后忽略已经是最值的下标（首下标），再进行下一次寻找，不断循环，直到有序。

单向和双向区别不大，就是一个二倍的关系，单向是每次选出最大或最小，双向是每次选出最大和最小，不影响最后的量级。

不过需要注意的是，双向的话需要考虑一种情况，如果一次选最大和最小两个，记得避免在选第二个最值时有没有因为第一个最值交换覆盖了求第二个最值时要用的数，需要进行额外处理。如果一次选一个最值就不会出现这种情况。

选择排序特性总结

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

🤩堆排序

介绍

选择排序太垃圾了，时间复杂度每次都是O(N^2)，不过进行升级后的堆排序时间复杂度时O(N*logN)，挺不错的，不过用时都要先建堆，然后再排序。以前堆的博客有详细讲解。

实现

//堆排序->选择排序的优化

void Swap(int* a, int* b)
{
	int tmp = *b;
	*b = *a;
	*a = tmp;
}
//向下调整
void AdjustDown(int* arr, int cur_begin, int n)//这里接收的n就是元素个数
{
	int parent = cur_begin; //不是下标，要减一

	while (parent < n)
	{
		int child = (parent * 2) + 1;

		if (child >= n)//防止越界
			break;

		if (parent * 2 + 2 < n)
		{
			if (arr[child + 1] > arr[child])
			{
				child += 1;
			}
		}
		if (arr[parent] > arr[child])
			break;
		Swap(&arr[parent], &arr[child]);
		parent = child;
	}
}

//升序 -> 建大堆
void HeapSort(int* arr, int n)//n个元素
{
	int begin = (n - 1) / 2;
	for (int cur_begin = begin; cur_begin >= 0; cur_begin--)//建大堆
	{
		AdjustDown(arr, cur_begin, n);//传的第n个，记得用时减一
	}

	//开始堆排序
	int end = n - 1;
	while (end > 0)
	{
		//Swap(&arr[0], &arr[end--]);
		//AdjustDown(arr, 0, end);//end在接收时代表的是n个元素，不是下标，所以这一点错了，没有对应好。
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end--);
	}
}

🤩堆排序思想：首先通过建堆满足堆结构（大根堆、小根堆），之后通过每次最值数与最后一个数交换，那么就能找到一个最值数，然后忽略这个最值数，先进行向下调整找出新的最值数，然后再通过同样的方法来不断循环，直到最后一个数。

排升序建大堆：这样可以避免父子乱辈，不然每次操作都要重新建一次堆（因为相反的建堆方式会破坏堆结构，而我们的操作比如向上向下调整都是需要是堆结构才能进行的）。
建堆：向上调整建堆时间复杂度为O(N*logN)，向下调整建堆时间复杂度为O(N)。
堆排序时的时间复杂度为O（N*logN）,虽然堆排序用的是向下调整，但其实是和建堆时的向上调整的情况很像的（多的要比较的高度高，少的比较的高度少）。

堆排序特性总结

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

三、交换排序

❄️冒泡排序

介绍

冒泡排序没太大使用价值，主要是教学价值，毕竟初学时冒泡排序可是能难倒一堆大学生哈哈哈。

实现

冒泡排序
//void BubbleSort(int* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < n - i - 1; j++)
//		{
//			if (arr[j] > arr[j + 1])
//				Swap(&arr[j], &arr[j + 1]);
//		}
//	}
//}

//冒泡排序(升级版，如果最内层循环一次都不交换，则表明有序了，则外层循环就不用继续了)
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int flag = 1;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				flag = 0;
			}
		}
		if (flag)
		{
			//printf("我跳出了哈！\n");
			break;
		}
	}
}

❄️冒泡排序思想：就像它的命名一样，不断向上冒，最上面的最大。它属于交换排序是因为它每次从第一个下标元素开始比较，如果大就和下一个交换，然后继续让第二个下标和第三个下标比，不断循环，比到最后，那么最后的下标就是最大的，然后忽略掉这个最大的，继续从第一个下标开始比较，不断循环。

对于优化的冒泡排序，实际上就是当一整个循环都不进行交换的话，说明就已经有序了，因为这种情况的话就意味着下标0比1小，1比2小等等，那么0当然也就比2小，依次类推，说明它们就有序了。下标这时候就没必要再进行之后数据的比较了，直接break就行了。

冒泡排序特性总结

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

❄️快速排序

• 快排思想

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

分割方法：左边做key，右边先走；右边做key，左边先走（至于原因，自己证一下就出来了，很简单，两个情况：左边遇到右边，右边遇到左边）。举例来说假如左边做key，右边先走：右边找到比key小的数，然后左边开始走，找到比key大的数，然后交换，直到左边等于右边，这时候交换左右边相遇位置与key的值，那么key左边的数就会都小于key，key右边的数都会大于key，那么key的位置就确定了，然后再对分成的两个子序列开始同样的操作，不断循环（这个是hoare版本，其他版本同样思想，只是实现方法不一样）。

快速排序是非常实用的排序手法，它分为三个版本：hoare版本、挖坑法、前后指针版本。它们的思想是一样的，不过实现上有一点区别。

快速排序也有许多优化方法。比如：随机取key、三数取中、小区间优化、三路划分（目前没学，等有空学了补上）。除了三路划分，其他的优化方法下面都会讲到。

☃️hoare版本

介绍

这个是最早出现的版本，是hoare（霍尔）大佬发明出来的，之后的两种方式是在它的基础上进行的改善。

实现

//快排->hoare版本
//左边做key，右边先走
void PartSort1(int* arr, int left, int right)
{
	小区间优化
	//if (right - left <= 10)
	//{
	//	InsertSort(arr + left, right - left + 1);
	//	return;
	//}
	
	if (left >= right)
		return;
	
	int begin = left;
	int end = right;

	//随机选key
	//int randi = rand() % (right - left) + left;
	//Swap(&arr[randi], &arr[begin]);
	
	//三数取中
	int mid_i = GetMidNumi(arr, left, right);
	Swap(&arr[mid_i], &arr[begin]);

	int key = arr[begin];
	while (left < right)//不能取等，因为：括号里的是进去的条件，我们最好要找到的是left与right相遇的位置再和keyi的数据交换，从而确定keyi的位置。下面内部循环的两个也是这样。
	{
		while (left < right)//右边找小
		{
			if (arr[right] < key)遇到与key相等的就跳过，不用管，因为相等的话换不换位不影响结果，但是可能出现死循环，如果修改了死循环，
								那么就会出现另一个不可避免地问题，下面是假设遇到key相等的要交换不跳过的情况：
								
							   问题如下
							  /1.keyi也就是key的下标的位置元素是在最后left与right相等时交换的，但如果遇到不跳过就会提前交换了。
							 2.两边都遇到key的话，break，Swap，然后继续进去无限循环。
							 
							解决方法
						    1.对于1的问题，我们需要首先让第二层循环开始前++left就行了，这样就跳过了keyi的位置。
						   2.对于2的问题可以通过内层循环交换时只让right--，不动left来实现消除死循环(不能动left，因为可能left这次的整个循环都不需要动，但是你却给++了，不过right能动是因为right
						 肯定会--，因为交换完再次进入循环是右边right先走的，不再--的话只有一种情况就是它们Swap时已经相等了，那样的话就不会进入循环了，不会再操作right，所以把right--不影响)。
						 
						解决方法的问题
					   1.不能首先跳过自己，因为这样的话就会出现新的问题：如果key合适的位置就应该在0下标，但是我们直接让left++，那么它最小也只会在1下标，这样就错误了。
					  2.第二条的解决方法没有问题，按照那样的操作就把死循环避免了，但是第一条的问题是避免不了的。所以我们只能当数值等于key时跳过，而不是进行交换。
				break;
			right--;
		}
		while (left < right)左边找大
		{
			if (arr[left] > key)
				break;
			left++;
		}
		Swap(&arr[left], &arr[right]);交换
	}
	int keyi = left;
	Swap(&arr[begin], &arr[keyi]);
	//return keyi;
	PartSort1(arr, begin, keyi - 1);
	PartSort1(arr, keyi + 1, end);
}

☃️hoare版本思想：左边做key，右边先走，右边找小，左边找大，然后交换，不断循环，直到左边等于右边，这时让左右相遇的下标元素与key(也就是第一个下标元素)交换位置，那么key的值就到了合适的下标，并且将剩下的分成了两个子序列，这些子序列不断重复该操作，直到初始时left大于等于right，然后证明该子序列结束。

提出问题
遇到与key相等的就跳过，不用管，因为相等的话换不换位不影响结果，但是可能出现死循环，如果修改了死循环，那么就会出现另一个不可避免地问题，下面是假设遇到key相等的要交换不跳过的情况：

错误如下
1.keyi也就是key的下标的位置元素是在最后left与right相等时交换的，但如果遇到不跳过就会提前交换了。
2.两边都遇到key的话，break，Swap，然后继续进去无限循环。

解决方法
1.对于1的问题，我们需要首先让第二层循环开始前++left就行了，这样就跳过了keyi的位置。
2.对于2的问题可以通过内层循环交换时只让right–，不动left来实现消除死循环(不能动left，因为可能left这次的整个循环都不需要动，但是你却给++了，不过right能动是因为right肯定会–，因为交换完再次进入循环是右边right先走的，不再–的话只有一种情况就是它们Swap时已经相等了，那样的话就不会进入循环了，不会再操作right，所以把right–不影响)。

解决方法的问题
1.不能首先跳过自己，因为这样的话就会出现新的问题：如果key合适的位置就应该在0下标，但是我们直接让left++，那么它最小也只会在1下标，这样就错误了。
2.第二条的解决方法没有问题，按照那样的操作就把死循环避免了，但是第一条的问题是避免不了的。所以我们只能当数值等于key时跳过，而不是进行交换。

☃️挖坑法

介绍

挖坑法就像它的名字一样，只是hoare的实现改版，思想是一样的，具体思想在代码实现的下面会说。

实现

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

void PartSort2(int* arr, int left, int right)
{
	小区间优化
	//if (right - left <= 10)
	//{
	//	InsertSort(arr + left, right - left + 1);
	//	return;
	//}

	if (left >= right)
		return;
	int begin = left;
	int end = right;

	随机选key
	//int randi = rand() % (right - left) + left;
	//Swap(&arr[randi], &arr[begin]);

	//三数取中
	int mid_i = GetMidNumi(arr, left, right);
	Swap(&arr[mid_i], &arr[begin]);

	int key = arr[begin];
	int hole = left;
	while (left < right)
	{
		while (left < right)
		{
			if (arr[right] < key)
			{
				arr[hole] = arr[right];
				hole = right;
				break;
			}
			right--;
		}
		while (left < right)
		{
			if (arr[left] > key)
			{
				arr[hole] = arr[left];
				hole = left;
				break;
			}
			left++;
		}
	}
	arr[hole] = key;
	int keyi = left;
	//return keyi;
	PartSort2(arr, begin, keyi - 1);
	PartSort2(arr, keyi + 1, end);
}

☃️挖坑法思想：还是遵循左边做key，右边先走的规则。首先让key用临时变量存起来，让它的下标标记为hole(坑)，然后开始操作：右边先找小，找到后放在坑位，然后坑位变成右边交换的这个数的，然后左边开始找大，一直重复，直到左右相遇（或者说左右有一方等于坑位），这时候让我们用临时数组存的key放入坑位即可，这是一次单抗，不断循环，让其子序列也都这样进行。

☃️前后指针版本

介绍

前后指针版本就是用两个指针同时从起始处开始操作，直到数组结束，具体思想代码实现下边会讲。

实现

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

//前后指针法
//左边做key，右边先走
void PartSort3(int* arr, int left, int right)
{
	小区间优化
	//if (right - left <= 10)
	//{
	//	InsertSort(arr + left, right - left + 1);
	//	return;
	//}

	if (left >= right)
		return;

	int begin = left;
	int end = right;

	随机选key
	//int randi = rand() % (right - left) + left;
	//Swap(&arr[randi], &arr[begin]);

	//三数取中
	int mid_i = GetMidNumi(arr, left, right);
	Swap(&arr[mid_i], &arr[begin]);

	int key = arr[begin];
	
	int pre = begin + 1;
	int cur = begin + 1;
	while (cur <= right)
	{
		if (arr[cur] < key)
		{
			Swap(&arr[pre++], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[begin], &arr[--pre]);
	
	int keyi = pre;
	//return keyi;
	PartSort3(arr, left, pre - 1);
	PartSort3(arr, pre + 1, right);
}

☃️前后指针版本思想：前后指针的思想就是pre(previous)，cur(current)，它们从keyi的下一个位置开始走，如果cur下标元素小于key，就让cur与pre元素值交换，然后他们两个都++，如果cur指向的元素大于key，那么就只让cur++，一直循环，直到cur>right结束，这个时候让key与pre指向元素交换，则pre左侧都是比它小的，右侧都是比它大的。这样key就到了相应的位置了。然后对子序列不断重复即可。

☃️快速排序非递归

介绍

上面三种快排版本都是递归实现，然而如果数据过多或者不理想，会导致递归层次太深，就会出现栈溢出现象，这时就需要我们改成非递归来实现了。

• 递归问题：1. 效率（现阶段这个不是主要问题） 2. 递归层次太深，栈溢出（现阶段的编译器主要问题）

实现

Stack.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int STDateType;

typedef struct Stack
{
	STDateType* a;
	int top;//如果初始化为0，可以理解为元素个数（也就是栈顶元素下标+1），如果初始化为-1，可以理解为栈顶元素的下标
	int capacity;
}ST;

//初始化和最后销毁
void STInit(ST* ps);
void STDestory(ST* ps);

//入栈
void STPush(ST* ps, STDateType x);

//出栈
void STPop(ST* ps);

//元素个数
int STSize(ST* ps);

//判断是否为空
bool STEmpty(ST* ps);

//栈顶元素
STDateType STTop(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"

//初始化和最后销毁
void STInit(ST* ps)
{
	assert(ps);
	//ps->a = malloc(sizeof(ST) * 5);  1.没有强转
	ps->a = (STDateType*)malloc(sizeof(ST) * 5);
	2.开辟新空间后没有检查
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->top = 0;
	ps->capacity = 5;
}
void STDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->capacity = 0;
	ps->a = NULL;
	1.没有让top也就是栈顶位置重置。
	ps->top = 0;
	//最后在Test.c上让结构体指针指向空。
}

//入栈
void STPush(ST* ps, STDateType x)
{
	assert(ps);
	//if (ps->top == ps->capacity)
	//{
	//	ST* str = realloc(ps->a, ps->capacity * sizeof(ST) * 2);
	//	if (str == NULL)
	//	{
	//		perror("realloc fail");
	//		return;
	//	}
	//}  
	1.没有把扩容的时候创建的新指针赋给原指针
	if (ps->top == ps->capacity) //判断是否满了
	{
		//ST* temp = realloc(ps->a, ps->capacity * sizeof(ST) * 2);
		//2.指针应该指向数据的类型的地址，而且realloc也没强转为数据类型的指针
		STDateType* temp = (STDateType*)realloc(ps->a, ps->capacity * sizeof(ST) * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}
		else
		{
			ps->a = temp;
			3.忘记让结构体内的容量*2
			ps->capacity *= 2;
			temp = NULL;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

//出栈
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

//元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

//判断是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//栈顶元素
STDateType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}

QuickSortNonR

//层序遍历用的是队列
//前序遍历用的是栈：根左右
//快排非递归->第一次先压栈，然后后面开始判断，如果栈不为空，就压入四个值：两次的左右
void QuickSortNonR(int* arr, int left, int right)
{
	ST stack;
	STInit(&stack);
	
	STPush(&stack, left);
	STPush(&stack, right);

	while (!STEmpty(&stack))
	{
		int right = STTop(&stack);
		STPop(&stack);
		int left = STTop(&stack);
		STPop(&stack);

		if (left >= right)
			continue;

		int keyi = PartSort1(arr, left, right);

		//小区间优化
		if (right - left <= 10)
		{
			InsertSort(arr + left, right - left + 1);
			continue;
		}

		//先压右边再压左边，因为栈是后进先出。
		STPush(&stack, keyi + 1);
		STPush(&stack, right);
			
		STPush(&stack, left);
		STPush(&stack, keyi - 1);
	}
}

☃️非递归快排思想：它的思路还是快排的思路，只不过是实现方式发生了变化，因为不能用递归了，我们仔细看快排递归的实现，我们会发现它类似一个前序遍历（跟左右），先弄完自己这一块然后分别调用左侧和右侧，一直这样，既然是前序，那么我们就可以调用栈（栈可以模拟前中后序的遍历，也就是通过调用栈可以用非递归的方式完成前中后序递归的实现，层序遍历的话需要用到队列来模拟非递归实现），每排完一次就把这一组范围弹出，然后把新得到的左右子序列压入（注意是后进先出的顺序）（注意我们是压得范围，要包含左右两端的下标），不断循环，直到队列为空停止，此时已经排完了。

☃️快速排序优化

快排优化分别为：随机取key、三路取中、三路划分（目前不写，等有空学了补上）、小区间优化。

随机取key

虽然本来数组就是随机的，我们每次取的该序列的第一个元素就是随机值，但是如果我们排的这个序列接近有序（顺序或逆序），那么它的时间复杂度就会接近O(N^2)，所以为了避免这种情况，出了一个叫随机取key的方法，它的思想就是每次选第一个元素作为key之前，先找一个随机数作为下标，然后让这个随机数下标的元素与第一个下标的元素换位，然后我们再让第一个元素（换之前的随机数下标的元素）作为key。

	//随机选key
	int randi = rand() % (right - left) + left;
	Swap(&arr[randi], &arr[begin]);
	int key = arr[begin];

三数取中

于随机取key，其实并没有很好的优化，因为本来我们取的key都具有随机性，它只能很好的优化那些接近有序的序列，这个三数取中会达到更好的效果，因为我们快排中选取的key要让它尽量接近中间值，这样就能尽最大程度二分，提高效率。三数取中的思想是让这个序列的第一个元素与中间的元素和最后一个元素比较，找出中间值的下标，然后让它与第一个元素交换位置，然后我们把第一个元素作为key。

//三数取中
int GetMidNumi(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] > arr[right])
	{
		if (arr[left] < arr[mid])
			return left;
		else if (arr[right] > arr[mid])
			return right;
		return mid;
	}
	else //arr[right] > arr[left]
	{
		if (arr[right] < arr[mid])
			return right;
		else if (arr[left] > arr[mid])
			return left;
		return mid;
	}
}

三路划分

• 快排的三路划分：它是用来解决有大量重复数据的情况的（如果不处理，就会是很坏的情况，假如一组数据全是重复的，那么对这组数据排序时间复杂度就会变成O(N^2)，因为它相当于有序），不过加上这个思想的话也是有性能损失的，C的qsort（快排思想），不知道使用没，但C++库里没用。

小区间优化

假如我们是很理想的情况，也就是一直近似二分，那么我们可以想一下，最后几层的递归次数就占了整个递归次数的大部分，但是最后的几层每个序列也就只有几个元素，没有再一直递归的必要，所以为了提高一点效率，我们可以当子序列数值在几个的时候，我们直接让这几个数调用直接插入排序，这样这些就直接有序了，不用再一直递归下去。至于为什么是调用直接插入排序：选择排序就不用说了，太垃圾了，冒泡也不说了，也很垃圾，只有刚学编程时会作为教学意义来学习一下，希尔的话虽然是插入的优化，但是那是对于很多数时的优化，所以希尔也不适用，堆排序的话也不好，因为排序前还要建堆这些操作，没必要，影响效率，而且直接插入排序是时间复杂度中O(N^2)中比较好的，因为它每次遇到合适的位置就会停下了，可能不需要遍历很多数。

//直接插入排序
void InsertSort(int* arr, int n)
{
	int end = 0;
	for (end = 0; end < n - 1; end++)
	{
		int end_ = end;
		int tmp = arr[end_ + 1];
		while (end_ >= 0)
		{
			if (arr[end_] > tmp)
			{
				arr[end_ + 1] = arr[end_];
				--end_;
			}
			else
			{
				break;
			}
		}
		arr[++end_] = tmp;
	}
}
//小区间优化
if (right - left <= 10)
{
	InsertSort(arr + left, right - left + 1);
	return;
}

☃️快速排序特性总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN) 不用考虑最坏情况，因为我们通过快排优化的方式能够把最坏情况避免了。
   
3. 空间复杂度：O(logN) 原因：在每次递归都开辟了几个变量，如果正好一直二分的话那就是logN(高度个，忽略了系数，所以未logN)，如果不是一直二分会更多，最多也就是最坏情况为O(N)，但是我们不从最坏情况来评定，因为我们通过快排优化的方式能够把最坏情况避免了。
4. 稳定性：不稳定
   

• 快排情况的总结（上面很多都提到了）

快排：一般从两端中的一端（尽量是边界）开始选基准值进行快排。左边做key，右边先走，右边做key，左边先走，自己分情况证一证就知道了。

快排时间复杂度：为什么不按照最坏的（顺序和逆序这样）O(N^2)，因为这种坏情况可以避免（随机选key，三数取中）。所以快排时间复杂度：O(N*logN)。

优化快排：优化的原理是使key尽量接近中等大小的数值（便于二分更多次，减少递归层数）。快排最好用三数取中。因为给的数据本来就带有随机性，你再随机选数，其实只能优化那一小部分情况（比较有序），意义不大，所以三数取中比较好。

随机选key：通过生成一个随机数下标然后与keyi位置的数据交换。不太好，因为本来数据都是随机性的，这样，还是随机性的，唯一的好处是可以用在接近有序或者无序上会提高效率。

快排的优化：对于key的选择：随机取值、三数取中（比较推荐）。这两种都是在数组中另外的位置找到一个值来和我们选择的这块区间最左侧的数换值，所以换后我们还是选择的这块区间的最左侧的值作为key，不过实际key已经不是本来那个最左侧的值了。小区间优化：对于二叉树最后的几层，如果让它们还是递归，其实比较麻烦，比如仅仅比较10个数就要进行三四次递归，并且这些数目特别多，所以就算不是我们理想的二叉树逐渐二分，它们的数目还是很多很多，所以我们在最后只剩一小部分数时采用选择排序，而不是继续递归，可以提高一点效率。这个方法主要作用是提高效率（没提升很多），对于栈溢出没有起太大作用，因为最后几次每次栈开辟的很小，而且开辟完回归时会释放掉再给新开辟的地方用。为什么用插入排序：首先它优于选择排序（无论怎样都是N^2）和冒泡排序（只有教学意义），和希尔排序比较的话，因为数据量不大，所以此时用希尔也不会很好，堆排序（这么点数据还要建堆）还不如希尔，所以就不用说了。

递归改成非递归（不是想斐波那契数列那种一个循环就能解决的简单问题）：一般都需要借助栈或队列（只适用于广度）来完成，所以一般用栈来模拟（栈哪种情况都可以，但队列有的情况不行）。

四、归并排序

😈归并排序递归

介绍

要学习的最后一个内排序（它也是唯一的属于内排序又属于外排序）：归并排序。它主要就是让两个有序数组合并为一个有序数组，为了如果在数组内部直接改，会非常麻烦（因为归并排序用到的必须是两个有序数组，但是如果排的时候直接在原数组修改，那就把有序打乱了，就用不了归并了），所以我们选择开一个临时数组tmp，然后每次拷贝完我们都把这部分值覆盖到原数组相应位置。因为开辟的临时数组一个就够了，所以我们要写一个子函数，在子函数里进行递归，在主函数里开辟一个tmp的临时数组空间。

实现

//归并函数子函数
void _MergeSort(int* arr, int* tmp, int n, int begin, int end)//1.begin表示该段数组起始元素下标，不一定是0。
															 //2.end表示该段数组末尾元素下标，不一定是n - 1。
															
														    //3.tmp临时拷贝进去也是按照原数组中的那部分位置拷进去的，不是每次都从0开始。
														   //并不是必须这样，不过这样比较容易控制，因为我们传的参数都是按照原数组的下标进行操作的（这个只能按照原数组下标），
														  //所以我们还按照原来的位置进行赋值能直接使用这些下标，不然还要自己重新创建新的临时变量来控制在tmp中从0下标开始的赋值操作。
{
	
	
	
	if (begin >= end)						
		return;

	int mid = (end - begin + 1) / 2 + begin;//mid是下标   

	int begin1 = begin;
	int end1 = mid - 1;

	int begin2 = mid;
	int end2 = end;

	int tmpi = begin;

	if (begin1 > end1 || begin2 > end2)//这需要这一步，自己调了半天：如果没有的话，当出现这个情况，并没有返回，继续递归时传的值会变得再次符合函数最开始的循环条件，然后无限循环，栈溢出。
		return;						  //无语，这一点调试了一个小时，不能取等号，因为最后一层递归（两组：每组都是一个数值）时，也需要进行比较并且看是否换位。如果是等号的话，就直接return了，走不到下面的交换数值那一步。

	_MergeSort(arr, tmp, end1 - begin1 + 1, begin, end1);//向左
	_MergeSort(arr, tmp, end2 - begin2 + 1, begin2, end);//向右

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
			tmp[tmpi++] = arr[begin1++];
		else
			tmp[tmpi++] = arr[begin2++];
	}
	while (begin1 <= end1)
	{
		tmp[tmpi++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[tmpi++] = arr[begin2++];
	}
	memcpy(arr + begin, tmp + begin, sizeof(int) * n);//能不能不创建tmp临时数组，直接在原数组操作？ 
													 //不能，因为直接在原数组操作，我们会打破这两组数组的规律：它们本来各自是有序的，如果直接在原数组交换，就不再有序，
													//归并的思想就是让两个有序的数组合并成一个有序的数组，因此不能让它们的本质打破，不然很难控制。
	
												   //为什么每次递归都要把已经排好的这部分覆盖到原数组？
												  //因为每次比较是基于原数组的数据进行比较的，然后挪到tmp数组上，如果我们两两比完不立刻覆盖到原数组上，那么在下一次比较时，
												 //arr数组中的数据还是原本的无序，那么我们刚才那些递归意义何在，也不能直接在tmp里操作我们已经排好的有序数组，因为这就是又是上面提到的问题了。
}

//归并->对两组有序数组进行有序合并
void MergeSort(int* a, int n)
{
	int* tmp = malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc error");
		return;
	}
	_MergeSort(a, tmp, n, 0, n - 1);
	free(tmp);
}

😈归并排序思想：因为归并排序是对两个有序数组进行操作让他们合成一个有序的数组，所以我们操作的必须是有序的，那么就需要一直分，直到分成一个和一个，这两个数就可以看作两个有序的数组，然后回归，一 一归，二 二归，四四归一直回归到最初，整个数组就有序了。归并排序的分是每次都固定的在中间分，并不像快排那样分还要取决于key的大小。

😈归并排序非递归

介绍

当数据过多并且递归层次太深，编译器可能会出现出现栈溢出，所以我们也要学习一下把归并排序的递归改成非递归。

递归问题：1. 效率（现阶段这个不是主要问题） 2. 递归层次太深，栈溢出（现阶段的编译器主要问题）

实现

//归并非递归--一把梭哈（每次gap只覆盖一次）
void MergeSortNonR1(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc error");
		return;
	}

	int gap = 1;

	while (gap < n)
	{
		int begin1 = 0;
		int end1 = begin1 + gap - 1;

		int begin2 = begin1 + gap;
		int end2 = begin1 + 2 * gap - 1;

		int tmpi = begin1;

		while (begin1 < n)
		{
			//修正路线：因为我们采用的是一把梭哈（覆盖的是整个数组的大小），所以即使是不需要排序的部分我们也会再覆盖到arr上，因此不需要排序的部分也要先拷贝到tmp里。
			if (end1 >= n)
			{
				end1 = n - 1;

				begin2 = n;//让这两个变成错误的范围，到时候就不会进循环（因为这些数不是数组内的了，是越界访问的，所以不能访问）
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;//同理
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			tmpi = begin1;

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
					tmp[tmpi++] = arr[begin1++];
				else
					tmp[tmpi++] = arr[begin2++];
			}
			while (begin1 <= end1)
			{
				tmp[tmpi++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[tmpi++] = arr[begin2++];
			}
			begin1 = end2 + 1;
			end1 = begin1 + gap - 1;
			begin2 = begin1 + gap;
			end2 = begin1 + 2 * gap - 1;
		}
		memcpy(arr, tmp, sizeof(int) * n);
		gap *= 2;
	}
	free(tmp);
}

//归并非递归--每次弄完一组拷回去一组，对于不需要排的，直接break，因为tmp不会覆盖arr里没有进行排序的部分（break跳过了直接）。
void MergeSortNonR2(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc error");
		return;
	}

	int gap = 1;

	while (gap < n)
	{
		int begin1 = 0;
		int end1 = begin1 + gap - 1;

		int begin2 = begin1 + gap;
		int end2 = begin1 + 2 * gap - 1;

		int tmpi = begin1;


		while (begin1 < n)
		{
			//修正路线：遇到不用排序的，直接break
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			int begin = begin1;//修正完再存begin1和end2，要不memcpy拷贝会越界
			int end = end2;
			tmpi = begin1;

			//printf("[%d][%d][%d][%d] ", begin1, end1, begin2, end2);

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
					tmp[tmpi++] = arr[begin1++];
				else
					tmp[tmpi++] = arr[begin2++];
			}
			while (begin1 <= end1)
			{
				tmp[tmpi++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[tmpi++] = arr[begin2++];
			}

			memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));

			begin1 = end2 + 1;
			end1 = begin1 + gap - 1;
			begin2 = begin1 + gap;
			end2 = begin1 + 2 * gap - 1;
		}
		//printf("\n");
		gap *= 2;
	}
	free(tmp);
}

//归并排序非递归
void MergeSortNonR(int* arr, int n)
{
	MergeSortNonR1(arr, n);
	//MergeSortNonR2(arr, n);
}

😈归并排序非递归思想：因为我们通过递归是一直从中间分，直到分成一个一个的再慢慢回归，我们非递归就是直接从每组两个都是一个的序列慢慢以二的指数级扩大，虽然这样说很好理解，但是有许多难控制的细节，比如end1、begin2、end2越界这些情况，还要memcpy拷贝的时机不一样，控制条件的修改也不一样。

一把梭哈和不一把梭哈的区别：
一把梭哈就是每次gap要修改时（说明这一种分组已经全部排的有序）都memcpy全部覆盖（整个数组都被覆盖）到原数组中，那么如果有的越界的本来就不需要排的也会被memcpy覆盖，所以它们即使不排序也要先拷贝到tmp临时数组里，但是如果不是一把梭哈，而是每组弄完就把这一组大小的覆盖到相应位置，那么当越界并且不需要排序时，我们就直接break，不用再拷贝过去然后再拷贝回来，没有意义，这就导致了两种实现方法对于越界的处理不同。

• 疑问总结

tmp临时拷贝进去也是按照原数组中的那部分位置拷进去的，不是每次都从0开始，可以每次都从0开始吗？
并不是必须这样，不过这样比较容易控制，因为我们传的参数都是按照原数组的下标进行操作的（这个只能按照原数组下标），所以我们还按照原来的位置进行赋值能直接使用这些下标，不然还要自己重新创建新的临时变量来控制在tmp中从0下标开始的赋值操作。

能不能不创建tmp临时数组，直接在原数组操作？
不能，因为直接在原数组操作，我们会打破这两组数组的规律：它们本来各自是有序的，如果直接在原数组交换，就不再有序，归并的思想就是让两个有序的数组合并成一个有序的数组，因此不能让它们的本质打破，不然很难控制。

为什么每次递归都要把已经排好的这部分覆盖到原数组？
因为每次比较是基于原数组的数据进行比较的，然后挪到tmp数组上，如果我们两两比完不立刻覆盖到原数组上，那么在下一次比较时，arr数组中的数据还是原本的无序，那么我们刚才那些递归意义何在，也不能直接在tmp里操作我们已经排好的有序数组，因为这就是又是上面提到的问题了。

😈归并排序特性总结

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

五、比较排序总结

• 上面的七个排序都属于比较排序，也都可以称为内排序（内存中），不过归并排序也可以称为外排序（磁盘中即文件中），因为其他排序都要支持随机访问，但是归并不需要随机，只需要让大的文件一半一半的拆分（不算随机，因为每次都是固定的一半），拆成1g左右让每个这样的小文件放到内存中用内排序排一下，然后在磁盘中让这些变有序的开始一一归，二二归，四四归等等用归并思想逐渐拷贝到一个新文件就好了（归并思想中都是按照顺序访问的了，都不是随机访问的了）（用的是非递归）。用递归的话，要很开辟栈帧（因为要一直拆到最后一个数再回归），用哪个都行。反正内存中和文件中思想一样，因为内存中也是划分后按照顺序排序的（归并的思想就是这）。

• 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次
  序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排
  序算法是稳定的；否则称为不稳定的。总结来说也就是：实现该排序后能不能（能够做到就行）是稳定的，不是这种排序一定稳定，是看你怎么实现了。总结：快的只有归并稳，剩下的只有冒泡和插入稳。计数排序一般不考虑了都，没什么意义。而且也都不是原数了。

同一量级：同一量级差距也可能很明显，不要以为他们一样。比如堆排序和快排：都是O(N*logN)，但是堆排在数据很多时明显不如快排，因为堆排首先要建堆，然后每次堆排要和最值换位再向下调整，基本每次都要换到最下边，因为我们在和最值换的时候换的是最后那个元素（可能不是最小，但是是个很小的值）。

• 那下面来看一看非比较排序。

六、非比较排序

非比较排序，也就是说不是通过比大小来进行排序的，它包括：计数排序、基数排序、桶排序。其中只有计数排序有价值，所以我们只学习计数排序就好了。

介绍

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。虽然它在理想情况下时间复杂度只有O(N)，但是它的使用很有限制，只适用于比较集中的数据的排序，详细的思想看实现下面写的吧。

实现

//计数排序-->适用于范围比较集中的数组
void CountSort(int* arr, int n)//计数排序-->相对映射-->适用于负数，如果是绝对映射，就不能有负数了，因为下标不能是负。
{
	int max = arr[0];//max记录的是最大值，而不是最大值的下标
	int min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (min > arr[i])
		{
			min = arr[i];
		}
		if (max < arr[i])
		{
			max = arr[i];
		}
	}
	int range = max - min;//0 ~ range
	int* Acount = (int*)calloc(range + 1, sizeof(int));//创建相对映射并初始化为0。

	//计数
	for (int i = 0; i < n; i++)
	{
		Acount[arr[i] - min]++;
	}
	int i = 0;//在排序时记录arr的下标
	//排序
	for (int j = 0; j <= range; j++)//记录Acount的下标
	{
		int n = Acount[j];//记录每个Acount元素的值
		while (n--)
		{
			arr[i++] = j + min;
		}
	}
	free(Acount);
}

计数排序思想：计数排序就像他的名字一样，通过计数来达到排序的效果，有两种开辟计数数组的方法：绝对映射、相对映射，他们的区别就是开辟计数数组的大小的差异，我们上面是用相对映射实现的。
绝对映射：就是待排序数组最大值为多少，就开辟多大的计数数组的空间，然后遍历一遍待排序的数组，哪个数出现了，就在计数数组该下标++，最后通过遍历一遍计数数组（存的是几就打印几个这个的下标）来实现排序，这样显然是很不合理的，可能会空出来很多空间都不使用，而且如果有负数就出错了，因为下标不能有负的。
相对映射：我们上面写的代码就是相对映射，它是只开辟原排序数组最大值-最小值+1的空间，因为这样就不会出现很多浪费的情况，而且也不用在不可能出现的地方去遍历，然后我们通过让这些数减去最小值来代表他们的下标，每次出现就在该数值减去最小值的下标位置++，最后对计数的数组遍历时也是这个位置的值就等于这个位置的下标加上待排序数组的最小值。而且对于有负数的排序也同样适用。

计数排序特性总结

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定（不用太在意，因为计数排序应用场景很少，更不用说对于它稳定性的应用场景了）

• 计数排序并不是很实用，只对于数据集中的情况下效果会很好。

七、总代码

Stack.h

Stack.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int STDateType;

typedef struct Stack
{
	STDateType* a;
	int top;//如果初始化为0，可以理解为元素个数（也就是栈顶元素下标+1），如果初始化为-1，可以理解为栈顶元素的下标
	int capacity;
}ST;

//初始化和最后销毁
void STInit(ST* ps);
void STDestory(ST* ps);

//入栈
void STPush(ST* ps, STDateType x);

//出栈
void STPop(ST* ps);

//元素个数
int STSize(ST* ps);

//判断是否为空
bool STEmpty(ST* ps);

//栈顶元素
STDateType STTop(ST* ps);

Stack.c

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"

//初始化和最后销毁
void STInit(ST* ps)
{
	assert(ps);
	//ps->a = malloc(sizeof(ST) * 5);  1.没有强转
	ps->a = (STDateType*)malloc(sizeof(ST) * 5);
	2.开辟新空间后没有检查
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->top = 0;
	ps->capacity = 5;
}
void STDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->capacity = 0;
	ps->a = NULL;
	1.没有让top也就是栈顶位置重置。
	ps->top = 0;
	//最后在Test.c上让结构体指针指向空。
}

//入栈
void STPush(ST* ps, STDateType x)
{
	assert(ps);
	//if (ps->top == ps->capacity)
	//{
	//	ST* str = realloc(ps->a, ps->capacity * sizeof(ST) * 2);
	//	if (str == NULL)
	//	{
	//		perror("realloc fail");
	//		return;
	//	}
	//}  
	1.没有把扩容的时候创建的新指针赋给原指针
	if (ps->top == ps->capacity) //判断是否满了
	{
		//ST* temp = realloc(ps->a, ps->capacity * sizeof(ST) * 2);
		//2.指针应该指向数据的类型的地址，而且realloc也没强转为数据类型的指针
		STDateType* temp = (STDateType*)realloc(ps->a, ps->capacity * sizeof(ST) * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return;
		}
		else
		{
			ps->a = temp;
			3.忘记让结构体内的容量*2
			ps->capacity *= 2;
			temp = NULL;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

//出栈
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

//元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

//判断是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//栈顶元素
STDateType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}

Sort.h

Sort.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>

#include "Stack.h"

// 排序实现的接口

// 插入排序
void InsertSort(int* a, int n);

// 希尔排序
void ShellSort(int* arr, int n);

// 选择排序
void SelectSort(int* arr, int n);

// 堆排序->选择排序的优化
void AdjustDown(int* arr, int cur_begin, int n);
void HeapSort(int* arr, int n);

// 冒泡排序
void BubbleSort(int* arr, int n);

// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* arr, int left, int right);

// 快速排序挖坑法
int PartSort2(int* arr, int left, int right);

// 快速排序前后指针法
int PartSort3(int* arr, int left, int right);

void QuickSort(int* arr, int left, int right);

// 快速排序 非递归实现
void QuickSortNonR(int* arr, int left, int right);

// 归并排序递归实现
void MergeSort(int* arr, int n);

// 归并排序非递归实现
void MergeSortNonR(int* arr, int n);

// 计数排序
void CountSort(int* arr, int n);

Sort.c

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"

void PrintArray(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}

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

//直接插入排序
void InsertSort(int* arr, int n)
{
	int end = 0;
	for (end = 0; end < n - 1; end++)
	{
		int end_ = end;
		int tmp = arr[end_ + 1];
		while (end_ >= 0)
		{
			if (arr[end_] > tmp)
			{
				arr[end_ + 1] = arr[end_];
				--end_;
			}
			else
			{
				break;
			}
		}
		arr[++end_] = tmp;
	}
}


希尔排序（四层循环）
//void ShellSort(int* arr,int n)
//{
//	int end = 0;
//	int gap = n;
//	while (gap >= 1)
//	{
//		gap /= 2;
//		int m = 0;
//		for (m = 0; m < gap; m++)//这里多的一层
//		{
//			for (end = m; end < n - gap; end += gap)
//			{
//				int end_ = end;
//				int tmp = arr[end_ + gap];
//				while (end_ >= 0)
//				{
//					if (arr[end_] > tmp)
//					{
//						arr[end_ + gap] = arr[end_];
//						end_ = end_ - gap;
//					}
//					else
//					{
//						break;
//					}
//				}
//				arr[end_ + gap] = tmp;
//			}
//		}
//	}
//}


//希尔排序（三层循环），与四层没差距，所以时间复杂度是看次数，而不是几层循环。
void ShellSort(int* arr, int n)
{
	int end = 0;
	int gap = n;
	while (gap >= 1)
	{
		//gap = (gap / 3)+1
		gap /= 2;
		int m = 0;
		for (end = m; end < n - gap; end++)
		{
			int end_ = end;
			int tmp = arr[end_ + gap];
			while (end_ >= 0)
			{
				if (arr[end_] > tmp)
				{
					arr[end_ + gap] = arr[end_];
					end_ = end_ - gap;
				}
				else
				{
					break;
				}
			}
			arr[end_ + gap] = tmp;
		}
	}
}

单向选择排序：每次只记录最小或最大
//void SelectSort(int* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		int mini = i;
//		for (int j = i + 1; j < n; j++)
//		{
//			if (arr[mini] > arr[j])
//			{
//				mini = j;
//			}
//		}
//		int tmp = arr[mini];
//		arr[mini] = arr[i];
//		arr[i] = tmp;
//	}
//}

//双向选择排序：每次记录最小和最大（记得第二次在交换时要判断是否第一次把第二次要操作的下标的值给修改了，单向选择排序不会出现这种情况）
void SelectSort(int* arr, int n)
{
	int begini = 0;
	int endi = n - 1;

	while (begini < endi)
	{
		int maxi = begini;
		int mini = begini;

		for (int i = begini; i <= endi; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}

		Swap(&arr[begini++], &arr[mini]);
		if (maxi == begini - 1)
		{
			maxi = mini;
		}
		Swap(&arr[endi--], &arr[maxi]);
	}
}

//堆排序->选择排序的优化
//向下调整
void AdjustDown(int* arr, int cur_begin, int n)//这里接收的n就是元素个数
{
	int parent = cur_begin; //不是下标，要减一

	while (parent < n)
	{
		int child = (parent * 2) + 1;

		if (child >= n)//防止越界
			break;

		if (parent * 2 + 2 < n)
		{
			if (arr[child + 1] > arr[child])
			{
				child += 1;
			}
		}
		if (arr[parent] > arr[child])
			break;
		Swap(&arr[parent], &arr[child]);
		parent = child;
	}
}

//升序 -> 建大堆
void HeapSort(int* arr, int n)//n个元素
{
	int begin = (n - 1) / 2;
	for (int cur_begin = begin; cur_begin >= 0; cur_begin--)//建大堆
	{
		AdjustDown(arr, cur_begin, n);//传的第n个，记得用时减一
	}

	//开始堆排序
	int end = n - 1;
	while (end > 0)
	{
		//Swap(&arr[0], &arr[end--]);
		//AdjustDown(arr, 0, end);//end在接收时代表的是n个元素，不是下标，所以这一点错了，没有对应好。
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end--);//end在接收时代表的是n个元素，不是下标，所以这一点错了，没有对应好。
	}
}

冒泡排序
//void BubbleSort(int* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < n - i - 1; j++)
//		{
//			if (arr[j] > arr[j + 1])
//				Swap(&arr[j], &arr[j + 1]);
//		}
//	}
//}

//冒泡排序(升级版，如果最内层循环一次都不交换，则表明有序了，则外层循环就不用继续了)
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int flag = 1;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				flag = 0;
			}
		}
		if (flag)
		{
			//printf("我跳出了哈！\n");
			break;
		}
	}
}

//三数取中
int GetMidNumi(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] > arr[right])
	{
		if (arr[left] < arr[mid])
			return left;
		else if (arr[right] > arr[mid])
			return right;
		return mid;
	}
	else //arr[right] > arr[left]
	{
		if (arr[right] < arr[mid])
			return right;
		else if (arr[left] > arr[mid])
			return left;
		return mid;
	}
}

//快排->hoare版本
//左边做key，右边先走
int PartSort1(int* arr, int left, int right)
{
	小区间优化
	//if (right - left <= 10)
	//{
	//	InsertSort(arr + left, right - left + 1);
	//	return;
	//}

	int begin = left;
	int end = right;

	//随机选key
	//int randi = rand() % (right - left) + left;
	//Swap(&arr[randi], &arr[begin]);
	
	//三数取中
	int mid_i = GetMidNumi(arr, left, right);
	Swap(&arr[mid_i], &arr[begin]);

	int key = arr[begin];

	left++;
	while (left < right)//不能取等，因为：括号里的是进去的条件，我们最好要找到的是left与right相遇的位置再和keyi的数据交换，从而确定keyi的位置。下面内部循环的两个也是这样。
	{
		while (left < right)//右边找小
		{
			if (arr[right] < key)遇到与k相等的就跳过，不用管，因为相等的话换不换位不影响结果，但是可能出现死循环：
								1.两边都遇到key的话，break，Swap，然后继续进去无限循环。
							   2.这样left在最开始时就不用++跳过自己了（第一条是关键，这个就算提前++第一条也还是那样的问题。）。
				break;
			right--;
		}
		while (left < right)左边找大
		{
			if (arr[left] > key)
				break;
			left++;
		}
		Swap(&arr[left], &arr[right]);交换
	}
	int keyi = left;
	Swap(&arr[begin], &arr[keyi]);
	return keyi;
	//PartSort1(arr, begin, keyi - 1);
	//PartSort1(arr, keyi + 1, end);
}

//挖坑法
//左边做key，右边先走
int PartSort2(int* arr, int left, int right)
{
	小区间优化
	//if (right - left <= 10)
	//{
	//	InsertSort(arr + left, right - left + 1);
	//	return;
	//}

	if (left >= right)
		return;
	int begin = left;
	int end = right;

	//随机选key
	int randi = rand() % (right - left) + left;
	Swap(&arr[randi], &arr[begin]);

	//三数取中
	int mid_i = GetMidNumi(arr, left, right);
	Swap(&arr[mid_i], &arr[begin]);

	int key = arr[begin];
	int hole = left;
	while (left < right)
	{
		while (left < right)
		{
			if (arr[right] < key)
			{
				arr[hole] = arr[right];
				hole = right;
				break;
			}
			right--;
		}
		while (left < right)
		{
			if (arr[left] > key)
			{
				arr[hole] = arr[left];
				hole = left;
				break;
			}
			left++;
		}
	}
	arr[hole] = key;
	int keyi = left;
	//return keyi;
	PartSort2(arr, begin, keyi - 1);
	PartSort2(arr, keyi + 1, end);
}

//前后指针法
//左边做key，右边先走
int PartSort3(int* arr, int left, int right)
{
	小区间优化
	//if (right - left <= 10)
	//{
	//	InsertSort(arr + left, right - left + 1);
	//	return;
	//}

	if (left >= right)
		return;

	int begin = left;
	int end = right;

	随机选key
	//int randi = rand() % (right - left) + left;
	//Swap(&arr[randi], &arr[begin]);

	//三数取中
	int mid_i = GetMidNumi(arr, left, right);
	Swap(&arr[mid_i], &arr[begin]);

	int key = arr[begin];
	
	int pre = begin + 1;
	int cur = begin + 1;
	while (cur <= right)
	{
		if (arr[cur] < key)
		{
			Swap(&arr[pre++], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[begin], &arr[--pre]);
	
	int keyi = pre;
	return keyi;
	//PartSort3(arr, left, pre - 1);
	//PartSort3(arr, pre + 1, right);
}

void QuickSort(int* arr, int left, int right)
{
	//小区间优化
	if (right - left <= 10)
	{
		InsertSort(arr + left, right - left + 1);
		return;
	}

	//hoare
	if (left >= right)
		return;
	int keyi = PartSort1(arr, left, right);
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);

	挖坑法
	//PartSort2(arr, left, right);
	//if (left >= right)
	//	return;
	//int keyi = PartSort2(arr, left, right);
	//QuickSort(arr, left, keyi - 1);
	//QuickSort(arr, keyi + 1, right);
	
	前后指针法
	//if (left >= right)
	//	return;
	//int keyi = PartSort3(arr, left, right);
	//QuickSort(arr, left, keyi - 1);
	//QuickSort(arr, keyi + 1, right);
}

//层序遍历用的是队列
//前序遍历用的是栈：根左右
//快排非递归->第一次先压栈，然后后面开始判断，如果栈不为空，就压入四个值：两次的左右
void QuickSortNonR(int* arr, int left, int right)
{
	ST stack;
	STInit(&stack);
	
	STPush(&stack, left);
	STPush(&stack, right);

	while (!STEmpty(&stack))
	{
		int right = STTop(&stack);
		STPop(&stack);
		int left = STTop(&stack);
		STPop(&stack);

		if (left >= right)
			continue;

		int keyi = PartSort1(arr, left, right);

		//小区间优化
		if (right - left <= 10)
		{
			InsertSort(arr + left, right - left + 1);
			continue;
		}

		//先压右边再压左边，因为栈是后进先出。
		STPush(&stack, keyi + 1);
		STPush(&stack, right);
			
		STPush(&stack, left);
		STPush(&stack, keyi - 1);
	}
}

//归并函数子函数
void _MergeSort(int* arr, int* tmp, int n, int begin, int end)//1.begin表示该段数组起始元素下标，不一定是0。
															 //2.end表示该段数组末尾元素下标，不一定是n - 1。
															
														    //3.tmp临时拷贝进去也是按照原数组中的那部分位置拷进去的，不是每次都从0开始。
														   //并不是必须这样，不过这样比较容易控制，因为我们传的参数都是按照原数组的下标进行操作的（这个只能按照原数组下标），
														  //所以我们还按照原来的位置进行赋值能直接使用这些下标，不然还要自己重新创建新的临时变量来控制在tmp中从0下标开始的赋值操作。
{
	
	
	
	if (begin >= end)						
		return;

	int mid = (end - begin + 1) / 2 + begin;//mid是下标   

	int begin1 = begin;
	int end1 = mid - 1;

	int begin2 = mid;
	int end2 = end;

	int tmpi = begin;

	if (begin1 > end1 || begin2 > end2)//这需要这一步，自己调了半天：如果没有的话，当出现这个情况，并没有返回，继续递归时传的值会变得再次符合函数最开始的循环条件，然后无限循环，栈溢出。
		return;						  //无语，这一点调试了一个小时，不能取等号，因为最后一层递归（两组：每组都是一个数值）时，也需要进行比较并且看是否换位。如果是等号的话，就直接return了，走不到下面的交换数值那一步。

	_MergeSort(arr, tmp, end1 - begin1 + 1, begin, end1);//向左
	_MergeSort(arr, tmp, end2 - begin2 + 1, begin2, end);//向右

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
			tmp[tmpi++] = arr[begin1++];
		else
			tmp[tmpi++] = arr[begin2++];
	}
	while (begin1 <= end1)
	{
		tmp[tmpi++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[tmpi++] = arr[begin2++];
	}
	memcpy(arr + begin, tmp + begin, sizeof(int) * n);//能不能不创建tmp临时数组，直接在原数组操作？ 
													 //不能，因为直接在原数组操作，我们会打破这两组数组的规律：它们本来各自是有序的，如果直接在原数组交换，就不再有序，
													//归并的思想就是让两个有序的数组合并成一个有序的数组，因此不能让它们的本质打破，不然很难控制。
	
												   //为什么每次递归都要把已经排好的这部分覆盖到原数组？
												  //因为每次比较是基于原数组的数据进行比较的，然后挪到tmp数组上，如果我们两两比完不立刻覆盖到原数组上，那么在下一次比较时，
												 //arr数组中的数据还是原本的无序，那么我们刚才那些递归意义何在，也不能直接在tmp里操作我们已经排好的有序数组，因为这就是又是上面提到的问题了。
}

//归并->对两组有序数组进行有序合并
void MergeSort(int* a, int n)
{
	int* tmp = malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc error");
		return;
	}
	_MergeSort(a, tmp, n, 0, n - 1);
	free(tmp);
}


//归并非递归--一把梭哈（每次gap只覆盖一次）
void MergeSortNonR1(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc error");
		return;
	}

	int gap = 1;

	while (gap < n)
	{
		int begin1 = 0;
		int end1 = begin1 + gap - 1;

		int begin2 = begin1 + gap;
		int end2 = begin1 + 2 * gap - 1;

		int tmpi = begin1;

		while (begin1 < n)
		{
			//修正路线：因为我们采用的是一把梭哈（覆盖的是整个数组的大小），所以即使是不需要排序的部分我们也会再覆盖到arr上，因此不需要排序的部分也要先拷贝到tmp里。
			if (end1 >= n)
			{
				end1 = n - 1;

				begin2 = n;//让这两个变成错误的范围，到时候就不会进循环（因为这些数不是数组内的了，是越界访问的，所以不能访问）
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;//同理
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			tmpi = begin1;

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
					tmp[tmpi++] = arr[begin1++];
				else
					tmp[tmpi++] = arr[begin2++];
			}
			while (begin1 <= end1)
			{
				tmp[tmpi++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[tmpi++] = arr[begin2++];
			}
			begin1 = end2 + 1;
			end1 = begin1 + gap - 1;
			begin2 = begin1 + gap;
			end2 = begin1 + 2 * gap - 1;
		}
		memcpy(arr, tmp, sizeof(int) * n);
		gap *= 2;
	}
	free(tmp);
}

//归并非递归--每次弄完一组拷回去一组，对于不需要排的，直接break，因为tmp不会覆盖arr里没有进行排序的部分（break跳过了直接）。
void MergeSortNonR2(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc error");
		return;
	}

	int gap = 1;

	while (gap < n)
	{
		int begin1 = 0;
		int end1 = begin1 + gap - 1;

		int begin2 = begin1 + gap;
		int end2 = begin1 + 2 * gap - 1;

		int tmpi = begin1;


		while (begin1 < n)
		{
			//修正路线：遇到不用排序的，直接break
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			int begin = begin1;//修正完再存begin1和end2，要不memcpy拷贝会越界
			int end = end2;
			tmpi = begin1;

			//printf("[%d][%d][%d][%d] ", begin1, end1, begin2, end2);

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
					tmp[tmpi++] = arr[begin1++];
				else
					tmp[tmpi++] = arr[begin2++];
			}
			while (begin1 <= end1)
			{
				tmp[tmpi++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[tmpi++] = arr[begin2++];
			}

			memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));

			begin1 = end2 + 1;
			end1 = begin1 + gap - 1;
			begin2 = begin1 + gap;
			end2 = begin1 + 2 * gap - 1;
		}
		//printf("\n");
		gap *= 2;
	}
	free(tmp);
}

//归并排序非递归
void MergeSortNonR(int* arr, int n)
{
	MergeSortNonR1(arr, n);
	//MergeSortNonR2(arr, n);
}

//计数排序-->适用于范围比较集中的数组
void CountSort(int* arr, int n)//计数排序-->相对映射-->适用于负数，如果是绝对映射，就不能有负数了，因为下标不能是负。
{
	int max = arr[0];//max记录的是最大值，而不是最大值的下标
	int min = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (min > arr[i])
		{
			min = arr[i];
		}
		if (max < arr[i])
		{
			max = arr[i];
		}
	}
	int range = max - min;//0 ~ range
	int* Acount = (int*)calloc(range + 1, sizeof(int));//创建相对映射并初始化为0。

	//计数
	for (int i = 0; i < n; i++)
	{
		Acount[arr[i] - min]++;
	}
	int i = 0;//在排序时记录arr的下标
	//排序
	for (int j = 0; j <= range; j++)//记录Acount的下标
	{
		int n = Acount[j];//记录每个Acount元素的值
		while (n--)
		{
			arr[i++] = j + min;
		}
	}
	free(Acount);
}

test.c

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"

//直接插入、希尔、选择、堆排、冒泡、快排（版本：霍尔版本、挖坑法、前后指针法）（技巧：随机取值、三数取中、三路划分）（递归和非递归）、归并排序（递归非递归）、计数排序

// 测试排序的性能对比
void TestOP()
{
	srand(time(0));
	const int N = 10000;
	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);
	int* a8 = (int*)malloc(sizeof(int) * N);
	int* a9 = (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];
		a8[i] = a1[i];
		a9[i] = a1[i];

	}

	//直接插入排序
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	printf("InsertSort:%d\n", end1 - begin1);
	//PrintArray(a1, N);
	//
	希尔排序
	//int begin2 = clock();
	//ShellSort(a2, N);
	//int end2 = clock();
	//printf("ShellSort:%d\n", end2 - begin2);
	PrintArray(a2, N);

	//选择排序
	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();
	printf("SelectSort:%d\n", end3 - begin3);
	//PrintArray(a3, N);

	堆排序->选择排序的优化
	//int begin4 = clock();
	//HeapSort(a4, N);
	//int end4 = clock();
	//printf("HeapSort:%d\n", end4 - begin4);
	PrintArray(a4, N);
	
	//冒泡排序
	int begin9 = clock();
	BubbleSort(a9, N);
	int end9 = clock();
	printf("BubbleSort:%d\n", end9 - begin9);
	//PrintArray(a9, N);

	//快排
	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();
	printf("QuickSort:%d\n", end5 - begin5);
	PrintArray(a5, N);

	快排非递归
	//int begin6 = clock();
	//QuickSortNonR(a6, 0, N - 1);
	//int end6 = clock();
	//printf("QuickSortNonR:%d\n", end6 - begin6);
	PrintArray(a6, N);

	归并排序
	//int begin7 = clock();
	//MergeSort(a7, N);
	//int end7 = clock();
	//printf("MergeSort:%d\n", end7 - begin7);
	PrintArray(a7, N);

	归并排序非递归
	//int begin8 = clock();
	//MergeSortNonR(a8, N);
	//int end8 = clock();
	//printf("MergeSortNonR:%d\n", end8 - begin8);
	//PrintArray(a8, N);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(a8);
	free(a9);
}

int main()
{
	srand((unsigned int)time(NULL));
	TestOP();

	测试计数排序
	//int arr[] = { 102,105,106,107,108,104,109,103,102,125,147,164,104 };
	//CountSort(arr, sizeof(arr) / sizeof(int));
	//PrintArray(arr, sizeof(arr) / sizeof(int));

	return 0;
}

总结

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

• 博主长期更新，博主的目标是不断提升阅读体验和内容质量，如果你喜欢博主的文章，请点个赞或者关注博主支持一波，我会更加努力的为你呈现精彩的内容。

🌈专栏推荐
😈魔王的修炼之路–C语言
😈魔王的修炼之路–数据结构初阶
😈魔王的修炼之路–C++
😈魔王的修炼之路–Linux
更新不易，希望得到友友的三连支持一波。收藏这篇文章，意味着你将永久拥有它，无论何时何地，都可以立即找到重新阅读；关注博主，意味着无论何时何地，博主将永久和你一起学习进步，为你带来有价值的内容。