你绝对不可以错过的常见排序算法大全（附详细源代码（C语言版））

常见排序算法的实现（C语言版）1.排序概念2.常见排序算法2.1插入排序2.11直接插入排序2.12折半插入排序2.13二路插入排序2.14希尔排序2.2选择排序2.21直接选择排序2.22堆排序2.3交换排序2.31冒泡排序2.32快速排序（三种版本）2.4归并排序2.5基数排序3.复杂度分析1.排序概念排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操

丶阿部

508人浏览 · 2020-10-03 09:38:27

丶阿部 · 2020-10-03 09:38:27 发布

文章目录

1.排序概念
2.常见排序算法
3.时间效率测试
4.复杂度分析

1.排序概念

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

2.常见排序算法

2.1插入排序

2.11直接插入排序

基本思想： 直接插入排序是一种简单的插入排序法，其基本思想是，把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
当插入第n(n >= 1)个元素时，前边的第n-1个元素已经有序，此时将这个元素与前边已经排好序的元素进行比较，找到合适位置则进行插入，原来位置上的元素后移。排序过程如下图：
在这里插入图片描述

代码实现如下：

//直接插入排序
void InsertSort_1(int *arr, int n)
{
	int i = 1;
	for (; i < n; i++) {
		int tmp = arr[i];//保存当前待排序的数据
		int end = i;
		while (end > 0 && tmp < arr[end - 1]) {
			arr[end] = arr[end - 1];//向后移动数据
			end--;
		}
		arr[end] = tmp;//插入到合适的位置
	}
}

通过观察上述代码我们发现当待排序数据在往前比较时必须得有end > 0这个关键的判断条件， 以确保在比较的过程中数组下标不会越界。这一点十分细节也非常关键，如果不小心忽略了这个细节，则可能会导致排序出错，但如果我们采用带哨兵位的直接插入排序，则可以避免这一风险。
哨兵位一般设置在整个数组的第一位， 这个位置的数据一般不参与排序，只是为了防止数组下标越界而设置。

代码实现如下：

//带哨兵位的直接插入排序
void InsertSort_2(int *arr, int n)
{
	int tmp = arr[0];
	int i = 1;
	for (; i < n; i++) {
		arr[0] = arr[i];//哨兵位
		int end = i;
		while (arr[0] < arr[end - 1]) {
			arr[end] = arr[end - 1];//向后移动数据
			end--;
		}
		arr[end] = arr[0];
	}
	arr[0] = tmp;
}

从上述代码可以看出，直接插入排序算法简便，并且容易实现。当待排序记录的数量n很小时，这是一种很好的排序方法。 但是，通常待排序序列中的记录数量n很大，则不宜采用直接插入排序。此时我们想办法对直接插入排序进行改进，通过思考，分别从减少记录的比较次数和移动次数俩方面入手，分别实现以下俩种改进的插入排序。

2.12折半插入排序

由于插入排序的基本操作是在一个有序表中进行查找（比较）和插入，所以我们考虑这个“查找”可以用 “折半查找” 来实现，由此进行的插入排序我们称之为折半插入排序。

代码实现如下：

//折半插入排序
void BinInsertSort(int *arr, int n)
{
	int i = 1;
	for (; i < n; i++) {
		int tmp = arr[i];
		int low = 0;
		int high = i - 1;
		//折半查找
		while (low <= high) {
			int mid = (low + high) / 2;
			if (tmp < arr[mid]) {
				high = mid - 1;
			}
			else { //tmp >= arr[mid]
				low = mid + 1;
			}
		}
		//数据的插入及移动
		int j = i - 1;
		for (; j >= high + 1; j--) {
			arr[j + 1] = arr[j];
		}
		arr[high + 1] = tmp;
	}
}

2.13二路插入排序

二路插入排序的主要思路是通过一个和原待排序记录一样大的辅助空间，利用循环的思路（取模实现）来减少数据的移动次数。 实现时，需要建立首尾俩个指针（如first和finsh）来指示第一个元素和最后一个元素，当待排序元素小于第一个元素时，则直接插入到第一个元素之前，first指针 --（注意将整个数组想象成一个循环的空间）；相反如果其大于最后一个元素，则直接插入到数组末尾，再使finsh指针++即可；如果待排序元素在中间位置，则从finsh位置开始向first方向进行比较并在合适位置进行插入。注意最后需要将排好序的记录依次（从first至finsh）再赋值回原数组。

代码实现如下：

//二路插入排序
void TwoWayInsert(int *arr, int n)
{
	int *tmp = (int *)malloc(sizeof(int)* n);//申请新空间
	assert(tmp != NULL);
    //在辅助空间进行插入排序
	tmp[0] = arr[0];
	int first = 0, finsh = 0;
	int i = 1;
	for (; i < n; i++) {
		if (arr[i] < tmp[first]) { //比第一个元素还小
			first = (first - 1 + n) % n;
			tmp[first] = arr[i];
		}
		else if (arr[i] > tmp[finsh]) { //比最后一个元素还大
			tmp[++finsh] = arr[i];
		}
		else { //该元素在中间
			int end = finsh;
			while (arr[i] < tmp[end]) {
				tmp[(end + 1) % n] = tmp[end];
				end = (end - 1 + n) % n;
			}
			tmp[(end + 1) % n] = arr[i];
			finsh++;
		}
	}
	//赋值回原数组
	int k = 0;
	int j = first;
	for (; k < n; k++) {
		arr[k] = tmp[j];
		j = (j + 1 ) % n;
	}
	free(tmp); //释放申请的空间
	tmp = NULL; //预防野指针
}

从二路插入排序的实现原理可知这种排序手段的确在一地程度上减少了排序过程中的移动次数， 但仍不可避免移动数据。并且由于使用了和原数组一样大的大辅助空间等原因，在实际测试时，可以发现其效率并不高。

2.14希尔排序

希尔排序又称 “缩小增量排序”， 它也是一种属于插入排序类的方法，但在时间效率上较前述几种排序方法有较大的改进。
通过对直接插入排序的分析可知，其算法的时间复杂度为O(n^2)，但如果排序记录为“正序”时，其时间复杂度可提高至O(n)。也就是说当待排序记录基本有序时，直接插入排序的时间效率会有明显的提升， 还有一点是当待排序的记录较少时，直接插入排序也会有很不错的效率。 而希尔排序正是从这俩点分析出发对直接插入排序进行改进得到的一种插入排序方法。
它的基本思想是：先将整个待排序记录分隔成若干个子序列分别进行直接插入排序，待整个记录中的记录基本有序时，再对全体记录进行一次直接插入排序。
如下图表示 “增量” 分别为5、3、1的希尔排序过程：
在这里插入图片描述
从上述排序过程可知，希尔排序的一个特点是：子序列的构成不是简单的“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。

代码实现如下：

//先进的希尔排序
void ShellSort(int *arr, int n)
{
	int dk = n;
	while (dk > 1) {
		dk = dk / 3 + 1;//比较合适的一种设置增量的办法
		int i = dk;
		for (; i < n; i++) {
			if (arr[i] < arr[i - dk]) {
				int tmp = arr[i];
				int end = i - dk;
				while (end >= 0 && tmp < arr[end]) {
					arr[end + dk] = arr[end];
					end -= dk;
				}
				arr[end + dk] = tmp;
			}
		}
	}
}

希尔排序的特性总结：

1.希尔排序是对直接插入排序的优化
2.当dk(增量) > 1时都是预排序，目的是让数组更接近于有序。当dk == 1时，数组已经接近有序，再进一步排序就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比（文章第3部分）
3.希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3 - N^2)
4.稳定性：不稳定

2.2选择排序

基本思想： 选择排序的基本思想是每次在待排序序列中选择一个最小（或最大）的数据元素，放在序列的最前面， 直到所有元素全部排序完毕。

2.21直接选择排序

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

排序过程如下图所示：

在这里插入图片描述

代码实现如下：

//这里是本篇博客第一次用到交换函数，故在此附上代码，下方再次出现时不在展示此代码
//交换函数
void Swap(int *x, int *y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

//获取最小值的下标(直接选择排序)
int GetMinIndex(int *arr, int left, int right)
{
	int min_val = arr[left];
	int index = left;

	int i = left + 1;
	for (; i < right; i++) {
		if (arr[i] < min_val) {
			min_val = arr[i];
			index = i;
		}
	}
	return index;
}

//直接选择排序
void SelectSort(int *arr, int n)
{
	int i = 0;
	for (; i < n - 1; i++) {
		int index = GetMinIndex(arr, i, n);
		if (i != index) {
			Swap(&arr[i], &arr[index]);
		}
	}
}

直接选择排序的特性总结：

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

2.22堆排序

堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行数据选择。需要注意的是排升序要建大堆，排降序建小堆。
下图为一个简单堆排序过程演示（升序）。
在这里插入图片描述
代码实现如下：

//向下调整算法
void AdjustDown(int *arr, int n, int curpos)
{
	int i = curpos;
	int j = 2 * i + 1; //左子树

	while (j < n) { //左子树存在
		if (j + 1 < n && arr[j] < arr[j + 1]) {
			j++;//右子树存在并且大于左子树，指到右子树
		}
		if (arr[i] < arr[j]) { 
			// 向下调整
			Swap(&arr[i], &arr[j]);
			//指到下一个分支，继续判断是否需要调整
			i = j;
			j = 2 * i + 1;
		}
		else {
			break;
		}
	}
}

//堆排
void HeapSort(int *arr, int n)
{
	//创建大堆
	int cur = n / 2 - 1; //先指到最后一个分支
	while (cur >= 0) {
		AdjustDown(arr, n, cur);
		cur--;
	}
	//排序
	int end = n - 1;//最后一个元素
	while (end > 0) {
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}

考虑到上述代码多次调动交换函数导致函数多次压栈，开销较大， 因此思考对其进行改进，不难想出利用一个辅助空间来进行数据移动，以此代替调动函数，从而提升算法的效率。

代码实现如下：

//向下调整算法
void AdjustDown_1(int *arr, int n, int curpos)
{
	int i = curpos; //当前调整的位置
	int j = 2 * i + 1; //左子树

	int tmp = arr[i];
	while (j < n) { //左子树存在
		if (j + 1 < n && arr[j] < arr[j + 1]) {
			j++;//右子树存在并且大于左子树，指到右子树
		}
		if (tmp < arr[j]) {
			// 向下调整
			arr[i] = arr[j];
			//指到下一个分支，继续判断是否需要调整
			i = j;
			j = 2 * i + 1;
		}
		else {
			break;
		}
	}
	arr[i] = tmp;
}

//堆排
void HeapSort_1(int *arr, int n)
{
	//创建大堆
	int cur = n / 2 - 1; //先指到最后一个分支
	while (cur >= 0) {
		AdjustDown_1(arr, n, cur);
		cur--;
	}
	//排序
	int end = n - 1;//最后一个元素
	while (end > 0) {
		Swap(&arr[0], &arr[end]);
		AdjustDown_1(arr, end, 0);
		end--;
	}
}

堆排序的特性总结：

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

2.3交换排序

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

2.31冒泡排序

冒泡排序相信大家都很熟悉了，这里就不再详细介绍它的思路。其过程大概来说，就是通过n-1趟排序（n为元素个数），每一趟进行n-i次比较（i为趟数），每一趟都会将最大（或最小）的一个元素“沉底”，直到最终排序完成。

代码实现如下：

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

以上代码完成冒泡排序并没有任何问题，但我们观察冒泡排序的特性可得出，如果排序过程并未结束但数据已经有序时，它仍然会继续进行比较，直至循环结束，而这种情况必然会造成不必要的时间浪费。 因此我们考虑对其进行改进，改进思路也非常清晰和简单，只需判断如果当前数据已经有序时结束循环即可。

代码实现如下：

//冒泡排序的改进
void BubbleSort_1(int *arr, int n)
{
	bool is_swap = false;//用于标志此趟排序是否有交换，如果有则说明整体数据未必有序，
						  //若没有则说明数据已经有序，直接退出
	int i = 0;
	for (; i < n - 1; i++) {
		int j = 0;
		for (; j < n - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				Swap(&arr[j], &arr[j + 1]);
				is_swap = true; //表示交换过
			}
		}
		if (!is_swap) { //没有交换过，直接跳出循环
			break;
		}
		else {
			is_swap = false;
		}
	}
}

冒泡排序的特性总结：

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

2.32快速排序（三种版本）

基本思想： 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
根据将区间按照基准值划分为左右两半部分的不同方式，快排可分为以下三种版本来实现：

hoare版本
挖坑法
前后指针版本

1.hoare版本
直接上图，应该很好理解！
在这里插入图片描述
代码实现如下：

//三者取中
/*为了避免基准值可能出现的一些极端情况，用第一个元素、
最后一个元素和中间的一个元素三者取中的方法来使基准值更加"趋于合理"。*/
int GetMidValIndex(int *arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] > arr[mid] && arr[left] < arr[right]) {
		return left;
	}
	else if (arr[mid] > arr[left] && arr[mid] < arr[right]) {
		return mid;
	}
	else {
		return right;
	}
}

//hoare版本
int Partition_1(int *arr, int left, int right)
{
	//三者取中
	int index = GetMidValIndex(arr, left, right);
	if (index != left) {
		Swap(&arr[left], &arr[index]);
	}
	int key = arr[left];//基准值

	while (left < right) {
		while (left < right && arr[right] >= key) {
			right--;
		}
		Swap(&arr[left], &arr[right]);
		while (left < right && arr[left] < key) {
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	return left;//right同理
}

//快速排序(三种版本)
#define M 25 //如果待排序的数据量较小，则采用直接插入排序，效率更高
void QuickSort(int *arr, int left, int right)
{
	if (left >= right - 1) {
		return;
	}
	if (right - left <= M) {
		InsertSort_1(arr, right - left); //调用直接插入排序
	}
	else {
		int pos = Partition_1(arr, left, right - 1);//hoare版本
		//int pos = Partition_2(arr, left, right - 1);//挖坑法
		//int pos = Partition_3(arr, left, right - 1);//前后指针法
		QuickSort(arr, left, pos);
		QuickSort(arr, pos + 1, right);
	}
}

2.挖坑法
挖坑法的实现方式和hoare版本几乎没有区别，其更像是对hoare版本的一种改进， 改进的思想与前面堆排的改进思想类似，重点在于预先通过一个辅助空间来保存基准值，从而在需要交换数据时直接进行数据覆盖，而不是调动交换方法， 最后再将最初保存起来的基准值放至对应位置即可。如果进行效率测试，就可以很明显的看出这种改进方式可以很好的提升时间效率。

代码实现如下：
（快速排序的主要逻辑模块及三者取中方法在hoare版本的代码中已经给出，下面的代码不再重复给出，只体现挖坑法的主要逻辑）

//挖坑法
int Partition_2(int *arr, int left, int right)
{
	//三者取中
	int index = GetMidValIndex(arr, left, right);
	if (index != left) {
		Swap(&arr[left], &arr[index]);
	}
	int key = arr[left];//基准值,并将其保存,相当于把它"挖走"
	while (left < right) {
		while (left < right && arr[right] >= key) {
			right--;
		}
		arr[left] = arr[right];
		while (left < right && arr[left] < key) {
			left++;
		}
		arr[right] = arr[left];
	}
	arr[left] = key;//放回基准值至合适位置
	return left;
}

3.前后指针版本
基本思想与过程： 分别建立前后俩个指针front和back，初始位置分别指向left和left+1，建立循环，当back还未“走出数组”时，每次判断arr[back]是否小于关键值。如果小于则front++，在此前提上再判断此时front与back是否相等，如果不相等则交换arr[front]与arr[back],否则什么都不做，循环继续。直到最终跳出循环后，再将arr[left]与arr[front]进行交换，即完成了一趟快排，此时front位置的值为基准值。
如果之前对这种方法没有了解，可能上述文字表述并不容易理解，因此此处上图帮助理解，最后再结合代码应该就没有任何问题了。
在这里插入图片描述
代码实现如下：

//前后指针法
int Partition_3(int *arr, int left, int right)
{
	//三者取中
	int index = GetMidValIndex(arr, left, right);
	if (index != left) {
		Swap(&arr[left], &arr[index]);
	}
	int key = arr[left];//基准值

	int front = left;
	int back = left + 1;
	for (; back <= right; back++) {
		if (arr[back] < key) {
			front++;
			if (back != front) {
				Swap(&arr[back], &arr[front]);
			}
		}
	}
	Swap(&arr[left], &arr[front]);
	return front;
}

快速排序的特性总结：

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

2.4归并排序

基本思想： 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
大致排序过程可参考下图：
在这里插入图片描述
代码实现如下：

//归并排序的过程
void _MergeSort(int *arr, int left, int right, int *tmp)
{
	//先分解
	if (left >= right) {
		return;
	}
	int mid = (left + right) / 2;
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//再归并
	int begin1, end1, begin2, end2;
	begin1 = left, end1 = mid;
	begin2 = mid + 1, end2 = right;
	int i = 0;
	while (begin1 <= end1 && begin2 <= end2) {
		if (arr[begin1] <= arr[begin2]) {
			tmp[i++] = arr[begin1++];
		}
		else {
			tmp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1) {
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2) {
		tmp[i++] = arr[begin2++];
	}
	memcpy(arr + left, tmp, sizeof(int)* (right - left + 1));
}

//归并排序
void MergeSort(int *arr, int n)
{
	int *tmp = (int *)malloc(sizeof(int) * n);//申请临时空间
	assert(tmp != NULL);

	//归并排序的过程
	_MergeSort(arr, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

归并排序的特性总结：

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

2.5基数排序

基数排序是一种典型的非比较排序，是和前面所述各种排序方法完全不同的一种排序方法。前面所讨论的各种排序主要是通过元素的比较和移动这两种操作来实现，而实现基数排序不需要进行元素间的比较。
基数排序是通过借助“分配”和“收集”俩种操作对单逻辑关键字进行排序的一种内部排序方法。
例如，我们采用链表数组来实现对数据的分配和收集，若待排序的数据序列为：278 109 063 930 589 184 505 269 008 083，在遍历数组时将它们分别分配到下标为0到9的链表中（即基数为10），第一次分配，以个位数的值为关键值把数据分配至对应下标的链表中，如下图所示：
在这里插入图片描述

分配结束后，将链表数组中的所有元素按照链表的下标由小到大（链表中由头至尾），依次重新收集，得到如下仍无序的数据序列：930 063 083 184 505 278 008 109 589 269。
然后进行第二次分配，以十位数的值为关键值进行分配， 过程及原理同上，如下图：
在这里插入图片描述
收集过程同上，此次收集之后得到的序列为：505 008 109 930 063 269 278 083 184 589，数据仍然无序。
紧接着进行第三次分配，以百位数的值作为关键值进行分配， 分配后情形如下图所示：

再次以同样的方式进行收集，此次收集完成之后，得到的数据序列为008 063 083 109 184 269 278 505 589 930，此时，我们发现数据已然有序，基数排序完毕。

代码实现如下：

//定义链表结构及相关操作
//用于基数排序中分发和回收数据
#define ELEM_TYPE int

typedef struct SListNode{
	ELEM_TYPE data;//数据域
	struct SListNode *next;//指针域
}SListNode;

typedef SListNode* SList;

void SListInit(SList *phead);
bool SListEmpty(SList phead);
void SListPushBack(SList *phead, ELEM_TYPE x);
void SListPopFront(SList *phead);
ELEM_TYPE SListFront(SList phead);
void SListClear(SList *phead);
void SListDestory(SList *phead);
//
//以下为函数实现
void SListInit(SList *phead)
{
	assert(phead);
	*phead = NULL;
}

bool SListEmpty(SList phead)
{
	return phead == NULL;
}

void SListPushBack(SList *phead, ELEM_TYPE x)
{
	assert(phead);
	SListNode *s = (SListNode *)malloc(sizeof(SListNode));
	assert(s != NULL);//必须确保malloc成功
	s->data = x;
	s->next = NULL;

	//链接节点
	SListNode *p = *phead;
	if (p == NULL){
		*phead = s;//插入的是第一个节点
	}
	else{
		while (p->next != NULL){
			p = p->next;
		}
		p->next = s;
	}
}

void SListPopFront(SList *phead)
{
	assert(phead);
	SListNode *p = *phead;
	if (p == NULL){
		//链表为空
		return;
	}
	else{
		*phead = p->next;
		free(p);
	}
}

ELEM_TYPE SListFront(SList phead)
{
	return phead->data;
}

void SListClear(SList *phead)
{
	assert(phead);
	SListNode *p = NULL;
	while (*phead != NULL){
		p = *phead;
		*phead = p->next;
		free(p);
	}
}

void SListDestory(SList *phead)
{
	assert(phead);
	SListClear(phead);
}
//
//基数排序
#define RADIX 10 //基数
SList list[RADIX]; //链表数组
#define K 3 //排序数据的最大位数

//获取关键值
int GetKey(int value, int k)
{
	int key;
	while (k >= 0) {
		key = value % 10;
		value /= 10;
		k--;
	}
	return key;
}

//分发
void Distribute(int *arr, int n, int k)
{
	int i = 0;
	for (; i < n; i++) {
		int key = GetKey(arr[i], k);//获取当前数据的关键值(哪一位)
		SListPushBack(&list[key], arr[i]);//分发数据至链表数组指定位置(尾插)
	}
}

//回收
void Collect(int *arr)
{
	int k = 0;
	for (int i = 0; i < RADIX; i++) {
		while (!SListEmpty(list[i])) {
			arr[k++] = SListFront(list[i]); //回收链表的头部元素
			SListPopFront(&list[i]); //回收后删除，更新头部元素
		}
	}
}

//基数排序
void RadixSort(int *arr, int n)
{
	for (int i = 0; i < RADIX; i++) {
		SListInit(&list[i]);//初始化单链表
	}
	for (int i = 0; i < K; i++) {
		//K次分发
		Distribute(arr, n, i);
		//K次回收
		Collect(arr);
	}
	//使用完毕之后摧毁单链表
	for (int i = 0; i < RADIX; i++) {
		SListDestory(&list[i]);
	}
}

基数排序的特性分析：

1.在某些时候，基数排序的效率高于其它的稳定性排序法
2.时间复杂度：O(d(n+r)) (d为位数，r为基数，n为元素个数)
3.空间复杂度：O(n+r)
4.稳定性:稳定

3.时间效率测试

可通过clock()对上述排序算法的时间效率做一个简单测试，从而可以从宏观上大致观察出以上各大排序算法的性能如何。
如用以下代码进行测试：

//测试排序效率
void TestSortEfficiency()
{
	int n = 20000; //测试数据量
	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);
	int *a10 = (int *)malloc(sizeof(int)* n);
	int *a11 = (int *)malloc(sizeof(int)* n);
	int *a12 = (int *)malloc(sizeof(int)* n);

	srand((unsigned int)time(NULL));
	int i = 0;
	for (; i < n; i++) {
		a1[i] = rand();//生成n个随机数
		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];
		a10[i] = a1[i];
		a11[i] = a1[i];
		a12[i] = a1[i];
	}

	time_t start = clock();
	InsertSort_1(a1, n);
	time_t end = clock();
	printf("InsertSort_1Eff: %u\n", end - start);

	start = clock();
	InsertSort_2(a2, n);
	end = clock();
	printf("InsertSort_2Eff: %u\n", end - start);

	start = clock();
	BinInsertSort(a3, n);
	end = clock();
	printf("BinInsertSortEff: %u\n", end - start);

	start = clock();
	TwoWayInsert(a4, n);
	end = clock();
	printf("TwoWayInsertEff: %u\n", end - start);

	start = clock();
	ShellSort(a5, n);
	end = clock();
	printf("ShellSortEff: %u\n", end - start);

	start = clock();
	SelectSort(a6, n);
	end = clock();
	printf("SelectSortEff: %u\n", end - start);

	start = clock();
	HeapSort_1(a7, n);
	end = clock();
	printf("HeapSort_1Eff: %u\n", end - start);

	start = clock();
	BubbleSort(a8, n);
	end = clock();
	printf("BubbleSortEff: %u\n", end - start);

	start = clock();
	BubbleSort_1(a9, n);
	end = clock();
	printf("BubbleSort_1Eff: %u\n", end - start);

	start = clock();
	QuickSort(a10, 0, n);
	end = clock();
	printf("QuickSortEff: %u\n", end - start);

	start = clock();
	MergeSort(a11, n);
	end = clock();
	printf("MergeSortEff: %u\n", end - start);

	start = clock();
	RadixSort(a12, n);
	end = clock();
	printf("RadixSortEff: %u\n", end - start);
}

以上代码运行结果如下图所示：
在这里插入图片描述
上述结果为排序20000万个数据各大排序算法所消耗的时间（单位为毫秒ms），从一定程度上可以反应出各大排序算法的性能好坏，并且如果只关注时间效率，孰好孰坏则一目了然。

4.复杂度分析

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