常见排序算法（C语言实现）

文章目录

- 排序介绍
- 插入排序
- - 直接插入排序
  - 希尔排序
- 选择排序
- - 选择排序
  - 堆排序
- 交换排序
- - 冒泡排序
  - 快速排序
  - - 递归实现
    - - Hoare版本
      - 挖坑法
      - 前后指针版本
    - 非递归实现
    - - Hoare版本
      - 挖坑法
      - 前后指针版本
    - 快排的优化
    - - 三值取中
      - 小区间优化
- 归并排序
- - 递归实现
  - 非递归实现
- 计数排序
- 排序算法复杂度及稳定性分析
- - 不同算法的运行效率

排序介绍

排序就是使一串记录按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的。比如A = B，在原序列中A在B前面，排序后A仍旧在B前面，则是稳定的。
数据元素全部放在内存中的排序称为内部排序。
数据元素过多而不能同时存放在内存中，需要根据排序过程的要求不断在内外存之间移动数据的排序称为外部排序。
在这里插入图片描述

插入排序

基本思想：把待排序的记录按其关键码值的代销逐个插入到一个已经排好的有序序列中，知道所有的记录插入完为止，得到一个新的有序序列。

直接插入排序

基本介绍：
在待排序的数组中，我们假设前n-1个元素已经是有序的了，然后将第n各元素逐一进行比较，然后将第n个元素放入合适的位置。
一个元素集合越接近有序，直接插入算法的时间效率就越高。
代码：

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}

}

时间复杂度与空间复杂度
插入排序的平均时间复杂度也是 O(n²)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。
插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N-1次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n²)。
动图演示：

希尔排序

基本介绍：
希尔排序是一种插入排序，又称为缩小增量排序。希尔排序在直接插入排序的基础上引入了分组，先分组进行预排序，然后在通过直接插入排序完成最后的排序。
先选定一个数gap（小于这个待排序数据的总数）作为第一增量，元素之间相差gap的元素作为一组，然后分组进行直接插入排序，排序完成后缩小增量，在重复上述操作，直到gap=1，实现最终的排序。
代码：

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

时间复杂度与空间复杂度：
希尔排序时间复杂度是 O(n^1.3-2)，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n²) 复杂度的算法快得多。
算法在执行过程中，只需要几个定义的临时变量，所以空间复杂度为常数级O(1)。
图示：

选择排序

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

选择排序

基本介绍：
直接选择排序也是一种简单的排序方法，它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，…，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。
一个简单的优化就是，反正都要遍历一次，那就可以找出最大最小的值，分别放到结尾和开头，这样能够提高一些效率。
代码：

void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;

	while (begin < end)
	{
		int minI = begin, maxI = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[minI])
				minI = i;
			if (a[i] > a[maxI])
				maxI = i;
		}
		int tmp = a[begin];
		a[begin] = a[minI];
		a[minI] = tmp;
		if (maxI == begin)
			maxI = minI;
		tmp = a[end];
		a[end] = a[maxI];
		a[maxI] = tmp;

		begin++;
		end--;
	}
}

时间复杂度与空间复杂度：
直接选择排序的时间复杂度为 O(n²) ，所以当记录占用字节数较多时，通常比直接插入排序的执行速度快些；
对于空间复杂度来说，简单选择排序仅需一个存储空间用于记录交换的暂存单元，即空间复杂度为 O(1)；
由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。
图示：

堆排序

基本介绍：
堆排序是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它通过堆来进行数据选择。排升序要建大堆，降序要建小堆。
代码：

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 确认child指向大的那个孩子
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		// 1、孩子大于父亲，交换，继续向下调整
		// 2、孩子小于父亲，则调整结束
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	// 向下调整建堆 -- O(N)
	// 升序：建大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
	// O（N*logN）
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

时间复杂度与空间复杂度：
使用堆排序最坏的情况就是一直需要交换结点，则需要循环h - 1次（h为树的高度）。而h = log(N+1)（N为树的总结点数），则排序的时间复杂度为O(logN)。但是在进行堆排序之前需要先建堆，建堆的时间复杂度为O(N)。
对于空间复杂度来说，堆排序仅需几个存储空间用于记录一些下标位置，所以空间复杂度为 O(1)；
图示：

交换排序

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

冒泡排序

基本介绍：
冒泡排序是一个很形象的形容，因为它排序就像冒泡一样，元素是一个一个冒出来的。从第一个元素开始，两两比较，根据升序还是降序，将大的或小的元素向后移。
如果一次遍历完了，都没有发生交换，就说明遍历的序列是有序的，可以直接跳出。这样可以提高一点效率，但是效率还是比不上其他排序算法。
代码：

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

时间复杂度与空间复杂度：
图示：

快速排序

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

递归实现

Hoare版本

基本介绍：
选出一个key值，定义一个L和一个R，L向右走R向左走。（需要注意的是，如果key值是第一个元素，R先走。如果key值是最后一个元素，L先走）
R先移动，遇到比key值小的就停止，然后L开始移动，遇到比key值大的停止，然后将此时L与R的值交换，然后重复以上步骤。直到L和R相遇，此时的值一定是小于key值的，然后把它与key交换。而此时的key值就放在了它应该在的位置，同时将序列分成了左右两个子序列。
为什么R和L相遇时的值一定是小于key值的？R在遇到小于key值的值时会停止，等L移动，L移动有两个结果，一种是遇到比key值大的，两者交换，然后R继续移动；另一种是没有遇到必key值大的，直到相遇，这个是比key值小的值。L在停止前必然是R遇到一个比key小的值停止，两者会交换。所以造成R和L相遇的值一定小于key值的原因是R先走，这是非常巧妙的一步。如果是L先走，那必然相遇位置的值是大于key值的，此时的key值应该取的是最后一个元素。
代码：

void QuickSortHoare(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int left = begin, right = end;
	int keyI = left;
	while (left < right)
	{
		// 右边先走，找小于key值的值
		while (left < right && a[right] >= a[keyI])
			right--;

		// 左边后走，找大于key值的值
		while (right < right && a[left] <= a[keyI])
			left++;

		int tmp = a[left];
		a[left] = a[right];
		a[right] = tmp;
	}

	int tmp = a[left];
	a[left] = a[keyI];
	a[keyI] = a[left];
	keyI = left;
	// 左子序列[begin,keyI)，右子序列(keyI,end]
	QuickSortHoare(a, begin, keyI - 1);
	QuickSortHoare(a, keyI + 1, end);
}

时间复杂度与空间复杂度：
对于快速排序来说，比较的次数是固定的，不会超过O(n)，那么划分的次数就非常重要了。如果初始序列是有序的，那么此时的排序过程就非常的像冒泡排序，时间复杂度为O(n)，则最差的情况时间复杂度为O(n²)。
如果每次key值都在中间，那么就有点像是二分法，则时间复杂度为O(logn)，此时的时间复杂度就是O(n*logn)了。
因为使用了递归，所以在执行过程中需要在栈中保存相关的信息，需要的空间和递归次数有关，递归与划分的次数有关系，也就是最好是O(logn)，最差是O(n)。
图示：

挖坑法

基本介绍：
挖坑法是基于Hoare的，他通过挖坑的方法避免了R和L相遇时的值一定小于key值的问题，因为不是所有人都能理解为什么R和L相遇时的值是小于key值的。但是像Hoare一样，它也需要根据key值的选定来决定是R先走还是L先走。
挖坑法一开始会取出key值，然后R移动找到比key值小的值，把这里的值填到L的位置上，随后L开始移动，找到比key值大的值填到R的位置上，然后R又开始移动，重复上述步骤，直到R和L相遇，最后把key值填入。
代码：

void QuickSortPit(int* a, int begin, int end)
{
	// 当只有一个数据或数列不存在时
	if (begin >= end)
		return;

	int left = begin;
	int right = end;
	int key = a[left];
	int pit = left;
	while (left < right)
	{
		// 右边先走，找比key值小的值
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[pit] = a[right];
		pit = right;

		// 左边再走，找比key值大的值
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}

	a[pit] = key;
	QuickSortPit(a, begin, pit - 1);
	QuickSortPit(a, pit + 1, end);
}

时间复杂度与空间复杂度：
核心思想并没有什么变化，换汤不换药，所以时间复杂度与Hoare版本是一样的。
图示：

前后指针版本

基本介绍：
这个是Hoare的一种变形，还是取一个key值，然后取prev和cur分别指向第一个元素和第二个元素，然后cur向后移动，遇到比key小的值，cur的值就和prev的值交换，遇到比key大的值cur就继续走。这样prev就两种情况与cur在同一位置，或者是停留在值比key值大的位置上，最后cur走到end后，就把prev与key交换，这样也就完成了左右子序列区分的任务。
这是一种Hoare的变形，过程不容易理解，但是代码容易实现。
代码：

void QuickSortPoint(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyI = begin;
	int prev = begin;
	int cur = begin + 1;
	while (cur <= end)
	{
		// 找到比key小的值时，与prev++位置交换，小的向前移动，大的向后移动
		if (a[cur] < a[keyI] && ++prev != cur)
		{
			int tmp = a[prev];
			a[prev] = a[cur];
			a[cur] = tmp;
		}
		cur++;
	}

	int tmp = a[prev];
	a[prev] = a[keyI];
	a[keyI] = tmp;

	keyI = prev;

	QuickSortPoint(a, begin, keyI - 1);
	QuickSortPoint(a, keyI + 1, end);
}

时间复杂度与空间复杂度：
时间复杂度与空间复杂度仍旧与Hoare版本的一样。
图示：

非递归实现

首先我们要知道一个点，每次递归都会开辟一次栈帧空间，而栈帧空间有一个特点就是先开辟的空间最后销毁，但是这也造成了一个问题，如果递归层度过深就会栈溢出。但是快排又依赖于这一先入栈后销毁的特性完成排序。所以我们要实现非递归的快排就需要实现这一特性，而在我们的数据结构中恰好有一个栈的数据结构是具备这种特性的，所以如果我们要非递归实现快排，就要使用栈这个数据结构。

Hoare版本

int Hoare(int* a, int begin, int end)
{
	int left = begin, right = end;
	int keyI = left;
	while (left < right)
	{
		// 右边先走，找小于key值的值
		while (left < right && a[right] >= a[keyI])
			right--;

		// 左边后走，找大于key值的值
		while (right < right && a[left] <= a[keyI])
			left++;

		int tmp = a[left];
		a[left] = a[right];
		a[right] = tmp;
	}

	int tmp = a[left];
	a[left] = a[keyI];
	a[keyI] = a[left];
	keyI = left;

	return keyI;
}

void QuickSortNonR(int* a, int begin, int end)
{
	// 创建、初始化栈，将begin、end插入栈中
	Stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	// 栈非空就循环
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		if (StackEmpty(&st))
			break;
		int left = StackTop(&st);
		StackPop(&st);
		if (StackEmpty(&st))
			break;

		int keyI = Hoare(a, left, right);

		if (keyI + 1 < right)
		{
			StackPush(&st, keyI + 1);
			StackPush(&st, right);
		}

		if (left < keyI - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyI - 1);
		}
	}

	StackDestroy(&st);
}

挖坑法

int Pit(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int key = a[left];
	int pit = left;
	while (left < right)
	{
		// 右边先走，找比key值小的值
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[pit] = a[right];
		pit = right;

		// 左边再走，找比key值大的值
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[pit] = a[left];
		pit = left;
	}

	a[pit] = key;

	return pit;
}
void QuickSortNonR(int* a, int begin, int end)
{
	// 创建、初始化栈，将begin、end插入栈中
	Stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	// 栈非空就循环
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		if (StackEmpty(&st))
			break;
		int left = StackTop(&st);
		StackPop(&st);
		if (StackEmpty(&st))
			break;

		int keyI = Pit(a, left, right);

		if (keyI + 1 < right)
		{
			StackPush(&st, keyI + 1);
			StackPush(&st, right);
		}

		if (left < keyI - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyI - 1);
		}
	}

	StackDestroy(&st);
}

前后指针版本

int Point(int* a, int begin, int end)
{
	int keyI = begin;
	int prev = begin;
	int cur = begin + 1;
	while (cur <= end)
	{
		// 找到比key小的值时，与prev++位置交换，小的向前移动，大的向后移动
		if (a[cur] < a[keyI] && ++prev != cur)
		{
			int tmp = a[prev];
			a[prev] = a[cur];
			a[cur] = tmp;
		}
		cur++;
	}

	int tmp = a[prev];
	a[prev] = a[keyI];
	a[keyI] = tmp;

	keyI = prev;

	return keyI;
}
void QuickSortNonR(int* a, int begin, int end)
{
	// 创建、初始化栈，将begin、end插入栈中
	Stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);
	// 栈非空就循环
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);
		if (StackEmpty(&st))
			break;
		int left = StackTop(&st);
		StackPop(&st);
		if (StackEmpty(&st))
			break;

		int keyI = Point(a, left, right);

		if (keyI + 1 < right)
		{
			StackPush(&st, keyI + 1);
			StackPush(&st, right);
		}

		if (left < keyI - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyI - 1);
		}
	}

	StackDestroy(&st);
}

快排的优化

三值取中

我们之前提到过，如果每次key值的位置恰好在最边上，那么快排的的时间效率就会变成O(n²)，虽然这样的概率很小，但是还是有概率会出现。这时我们可以采用三值取中法来避免这种的情况发生。因为key值是影响划分次数的关键，三值取中，就是找到首、中、尾三个位置的值，比较大小，将中间大小的值与key值交换，这样就能保证key值的位置不会是在最边上。

int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else // a[begin] > a[mid]
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

小区间优化

每一层的递归都会以2倍数进行增长，即1,2,4,8,16……，通过这个数列我们可以发现，在逻辑上只要我们减少一层递归，就能减少约一半的递归次数。所以我们可以结合其他排序，进行一个判断，在只有多少数的时候就采用其他排序，这样就能有效的避免递归过深。

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	if ((end - begin + 1) < 15)
	{
		// 小区间用直接插入替代，减少递归调用次数
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int keyi = PartSort3(a, begin, end);

		// [begin, keyi-1]  keyi [keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

归并排序

递归实现

基本介绍：
归并排序是建立在归并操作上的一种有效的排序算法，它采用了分治的思想。将已经有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，然后合并成一个有序的序列。将两个有序表合并成一个有序表叫做二路归并。归并排序需要先分解，在合并。
代码：

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	// [begin, mid] [mid+1, end] 递归让子区间有序
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);

	// 归并[begin, mid] [mid+1, end]
	int begin1 = begin, end1 = mid;
	int begin2 = mid+1, 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++];
	}

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

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

	_MergeSort(a, 0, n - 1, tmp);


	free(tmp);
	tmp = NULL;
}

时间复杂度与空间复杂度：
归并排序有点类似二叉树结构，高度O(logn)，每层循环n次，所以时间复杂度O(n*logn)；
归并排序额外开辟了n个空间加上递归的logn，所以空间复杂度为O(n+logn），但是logn是可以忽略掉的，最后的复杂度为O(n)。
图示：

非递归实现

基本介绍：
归并排序的非递归算法并不需要借助栈这个数据结构来实现，如果使用了栈反而会非常的麻烦，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序。
但是我们需要考虑到一些特殊情况，因为归并是两两归并的，也就是它归并的元素个数是1,2,4,8,16……这样增长的，那么如果元素个数不是这样标准的倍数呢？这时就会有三种情况。
①：最后一个分组中，右侧区间元素个数不够，此时我们合并序列，就需要对这个区间的边界进行控制；
②：最后一个分组中，右侧区间没有元素，就是元素刚好只够左侧区间，那么我们就不需要对这个分组进行合并，因为它本身已经是有序的了；
③：最后一个分组中，左侧区间的元素个数不够，那么我们就不需要对该小组进行合并了。
代码：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	// 归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并
	int rangeN = 1;
	while (rangeN < n)
	{
		for (int i = 0; i < n; i += 2 * rangeN)
		{
			// [begin1,end1][begin2,end2] 归并
			int begin1 = i, end1 = i + rangeN - 1;
			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;
			int j = i;

			// end1 begin2 end2 越界
			// 修正区间  ->拷贝数据 归并完了整体拷贝 or 归并每组拷贝
			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;
			}

			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++];
			}
		}

		// 也可以整体归并完了再拷贝
		memcpy(a, tmp, sizeof(int)*(n));

		rangeN *= 2;
	}

	free(tmp);
	tmp = NULL;
}

计数排序

基本介绍：
计数排序又称为鸽巢排序，是对哈希直接定址法的变形应用，是一种非比较排序。它先统计相同元素出现的次数，然后根据统计的结果将序列回收到原来的序列中。
计数排序适用于数据范围集中的序列，此时效率很高，但是适用的范围及场景受到限制。
代码：

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];

		if (a[i] > max)
			max = a[i];
	}

	int range = max - min + 1;
	int* countA = (int*)calloc(range, sizeof(int));
	if (NULL == countA)
	{
		perror("calloc fail\n");
		exit(-1);
	}
	// 统计次数
	for (int i = 0; i < n; i++)
		countA[a[i] - min]++;

	// 排序
	int k = 0;
	for (int j = 0; j < range; j++)
	{
		while (countA[j]--)
			a[k++] = j + min;
	}

	free(countA);
}

时间复杂度与空间复杂度：
它的时间复杂度和空间复杂度都是由它自身元素的区间跨度决定的，时间复杂度是O(MAX(n,范围))，空间复杂度是O(范围)。
图示：

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

排序算法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
简单选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
直接插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
希尔排序	O(nlogn)~O(n²)	O(n^1.3)	O(n²)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n²)	O(nlogn)~O(n)	不稳定

不同算法的运行效率

数据过大可能会导致栈溢出，所以选择非递归的快排和归并排序来测试。

void TestOP()
{
	srand(time(0));
	const int N = 50000;
	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();
	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();
	BubbleSort(a5, N);
	int end5 = clock();

	int begin6 = clock();
	QuickSortNonR(a6, 0, N - 1);
	int end6 = clock();

	int begin7 = clock();
	MergeSortNonR(a7, N);
	int end7 = clock();

	int begin8 = clock();
	CountSort(a8, N);
	int end8 = 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("BubbleSort:%d\n", end5 - begin5);
	printf("QuickSort:%d\n", end6 - begin6);
	printf("MergeSort:%d\n", end7 - begin7);
	printf("CountSort:%d\n", end8 - begin8);

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