【排序】常见的八大排序算法

前言

        本文排序算法有：冒泡排序、堆排序、直接插入排序、希尔排序、直接选择排序、快速排序、归并排序、计数排序。

❤️感谢支持，点赞关注不迷路❤️

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。生活中很多场景都会使用排序，比如购物页面按价格排序筛选，全国院校排名，比赛成绩排名等等。不多废话，直入正题：

注意：本文排序都以递增进行演示

一、冒泡排序

我们学习编程时接触的第一个排序就是冒泡排序，尽管它的效率不高，但是它有着重要的教学意义，为我们打开了排序算法世界的大门：

动图展示：

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

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

冒泡排序由两个 for 循环组成，外循环表示循环的趟数，内循环表示一次循环中比较的次数。

过程：

1. 
2. 内循环会下标0开始，依次比较下标 [0,1] [1,2] ...[6,7]，如果当前数据大于下一个数据，就将两者进行交换，大的数据就在下一个位置，小的数据就在当前位置。
3. 
4. 如上：下标 [1,2] 比较完后需要进行交换，如此循环到 [6,7]，最大的一个数据就会被排在最后一位，这就是第一趟排序，因为每趟排完最大的数据总会出现在最后一位，因此对于8个数据来说，只需要排7趟就行，因为7趟排完只剩下最小的一个数据不需在排。所以外层循环 i 应该小于 n -1，n为元素个数。
5. 而内循环也不需要每次都比较完整个数据，因为每比较一趟，最后一个数据就确认了，因此内循环 j - i 表示每比较完一趟内循环就少比较一个。然后需要注意的是，我们每次比较的两个数据是当前数据和下一个数据，下一个位置的数据不能越界，因此它的下标最大不能超过n-1，j 是当前下标，j+1 要小于 n，因此 j 要小于 n-1。两个限制一起就是 j < n-i-1
6. 最后就是可以简单优化一下，设置一个变量 flag=1，如果内循环完一次，没有进入 if 分支里面，表明整个数据已经有序，不需要交换。进入 if 分支，表示数据仍需要排序，修改flag=0。然后在内循环结束时判断 falg 有没有被修改，没有就直接return返回跳出函数。

空间复杂度：O(1)

时间复杂度：O(n^2)

验证：

二、堆排序

堆排序的理解需要我们学习二叉树的顺序结构 ---- 堆，堆排序就是由堆的特性演化过来的，堆排序的详细介绍我在上一篇二叉树文章中有详细说明。

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

//向下调整算法
void AdjustDown(int* arr, int parent, int n)
{
	//左孩子
	int child = 2 * parent + 1;

	while (child < n)
	{
		//小堆：找左右孩子中小的值
		//大堆：找左右孩子中大的值
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}

		//小堆：孩子节点 < 父节点, 交换
		//大堆：孩子节点 > 父节点，交换
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

//堆排序
void HeapSort(int* arr, int n)
{
	//小堆 -- 降序
	//大堆 -- 升序
	//向下调整算法建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(arr, i, n);
	}

	//排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		--end;
	}
}

堆排序利用向下调整算法建堆，以及用向下调整算法进行排序，因此堆排序的核心就是向下调整算法。

过程：

• 首先在原数组上进行建堆，使之成为一个大堆
• 
• 将原数组按顺序画出完全二叉树，此时二叉树不满足大(小)堆的特性，使用向下调整算法从下往上进行调整建堆。
• 向下调整算法本来的用途是删除堆元素后对堆的调整。对整个堆调整时传入的父结点参数为0，也就是根结点下标。而因为删除堆元素时，堆的根结点左右子树已经是大(小)堆，因此只需要走一遍向下调整算法即可。但是建堆不一样，整个堆的元素都是无序的。
• 因此建堆时，我们需要从下往上，一步一步的把根结点的左右子树变为大(小)堆，第一次传入的父结点参数为 (n-1-1)/2，表示最后一个结点的父节点下标，由此父节点开始，逐渐往上建成大(小)堆。直到传入的参数 i=0 调整根结点。
• 
• 建完堆后，就是排序了，排序也是向下调整算法，模拟堆删除元素，因为堆删除元素是删除堆顶元素，我们建的大堆，堆顶就是堆的最大元素，将堆顶元素与堆底元素交换，让元素总数减1，随后使用一次向下调整算法，堆顶就又被更新成最大元素，每一次交换堆顶和堆底，最大元素就会排到最后，因为每交换一次 end--，因此整个数组的数据从右往左就会逐渐递减，最后排序完，整个数组从左往右就是递增的了。
• 

空间复杂度：O(1)

时间复杂度：O(nlogn)

验证：

时间效率比较：

我们可以看到，排十万个数据堆排序只需要6毫秒，而冒泡排序则需要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. 首先需要一个循环遍历每个元素，用 end 记录当前位置的下标，tmp记录下一个元素，为了避免越界，i<n-1。
2. 然后用当前下标元素与 tmp 比较，如果当前元素更大，就需要往前挪动，因为 tmp 保存了下一个元素因此不用担心数据丢失，随后end--，如果end>=0就继续比较，如果当前end(end以及是后面一个元素了)小于下一个元素就跳出循环。此时end+1就是我们需要插入数据的位置，将tmp插到此处。
3. 
4. 简单点说就是先保存下一个元素tmp，如果当前元素比下一个元素大，那么把当前元素挪到下一个元素位置上，然后当前的下标减减，指向后一个元素，后一个元素再与tmp比较，还大就继续把后一个元素往前挪，然后下标继续减减，指向后后一个元素，直到这个下标不超过0并且这个下标指向的元素小于tmp，那么这个下标前一个位置就是tmp应该插入的位置
5. 再简单点说就是移动排序，像打扑克牌一样，新拿到的牌与手牌比较，比新牌大的牌就往前挪。

空间复杂度：O(1)

时间复杂度：O(N^2)

• 时间复杂度计算的是最差的情况，而直接插入排序最差的情况就是动图演示中的情况，也就是数据是递减的，而我们要排成递增的情况。
• 如果数组是逆序的，那么每个新元素都需要与已排序部分的所有元素进行比较才能找到它的正确位置。对于第i个元素（i从1开始），它需要与之前所有的i-1个元素进行比较。因此，总的比较次数为：
• 

验证：

时间效率比较：

可以看出，即使直接插入排序时间复杂度为O(N^2)，但是它很难遇到极端的情况，也就是出现O(N^2)的情况不常见，因此它比冒泡排序时间效率高。而冒泡排序只有一种情况时间复杂度为O(1)，也就是数据已经有序了，这种情况很难遇到。

四、希尔排序

希尔排序是直接插入排序的升级版，

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数（通常是gap=n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每一组内的记录进行排序，然后 gap=gap/3+1 得到下一个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。

//希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//保证最后一次gap=1
		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;
		}
	}
}

希尔排序简单点说就是将一组数据先进行预排序，因为在直接插入排序中，元素越有序，算法效率越高，因此进行预排序就是先让数据基本有序，最后再进行直接插入排序

过程：

• gap即进行预排序时的分组，gap=gap/3+1，我们知道直接插入排序是当前元素与下一个元素比较，那么希尔排序中，就是将1改为gap，gap/3就是让每3个左右元素为一组，每组单独排序。所有组排完再gap/3分组排序，直到gap=1，为了保证排序最后一次gap=1，也就是最后一次进行直接插入排序，因此gap=gap/3+1，+1就是保证最后一次能取到1，外循环条件 gap>1 而不等于是因为如果等于，那么进过gap=gap/3+1计算会循环等于1，进入了死循环，因此gap>1
• 
• 第二层循环是优化后的结果，原本是每组单独排序，现在是 i 下标到了哪一组就排哪一组，i < n-gap，为了避免arr[end+gap]越界。并且内内循环基本是将直接插入排序中的 1 修改为 gap。
• gap=4循环完后重新计算就等于2，也就是分2组，每隔2个为一组，再进行插入排序，因为前面已经排过一次，第二次排即使每组元素个数多，但是比较次数少了。
• 最后一次gap=1，也就是分1组，每隔1个元素为一组，也就是直接插入排序了，此时数组以及基本有序，效率会非常高。

空间复杂度：O(1)

时间复杂度：O(n^1.3)

希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。《数据结构(C语言版)》---严蔚敏书中给出的时间复杂度为：

验证：

时间效率比较：

可以看出，希尔排序相比直接插入排序，已经得到了很大的提升，排十万个数据，只需要6毫秒

五、直接选择排序

直接选择排序是直接在数据中选择最大值和最小值进行排序，最大值放最后，最小值放开头，依次往下找第二最大值和最小值。

动图展示：

//直接选择排序
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 <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}

		//最大值在首位时，因为最小值会首先与首位交换，因此要重新定位最大值下标为最小值位置
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&arr[mini], &arr[begin]);
		Swap(&arr[maxi], &arr[end]);

		++begin;
		--end;
	}
}

过程：

1. 先遍历数组找出最小值和最大值，然后最大值放最后，最小值放开头，然后begin++,end--，就这么简单
2. 需要注意的就是当最大值刚好是数组首位时，因为最小值会先和首位进行交换，因此遇到这种情况，我们需要更改最大值下标，使之指向最小值下标即可，因为最大值在首位，最小值与首位交换后，最小值下标对应的数据就是最大值。
3. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用，与之相对应的选择排序是堆排序

空间复杂度：O(1)

时间复杂度：O(n^2)

• 直接选择排序无论在什么情况下，数据遍历的次数是固定的，
• 
• 
• 因为无论什么情况下，直接选择排序时间复杂度都为O(N^2)，因此它算得上是最差的排序算法了，冒泡排序都还有个情况时间复杂度为O（1）

验证：

时间效率比较：

可以看到，直接选择排序与冒泡排序大差不差。

六、快速排序

快速排序简称 “快排”，相信即使没学也或多或少听说过它的大名，

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

实现快排的方法有很多，但最核心的东西就是找 "基准值"。

什么是基准值：简单点说，基准值就是它本就应该待在数组中某个位置上的值。

比如说，一个数组元素5本应排序在数组下标为4的位置上，但它在下标为0的位置上，将5排到下标为4的位置上的这个过程就是找基准值，5就是基准值，5回到下标为4的位置后，以它为基准将数组一分为二，两边都不包含元素5，因为它已经排好了，剩下的就是递归剩下分开的两段数组，继续在这两段数组中找基准值，找好了分割然后继续寻找，直到将每个基准值放到它应该待的位置上，排序就完成了

1.hoare版本

//找基准值
//hoare版本
int _QuickSort(int* arr, int left, int right)
{
	int keyi = left;
	++left;

	while (left <= right)
	{
		//right找比基准值小的数据
		while (left <= right && arr[right] > arr[keyi])
		{
			--right;
		}
		//left找比基准值大的数据
		while (left <= right && arr[left] < arr[keyi])
		{
			++left;
		}

		if (left <= right)
		{
			Swap(&arr[left++], &arr[right--]);
		}
	}

	//让基准值待在数组中应该在的位置，即right
	Swap(&arr[right], &arr[keyi]);

	return right;
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	//找基准值
	int keyi = _QuickSort(arr, left, right);
	//递归找左区间[left, keyi-1]基准值
	QuickSort(arr, left, keyi - 1);
	//递归找右区间[keyi+1, right]基准值
	QuickSort(arr, keyi + 1, right);
}

过程：

1. 
2. keyi 为数组首元素下标同时也是基准值下标，记住因为数组会被分割，所以首元素下标不一定为0哦，left 为数组首元素下标，right 为数组末尾下标
3. 定义基准值下标后，left 就可以++了，接下来的过程就是在 [left, right] 范围内找到基准值应该待的位置。
4. 
5. 那么如何找到这个位置？我们让 right 从右往左遍历，如果遇到比基准值小的值，就停下来，left 从左往右遍历，如果遇到比基准值大的值就停下来，简单点说就是 left 找大，right 找小
6. 很明显，left 和 right 一开始就得停下来，都停下来后，就交换 left 与 right 对应的值，此时大的就被扔到了右边，小的被扔到了左边，随后记得让 left++，right--
7. 
8. 仅交换一次明显找不到基准值，因此需要循环，因此外循环 while(left<=right) ，而在 内循环中 right 和 left 在寻找的过程中有可能越界，因此也需要限制在 left<=right。如此循环下去，比基准值大的值都被扔到了右边，比基准值小的都被扔到了左边。
9. 
10. 以上就是循环结束后的效果，此时只需要完成最后一步，交换基准值与 right 下标对应的元素。那么基准值 3 就找到了它应该待的位置。
11. 
12. 如上图，就是一次寻找基准值，找到之后，函数需要返回下标 right ，用返回值 keyi 接收，然后以 right 为基准分为左区间 [left, keyi-1], 右区间 [keyi+1, right]，然后分别递归这两个区间，递归结束条件就是 left <= right，为什么取等，因为当 left==right 时，区间就只有一个元素。
13. 再解释一下在快排子方法 _QuickSort 中，为什么 left<=right ,也就是为什么要取等，因为当 left==right 时，此时 left 是找大，right 是找小，因此它两相等时不能确定当前元素是否是基准值应该待的位置，如下图情况：
14. 
15. 此时 right==left，但是你敢把基准值 6 与 9 交换吗，那不是乱套了吗，大的值被扔到了左边。所以在 left==right 时，循环应该继续。
16. 但是在找 right 和 left 时，像 arr[right] > arr[keyi]这种就不能取等，因为如果遇到以下情况，就会出现问题：
17. 
18. 以上这种情况就会导致 right 与 key 直接交换，递归时无法二分，导致效率低下

2.挖坑法

挖坑法找基准值，以下是动画演示：

//挖坑法
int _QuickSort(int* arr, int left, int right)
{
	int hole = left;
	int key = arr[left];

	while (left < right)
	{
		while (left < right && arr[right] >= key)
		{
			--right;
		}
		arr[hole] = arr[right];
		hole = right;

		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)
{
	if (left >= right)
	{
		return;
	}

	//找基准值
	int keyi = _QuickSort(arr, left, right);
	//递归找左区间[left, keyi-1]基准值
	QuickSort(arr, left, keyi - 1);
	//递归找右区间[keyi+1, right]基准值
	QuickSort(arr, keyi + 1, right);
}

过程：

1. 
2. 除了定义一个基准值 key 保存 arr[left] 外，还要定义一个坑 hole，right 和 left 还是同 hoare 版一样，right 找小，left 找大。当 right 找到比 key 小的值就停下来，将 right 对应的值挖起来填到 hole 处，就是将 right 下标对应的值给到 hole 处，然后 right 就成了新的坑，将 hole 值更新为 right。
3. 
4. 然后 left 开始寻找大的值，找到后依旧赋值给 hole 处，然后 left 处就为新坑
5. 
6. 如此循环下去，最后：
7. 
8. 最后让 hole 处赋值为基准值 key，并返回基准值下标 right，这就是挖坑法，注意挖坑法 left < right。另外arr[right] >= key，如果不等，碰到值全相同的情况，right 和 left 不会移动，陷入死循环。

3.lomuto前后指针

用前后指针法找基准值，动画演示：

//lomuto前后指针法
int _QuickSort(int* arr, int left, int right)
{
	int prev = left, cur = left + 1;
	int keyi = left;

	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		cur++;
	}
	Swap(&arr[prev], &arr[keyi]);

	return prev;
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	//找基准值
	int keyi = _QuickSort(arr, left, right);
	//递归找左区间[left, keyi-1]基准值
	QuickSort(arr, left, keyi - 1);
	//递归找右区间[keyi+1, right]基准值
	QuickSort(arr, keyi + 1, right);
}

过程：

1. 
2. 定义两个指针 prev 和 cur ，分别指向 left 和 left+1，基准值 key 仍是首元素，找基准值的过程就是 cur 不断往前遍历，如果遇到比基准值大的值，cur直接++往前走，如果 cur 遇到比基准值小的值，就让 prev 往前走一步，并交换 cur 和 prev 对应的值。这个过程本身也是将小的值扔到左边，顺便大的值会被交换到右边。
3. 
4. 当然有一种情况就是 ++prev 后，prev 下标与 cur 相同，此时两者没必要进行交换，因此在 cur 遇到小的值时加了一层判断 ++prev!=cur 。这样循环到最后，cur 超过 right 时就停下来，如下图：
5. 
6. 最后 prev 的位置就是基准值 key 应该待的位置，最后 prev 与基准值交换后，返回基准值下标 prev 即可。

以上就是快排找基准值的三种方式，这三种方式实际效率差不多，时间复杂度也相同

空间复杂度：O(logn)

• 因为递归需要开辟函数栈帧，因此有空间的消耗
• logn的由来是以平均情况来看的，假如每次基准值都出现在中间位置，那么数组会一直类似于被2分，n个数据需要2分 logn 次，因此平均情况下，快排空间复杂度为 O(logn)。
• 当然也有差的情况，比如数组已经有序，那么每次找基准值只会排出开头元素，因此空间复杂度为 O(n)

时间复杂度：O(nlogn)

验证：

时间效率比较：

快排毫不意外夺得第一，十万个数据排序仅需4毫秒

递归的算法优化

我们发现，快排虽然效率高，但是在一些极端或者说特殊的情况下，它的效率会急速下降，比如经常被人调侃的，对于已经有序的数组排序，快排的效率还不如冒泡排序，毕竟对于有序的数组，优化后的冒泡时间复杂度为O(n)，而经典的快排应对有序的数组时间复杂度为O(n^2)。

也许你会说，谁会对已经有序的数据进行快排啊，对，但是还有一种情况，比如说有大量重复数据的情况下，在前面有说到，这时快排也捉襟见肘了，因为对重复数据找基准值，在hoare版本中，只能依靠 left 和 right 每次交换后的++和--慢慢使得 left 和 right 逐渐靠近，这样大量交换会使得算法效率急速下降，因此需要进行优化。

优化1：三路划分法

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//先保存区间
	int begin = left;
	int end = right;

	int key = arr[left];
	int cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < key)
		{
			Swap(&arr[cur], &arr[left]);
			++cur;
			++left;
		}
		else if (arr[cur] > key)
		{
			Swap(&arr[cur], &arr[right]);
			--right;
		}
		else
		{
			++cur;
		}
	}

	//三路划分结果
	//[begin, left-1] --- 小于key值
	//[left, right] --- 等于key值
	//[right+1, end] --- 大于key值
	QuickSort(arr, begin, left - 1);
	QuickSort(arr, right + 1, end);
}

过程：

1. 三路划分法，旨在寻找基准值时，将数组分成三个区间：小于基准值的左区间，大于基准值的右区间，以及与基准值相等的区间。多的这个相等的区间就是为了应对有着大量重复数据的情况。
2. 
3. cur 往右遍历，遇到比基准值 key 小的，就交换 cur 和 left 对应的值，随后 cur 和 left 都++
4. cur 如果遇到比基准值 key 大的，就无脑让 cur 与 right 对应的值交换，因为是无脑换的，所以不保证 right 对应的值的大小，right 对应的值可能比 cur 对应的值更大，因此交换完 cur 不++，只让 right--，就能继续比较 cur 对应的值。
5. cur 遇到的第三种情况就是与基准值 key 相等，此时就只让 cur++
6.  
7. 以上就是最后的结果，我们很神奇的发现，区间 [left, right] 刚好就是与基准值相等的区间，此时 left 就是基准值的下标，数组被分为 [begin, left-1]、[left, right]、[right+1, end] 这三个区间，很明显 [left, right] 区间内都是相等的值，因此不用递归，只需要递归左右两个区间，这就是三路划分法。
8. 三路划分法主要解决的是大量重复数据的情况，其时间复杂度和空间复杂度与上述相同

优化2：自省排序

快排的自省排序不仅可以解决大量重复数据的情况，哪怕对于已经有序的数据也不会效率低下，因为它算的上一种混合排序的模式，它融合了直接插入排序和堆排序。

自省排序还解决了如果递归深度太深，可能会栈溢出的情况。

//自省排序
void IntroSort(int* arr, int left, int right, int depth, int defauldepth)
{
	if (left >= right)
	{
		return;
	}

	//数据小于16个使用直接插入排序
	if ((right - left + 1) < 16)
	{
		InsertSort(arr, right - left + 1);
		return;
	}

	//深度大于2*logn，使用堆排序
	if (depth > defauldepth)
	{
		HeapSort(arr, right - left + 1);
		return;
	}

	//深度加一
	depth++;

	
	//正常使用lomuto快排
	int prev = left, cur = left + 1;
	int keyi = left;

	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		cur++;
	}
	Swap(&arr[prev], &arr[keyi]);

	//[left,prev-1] [prev+1,right]
	IntroSort(arr, left, prev - 1, depth, defauldepth);
	IntroSort(arr, prev + 1, right, depth, defauldepth);
}

//快速排序 -- 自省排序
void QuickSort(int* arr, int left, int right)
{
	int depth = 0;
	int logn = 0;

    //计算2分深度logn
	int N = right - left + 1;
	for (int i = 1; i < N; i *= 2)
	{
		logn++;
	}

	IntroSort(arr, left, right, depth, logn * 2);
}

过程：

1. 自省排序的想法就是遇到递归深度过深时，取消经典快排，换用其他排序算法，换用的算法选择堆排序，主要是因为堆排序稳定并且不用开辟辅助空间。
2. 首先是计算当前数组在不断2分的情况下，最多能分几层，类似二叉树的深度。计算过程就是一个 for 循环，不断乘2来算出logn，这与官方 log 函数计算方式相同。
3. 我们知道快排递归时如果基准值每次都在中间位置，那么效率是最好的，因此我们计算出深度 logn 时，传给 IntroSort 自省排序函数时，logn 要乘2，IntroSort 函数的参数 defauldepth 就是指递归的最大深度，如果超过这个，就需要更换排序算法了，那么 logn 选择乘2就是一种折中的方法。
4. IntroSort 函数的另一个参数 depth 就是当前递归的深度，因此每次进入函数时 depth要加1
5. 直接插入排序主要用于在数组长度小于16时，这时候直接插入排序的效率高，不需要再递归找基准值。
6. 自省排序中快排选择的是 lomuto前后指针法，代码短。

自省排序融合了三种排序算法，因此在不同情况下，它的效率十分稳定。

最后一种快排：非递归版本快排

哈哈，没想到吧，快排有如此之多的版本，当然我也没想到

非递归版本的快排需要借助一种数据结构 --- 栈，简单点说，非递归版本的快排就是用循环代替递归，将每次找完基准值后的分区存入栈中，利用栈的先进后出配合循环模拟出递归的效果

//非递归快排
void QuickSortNonR(int* arr, int left, int right)
{
    //先建栈，初始化
	ST st;
	STInit(&st);

    //入栈，存区间，先存右再存左
	StackPush(&st, right);
	StackPush(&st, left);

	while (!StackEmpty(&st))
	{
        //取栈顶元素并出栈，依次赋值给begin和end
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);

        //用lomuto前后指针法找基准值
		int prev = begin;
		int cur = begin + 1;
		int keyi = begin;
		while (cur <= end)
		{
			if (arr[cur] < arr[keyi] && ++prev != cur)
			{
				Swap(&arr[cur], &arr[prev]);
			}
			cur++;
		}
		Swap(&arr[keyi], &arr[prev]);
		keyi = prev;//将基准值下标赋值给keyi

		//左区间[begin, keyi-1]
		//右区间[keyi+1, end]
        //为了存入有效区间，因此需要判断left 是否< right
        //并且需要注意顺序，先存右区间，再存左区间
		if (keyi + 1 < end)
		{
			StackPush(&st, end);
			StackPush(&st, keyi + 1);
		}

		if (keyi - 1 > begin)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}

	STDesTroy(&st);
}

过程：

1. 
2. 详细理解了前面那么多种快排的你，理解非递归版本的快排难度应该不大，我也不再赘述
3. 需要注意的是，每次入栈时，先存右区间，再存左区间，每一个区间又是先存右再存左。然后每次出栈时先取到的元素为 区间的左开始下标，再取就是右结束下标。这些操作主要是为了配合栈的先进后出特性。最后要记得销毁栈。
4. 注意看注释

七、归并排序

归并排序算法思想：

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

void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)
	{
		return;
	}

	//计算中间值
	int mid = (left + right) / 2;
	//[left, mid] [mid+1, right]
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//走到这里说明需要合并了
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];
		}
	}

	//有剩余数据未拷贝, 要么是begin1要么是begin2
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}

	//将tmp数据拷贝到arr
	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. 就是上图中这种情况，例如 10和6，返回上一层函数的区间 [10, 6]，然后对这两个数进行排序，再继续往上回归，再进行递归另一半区间...回归时就是让排好序的区间再合并排序。最终形成有序数组。
4. 因为直接在原数组上进行合并排序会很麻烦，特别是两个数据多的区间进行合并时，直接在原数组上进行合并排序复杂且效率不高，因此我们需要申请一块与原数组一样大的空间，使其专门存放合并排序后的数据，然后拷贝回原数组。
5. 子函数 _MergeSort ，单独出来方便递归，传入的参数包括辅助数组 tmp 和区间左右下标，在子函数中首先求中间值mid，然后以 mid 为中心将数组二分，分成 [left, mid] [mid+1, right]，先递归左区间，递归时回归的条件就是仅剩下一个数据，当两段递归都开始回归后，返回的第一处的函数栈帧就是有着两个数据的区间，接着就开始进行合并排序。
6. 
7. 因为首次合并排序时，只要两个元素，因此 begin 和 end 指向的都是同一数据，我们再另设置一个变量 index 表示 tmp 数组的下标，合并排序的思路就是让两个区间的 begin 指针同时往后遍历，比较 begin 对应的值，然后小的值给到数组 tmp，并让数组下标 index++，小的 begin 指针也++。
8. 
9. 第一次循环结束后就是以上情况，循环条件就是 begin1<=en1 && begin2<=end2，根据上图，我们发现循环结束了还有元素未进入 tmp 数组，因此我们再设立两组循环，用于让有剩余数据的一个区间将数据全部拷贝进 tmp 数组。
10. 最后把 tmp 的数据拷贝回 arr 数组。整体递归下来，这就是归并排序。

空间复杂度：O(n)

        数组 tmp 开辟了 n 个辅助空间。

时间复杂度：O(nlogn)

验证：

时间效率比较：

十万个数据归并排序仅需4毫秒

八、非比较排序 --- 计数排序

前面的排序算法都需要进行数据间的比较才能正确排序，假如规定不能进行数据比较，如何将一段数据进行排序呢？

计数排序就是一种非比较排序，操作步骤：

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

如图：

我们如上的这个数组，不进行比较，然后排序，怎么做呢？

步骤：

1. 首先我们需要创建一个计数数组，就是专门用来统计每个元素出现的次数，然后利用下标对数据进行排序。
2. 计数数组的大小由数据的最大值减去最小值加1得到，创建完成后需要把数组数据全初始化为0。
3. 
4. 下标怎么用来排序？，我们让下标 0 的位置映射的值为最小值，即 count [arr[i] - min]，arr[i] 为原数组，原数组的每个数据减去最小值，得到的就是计数数组的下标，然后每计算到一个下标，就++当前下标对应的值，最终就得到完整的计数数组，是不是很巧妙？
5. 
6. 计数数组不仅包含了每个数据的个数，还通过下标让其从小到大进行了排序。

以下为完整代码：

//计数排序
void CountSort(int* arr, int n)
{
	//找最小和最大值
	int min = arr[0];
	int max = arr[0];
	for (int i = 0; i < n; i++)
	{
		if (arr[i] < min)
		{
			min = arr[i];
		}
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}

	//开辟空间
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}

	//通过内存函数memset初始化数组
	memset(count, 0, range * sizeof(int));

	//遍历原数组，计算下标并++计数值
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}

	//根据计数，排序原数组
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			arr[index++] = i + min;
		}
	}
}

• 当然，最后一步就是拷贝回原数组，这里也很巧妙，for 循环遍历计数数组，只要下标 i 处的值不为0，就让该下标加上最小值赋值给原数组，因为下标就是通过最小值求得，再加上最小值就是原数值了。因为计数可能不为0，因此采用 while 循环给原数组赋值。

当然，计数排序最难想到的就是通过 减去最小值计算下标，你可能会困惑遇到负数怎么办，你可以自己默算一下，负数作为最小值也完全Ok，计算下标时，负数的最小值减去自己刚好等于0。

计数排序的特性：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 计数排序在数据非常集中时，效率非常高。反之在数据疏散时，开辟的空间就会很大，浪费了大量空间遍历的效率也会下降。

空间复杂度：O(range)

        因为计数排序会开辟计数数组，而计数数组的大小就是range

时间复杂度：O(n+range)

        计数排序也就两个 for 循环，每个循环的时间复杂度都为O(n)，另外还有一个循环，循环次数为range次，虽然其存在内循环，但通常情况下内循环次数可以忽略。因此总的时间复杂度为O(n+range)。

验证：

时间效率比较：（完整代码）

void TestOp()
{
	srand((unsigned int)time(NULL));
	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);
	int* a8 = (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];
	}

	int begin1 = clock();
	HeapSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	InsertSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	ShellSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	SelectSort(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();
	CountSort(a7, N);
	int end7 = clock();

	int begin8 = clock();
	BubbleSort(a8, N);
	int end8 = clock();

	printf("排序相同的%d个随机数，各算法用时：（毫秒）\n", N);
	printf("\n");
	printf("HeapSort: %d\n", end1 - begin1);
	printf("InsertSort: %d\n", end2 - begin2);
	printf("ShellSort: %d\n", end3 - begin3);
	printf("SelectSort: %d\n", end4 - begin4);
	printf("QuickSort: %d\n", end5 - begin5);
	printf("MergeSort: %d\n", end6 - begin6);
	printf("CountSort: %d\n", end7 - begin7);
	printf("BubbleSort: %d\n", end8 - begin8);

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


int main()
{
	TestOp();

	return 0;
}

运行结果：

排序十万个数据，计数排序达到了恐怖的0毫秒，超越了以上所有排序。当然计数排序不是万能的，有着适用场景的限制。

（ps：测试时可以选择 release 版本，速度会快些，Debug版本会加载调试信息，速度会慢些）

九、排序的分类及稳定性分析

1.分类

1. 希尔排序为直接插入排序的升级版，都属于插入排序
2. 直接选择排序、堆排序都是选择排序，直接选择排序是直接选最大最小值，堆排序则是因为堆分为大堆和小堆，通过堆顶的最大最小值进行排序。
3. 冒泡排序、快排都是通过交换来排序，都使用了大量的 Swap 函数。
4. 归并单独一类
5. 计数属于非比较排序

2.稳定性

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之 前，则称这种排序算法是稳定的；否则称为不稳定的。

简单点说：原数组中有重复数据，这些重复数据在原数组中的相对前后顺序，在排完序后没有改变，则称该排序算法是稳定的。

计数排序也是稳定的排序算法。

总结

        以上就是本文的全部内容了，感谢大家的支持！