数据结构之各类排序算法代码及其详解

首先，计算区间的中间位置 mid 。然后通过比较区间左右端点和中间点的值，来确定返回哪个位置的索引作为中间值的索引。如果 a[left]<a[mid] ，再判断 a[mid] 和 a[right] 的大小。如果 a[mid]<a[right]，返回 mid ；如果 a[left]>a[right]，返回left；否则返回right。如果 a[left]>=a[mid]，同样再判断 a[left] 和 a[right] 的大小。如果 a[left]<a[right] ，返回 left ；如果 a[mid]>a[right]，返回mid；否则返回right。

PS:这个函数是为了取出一个不是最大或者最小的值，因为max或者min的值会影响快速排序的效率。

5.2.1 Hoare版快速排序

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

首先，检查区间的起始位置 left 是否大于等于结束位置 right ，如果是则直接返回，因为这种情况不需要排序。然后，初始化起始和结束位置的变量 begin 和 end ，通过 ChooseMid 函数选择一个 keyi ，并将keyI与起始位置的元素交换。接下来，通过两个 while 循环，从右向左找到小于keyi，从左向右找到大于keyi，然后交换它们的位置，直到左右指针相遇。相遇后，将keyi与当前指针位置的元素交换，确定keyi 的最终位置 。最后，对keyi左右两侧的子区间分别递归调用 QuickSort1 函数进行排序。

PS:我个人认为Hoare版本的快速排序挺简单的也好理解,个人比较推荐掌握这种。

我们把这个快速排序递归部分具体出来就是这个样子，通过这种方式来把它变的有序。

5.1.2 挖坑法版快速排序

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	int keyi = ChooseMid(a, left, right);
	Swap(&a[keyi], &a[left]);

	int hole = begin;
	int key = a[hole];
	while (left < right)
	{
		while (a[right] >= key&& left < right)
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;
		while (a[left] <= key && left < right)
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}
	//Swap(&stay, &a[left]);
	//keyi = left;
	a[hole] = key;
	keyi = hole;
	QuickSort2(a, begin, keyi - 1);
	QuickSort2(a, keyi + 1, end);
}

首先，如果区间的起始位置 left 大于等于结束位置 right ，则直接返回，因为这种情况不需要排序。然后，初始化起始和结束位置的变量 begin 和 end ，通过 ChooseMid 函数选择一个基准元素的索引 keyi ，并将基准元素与起始位置的元素交换。接着，定义一个变量 hole 并初始化为起始位置，同时记录基准元素的值 key 。通过两个 while 循环，从右向左找到小于key的值，将其放到 hole 位置，更新 hole 为当前的右指针位置；从左向右找到大于基准元素的值，将其放到 hole 位置，更新 hole 为当前的左指针位置（简单来说就是先右边找比key小的，找到后给他放到key的位置，然后key变到右边，接着左边找比key小的，再换给已经到右边的key，最后循环往复）。循环结束后，将key放到 hole 位置，确定基准元素的最终位置 keyi 。最后，对key左右两侧的子区间分别递归调用 QuickSort2 函数进行排序。

5.1.3 前后指针版快速排序

void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	int keyi = ChooseMid(a, left, right);
	//int keyi = left;
	Swap(&a[keyi], &a[left]);
	int first = left;
	int second = left + 1;
	while (second <= right)
	{
		if (a[second] < a[keyi]&&++first!=second)
		{
			//++first;
			Swap(&a[first], &a[second]);
		}
		++second;
	}
	Swap(&a[keyi], &a[first]);
	keyi = first;
	QuickSort3(a, begin, keyi - 1);
	QuickSort3(a, keyi + 1, end);
}

如果左边的位置大于等于右边，就不排序直接返回。先记录下开始和结束的位置，选一个基准元素并和左边的元素交换。然后设两个指针，一个从左边开始，另一个从左边下一个位置开始。在一个循环里，如果第二个指针（second）指向的元素小于基准元素，并且两个指针位置不同(因为同一位置交换没有意义），就交换它们指向的元素，两个指针再移动。如果second指向的元素比keyi大，那就不走if语句，直接加加second。循环完后，把基准元素和第一个指针指向的元素交换，确定基准位置。最后，对keyi两边的子区间再分别进行同样的排序操作。

5.3 快速排序（非递归版）

我们之所以要学习非递归版本的是因为递归版本的快速排序在面对大数量级的时候容易造成栈溢出，从而导致错误，所以我们要学习非递归版本的快速排序。

int PartSort3(int* a, int left, int right)
{
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	int keyi = left;

	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	return keyi;
}

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, right);
	STPush(&st, left);
	while (!STEmpty(&st))
	{
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		int keyi = PartSort3(a, begin, end);
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}
	STDestroy(&st);
}

PartSort3 函数前后指针版快速排序，只不过去掉了递归。

QuickSortNonR 函数实现非递归的快速排序。首先创建一个栈 st 并初始化，将排序区间的左右边界压入栈。在循环中，取出栈顶的两个值作为当前排序区间的起止位置，调用 PartSort3 进行部分排序得到基准索引。若基准右边区间可继续划分，将右边新的区间边界压入栈；若基准左边区间可继续划分，将左边新的区间边界压入栈。循环结束后销毁栈。

PS:其实本质这就是通过栈来进行一种对递归的模拟实现。

6. 归并排序

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;
	int mid = (begin + end) / 2;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);
	int begin1 = begin; 
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	for (int i = 0; i < end-begin+1; ++i)
	{
		a[i+begin] = tmp[i+begin];
	}
}

void MergeSort(int*a,int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

_MergeSort 函数用于对数组的指定区间进行归并排序的核心操作。如果起始位置大于等于结束位置，函数直接返回。通过计算中间位置，对左右子区间分别递归调用 _MergeSort 进行排序。然后，通过循环比较两个子区间的元素，将较小的元素依次放入临时数组 tmp 中。当其中一个子区间遍历完后，将另一个子区间剩余的元素放入 tmp 。最后，将 tmp 中的元素复制回原数组。MergeSort 函数用于对外提供归并排序的接口。首先分配一个与原数组大小相同的临时空间 tmp ，如果分配失败则报错并返回。然后调用 _MergeSort 对整个数组进行排序，排序完成后释放临时空间。

PS：其实他的本质就是分成一块一块然后进行小区间排序，然后小块合并再进行小区间排序，最后达到有序。

6.1 归并排序非递归版

void _MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			int j = i;
			if (end1 > n || begin2 > n)
			{
				break;
			}
			if (end2 > n)
			{
				end2 = n - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			int k = begin1;
			memcpy(a + i, tmp + i, sizeof(int)*(end2 - i + 1));
		}
		gap *= 2;
	}
	free(tmp);
}

void MergeSort(int*a,int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	MergeSortNonR(a,n);
	free(tmp);
}

首先分配一个与原数组大小相同的临时数组tmp用于辅助排序。然后通过一个循环不断增加归并的子数组大小gap，每次循环对数组进行分组归并。对于每个分组，确定两个子数组的起始和结束位置，然后比较并合并两个子数组到tmp中，最后将tmp中的排序结果复制回原数组。当gap小于数组长度n时，不断重复这个过程。MergeSort函数主要用于分配临时空间，调用_MergeSortNonR进行排序，最后释放临时空间。

PS:非递归版的归并排序在代码实现的部分要格外注意边界处理。

7.  计数排序

void CountSort(int* a, int n)
{
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; ++i)
	{
		if (max < a[i])
		{
			max = a[i];
		}
		if (min > a[i])
		{
			min = a[i];
		}
	}
	int range = max - min + 1;
	int* cmp = (int*)malloc(sizeof(int*) * range);
	if (cmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	memset(cmp, 0, sizeof(int) * range);
	for (int i = 0; i < n; ++i)
	{
		cmp[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < n; ++i)
	{
		while (cmp[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(cmp);
}

首先，通过遍历数组找到数组中的最大值 max 和最小值 min 。然后计算数据的范围 range ，并分配一个与范围大小相同的辅助数组 cmp 。接着，再次遍历原数组，对每个元素在辅助数组中对应的位置进行计数。之后，通过另一个循环，根据辅助数组中的计数，将元素按顺序放回原数组。最后，释放辅助数组的内存。

PS：简单来说，他的原理就类似于这种（画的有点丑陋），通过记录出现的数的次数，最后把他们依次放入原始数组里面。从这张图我们也可以看出计数排序在原数组数字重复多并且数字间隔比较密的时候（max-min+1），计数排序会格外的好用。

6. 总结

在实际工程中，没有绝对的最优算法。当处理百万级数据时，快速排序往往表现优异；面对海量数据时，归并排序的稳定性优势凸显；在资源受限的嵌入式系统中，堆排序可能是更安全的选择。理解算法本质，分析数据特征，结合具体场景，才能做出最合适的决策。愿这些排序算法成为你解决实际问题的利剑，在编程之路上助你披荆斩棘！
 
 建议读者在实践中尝试用不同算法处理同一数据集，直观感受性能差异。当面对特殊业务场景时，也可以考虑将多种算法组合使用，或者基于这些经典思想进行改良创新。排序的世界永远充满惊喜，期待你在实践中发现更多精妙之处！