目录

一排序的概念及其应用

1概念

 2排序在生活的应用

3常见的排序算法

​编辑二插入排序 

1直接插入排序

 1.1代码实现

1.2特性总结

2希尔排序(最小增量排序)

2.1代码实现 

2.2特性总结

三选择排序

1选择排序

1.1代码实现

1.2特性总结

 2堆排序

2.1代码实现

2.2特性总结

四交换排序

1冒泡排序

1.1代码实现

1.2特性总结 

2快速排序

2.1hore法

2.1.1最小区间优化

2.2挖坑法

 2.3前后指针法

 2.4非递归实现

2.5特性总结

五归并排序

1代码实现

 2非递归实现

 3特性总结

 六非比较排序

1代码实现 

2性能测试

3特性总结

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

---

在前面我们学习c语言的时候，我们第一个接触的比较简单的排序想必是——冒泡排序；但在排序这一内容中有很多的排序思想来等着我们去学习，去掌握它们其中的奇妙思想实现！本篇文章让我们来进行对排序的整体认识：

一排序的概念及其应用

1概念

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

与排序有关的几个概念：
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序.如——归并排序。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

 2排序在生活的应用

在买手机时对价格进行从大到小进行观看：

3常见的排序算法

二插入排序 

1直接插入排序

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

 我们在玩扑克牌时，本质上就是用到了这个思想：

 1.1代码实现

先来看看它其中的一趟是这么走的：(这里与下面都是以升序为例)

 

 用end表示所在当前位置的下标，用一个临时变量tmp保存当前位置的值；end往前进行遍历:如果遇到比tmp大的就把end+1位置的值换成end的值,end继续遍历;反之则结束end的遍历

注意：end要走到<0的位置才能停止移动！然后再end+1位置的值换成tmp(end结束遍历的下一步要进行的动作)

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++) //i< n-1防止tmp的取的值越界
	{
		int end=i, tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

1.2特性总结

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

2希尔排序(最小增量排序)

希尔排序法又称缩小增量法。希尔排序法的基本思想是：

先选定一个整数gap，把待排序数据(n)分成个n/gap组，从第一个开始往后距离为gep的数据分在同一组内，并对每一组内的记录进行排序。(预排序)->本质上是插入排序

然后，取重复上述的排序；当gap=1时，进行一遍直接插入排序。这样数据就排好了！

2.1代码实现 

 在写代码的过程中，建议先写出其中一趟的代码，再根据里面的思想继续代码的完善

 初始版本

void ShellSort(int* a, int n)
{
	int gep = n;
	while (gep > 1)
	{
        gep=gep/3+1;
		for (int j = 0; j < gep; j++)
		{
            //只有一组在排序
			for (int i = j; i < n - gep; i += gep)
			{
				int end = i;
				int tmp = a[end + gep];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gep] = a[end];
						end -= gep;
					}
					else
					{
						break;
					}
				}
				a[end + gep] = tmp;
			}
		}
	}
}

将上面代码继续优化：

void ShellSort(int* a, int n)
{
	int gep = n;
	while (gep > 1)
	{
		gep = gep / 3 + 1;
        //预排序处理
		for (int i = 0; i < n-gep ; i++)
		{
			int end = i, tmp = a[end + gep];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gep] = a[end];
					end -= gep;
				}
				else
				{
					break;
				}
			}
			a[end + gep] = tmp;
		}
	}
}

希尔排序看上去这么高大上，实际处理数据的能力如何呢？让我们用代码来简单演示下：

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);
	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];
	}
	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();
	//QuickSort(a6,0, N-1);
	int end6 = clock();
	int begin7 = clock();
	//MergeSort(a7, N);
	int end7 = 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("MergeSortSort:%d\n", end7 - begin7);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
}

srand()与for循环来创建一堆的随机数据(有重复)

begin = clock() end = clock() ->代表了一个程序从启动到结束时所需要花费的时间 

 结果时间上相差了50倍，希尔排序远远优于直接插入排序还是很牛的一个排序

2.2特性总结

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算

取这两者的增加至：O(N) ：n^1.3

4稳定性：不稳定

三选择排序

1选择排序

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

1在数组元素中选择关键码最大(小)的数据元素：若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
2在剩余的元素中，重复上述步骤...

1.1代码实现

void SlectSort(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;
		}
		Swap(&a[mini], &a[begin]);
        //如果begin与maxi同时指向的相同的元素，此时当前最大数已经被移动了，要注意更新maxi
		if (maxi == begin) maxi = mini;
		Swap(&a[maxi], &a[end]);
		begin++;
		end--;
	}
}

1.2特性总结

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

 2堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是：排升序要建大堆，排降序建小堆

2.1代码实现

实现一个堆排序要使用到：向下调整算法(数据交换调整)，如果不清楚的话叫跳转????：​​​​​​二叉树；

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

void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	//判断放里减少计算
	while (child < size)
	{
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	//大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;

	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		//调整堆为大堆
		AdjustDown(a, end, 0);
		end--;
	}
}

2.2特性总结

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

四交换排序

1冒泡排序

字如其义：将最大（最小）的数冒到n-1的位置，再依次将次大(小)的数冒到n-2位置...

1.1代码实现

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

1.2特性总结 

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

2快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程(递归)，直到数组为有序才结束该过程；

这本质上是一种后序遍历

2.1hore法

 老规矩，先来解决其中一趟的问题：

选择第一个位置的元素作为key，要实现：

就要定义两个指针(下标来充当)：begin和end；end一定是在数组的最后一个元素，但begin的位置呢？我们先假设它是key的下一个位置

 

此时左边比一定key值小，右边一定比key值大

 有没有可能存在相遇位置的值是一个比key的值？

分析：

在我们进行移动的前提是：让R先走

相遇的情况有两种：

1.R遇到L停止：R找不到小一直走；直到与L相遇：

2.L遇到 R停止：R先走，找到小之后停下来；L一直走找不到大之后与R相遇： 

 

两种情况的相遇的值都是比key要小的！则无论什么时候相遇的值一定比key小！！ 

左边有序，右边有序就整体就有序了 ：->（二叉树分治的思想）

当begin >= end说明此时的区间不存在或者只有一个数，我们就不用再往下进行递归了；

明白了思路，在写代码之前，要注意的三个点：

1begin无论如何是要在数组的第一个位置的！！

beign在key的前一个位置：当数组的个数是奇数时，执行到最后一步时，出现left与right还没移动就相遇了：

此时交换key与相遇位置的值就会造成错误；

2标记key值要用下标keyi来进行标记：用整形key在也相遇位置的值交换时只是进行与key这一变量进行的交换,不是与在数组里的key值交换

3begin,end在进行判断是否要移动的前提是：永远是：begin<end

4取key值问题：每次取到的key值一定是当前所在区间中的中位数

int GetMidi(int* a, int left, int right)
{
	int middle = (left + right) / 2;
	if (a[left] > a[middle])
	{
		if (a[middle] > a[right])
			return middle;
		else if (a[left] < a[right])
			return left;
		else
			return right;
	}
	else//a[left]<a[middle]
	{
		if (a[middle] < a[right])
			return middle;
		else if (a[left] > a[right])
			return right;
		else
			return left;
	}
}

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

	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int left = begin, right = end;
	int keyi = begin;

	while (left < right)
	{
		// 右边找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		// 左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

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

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

 实现这一排序时要注意的点很多，稍不注意就会写出错误的代码出来导致结果出现错误

2.1.1最小区间优化

在一棵满二叉树上，最后三层的节点个数几乎是占了整个二叉树节点的80%

转化到快排的递归上：

//hore
int PartSort1(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);
    if(end - left + 1 <= 10)
    {
        InsertSort(a , end - left + 1);
    }

	int left = begin, right = end;
	int keyi = begin;
    
	while (left < right)
	{
		// 右边找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		// 左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);

	return left;
}

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

	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

2.2挖坑法

由于hore版本的代码坑太多，有人就将它的进行优化，形成挖坑法，但本质上没有还是一样的，只是好理解些：

// 挖坑法
int PartSort2(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], &a[begin]);

	int key = a[begin];
	int hole = begin;
	while (begin < end)
	{
		// 右边找小，填到左边的坑
		while (begin < end && a[end] >= key)
		{
			--end;
		}

		a[hole] = a[end];
		hole = end;

		// 左边找大，填到右边的坑
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}

		a[hole] = a[begin];
		hole = begin;
	}

	a[hole] = key;
	return hole;
}

这种实现出来的代码你就不会有疑问为什么要右边先走的原因了！！ 

 2.3前后指针法

 

让我们来模拟一下其中一趟： 

我们发现，比key大的数通过cur的移动将它们像推箱子一样推到了右边去了；

最后key与cur位置的值交换，形成比key小的在左边，比key大的在右边，与快排的思路是一样的！！

int PartSort3(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	Swap(&a[mid], &a[begin]);
	int left = begin, right = end;
	int ptr = begin, cur = ptr + 1, keyi = begin;
	while (cur <= end)
	{
		if(a[cur]<a[keyi]&&++ptr!=cur)
			Swap(&a[ptr], &a[cur]);
		cur++;
	}
	Swap(&a[ptr], &a[keyi]);
	keyi = ptr;
	return keyi;
}

 2.4非递归实现

理解了快排的思想，现在让我们来实现一个非递归的方法来实现快排吧！

我们知道：快排最核心的思路就是对数组进行重复的排序(递归)来达到最终的目的：本质上是在内存中不断开辟栈帧来进行处理这个过程；

针对它这个过程，我们可以用栈的特性——后进先出来帮助我们进行实现：

#include<stack>
#include<algorithm>
using namespace std;

int GetMid(int* a, int left, int right)
{
	int middle = (left + right) / 2;
	if (a[left] > a[middle])
	{
		if (a[middle] > a[right])
			return middle;
		else if (a[left] < a[right])
			return left;
		else
			return right;
	}
	else//a[left]<a[middle]
	{
		if (a[middle] < a[right])
			return middle;
		else if (a[left] > a[right])
			return right;
		else
			return left;
	}
}

int PtrSort(int* a, int begin, int end)
{
	int mid = GetMid(a, begin, end);
	Swap(&a[mid], &a[begin]);
	int left = begin, right = end;
	int ptr = begin, cur = ptr + 1, keyi = begin;
	while (cur <= end)
	{
		if(a[cur]<a[keyi]&&++ptr!=cur)
			Swap(&a[ptr], &a[cur]);
		cur++;
	}
	Swap(&a[ptr], &a[keyi]);
	keyi = ptr;
	return keyi;
}

#include<stack>
#include<algorithm>
using namespace std;
void QuickSortNOTR(int* a, int begin, int end)
{
	stack<int> st;
	st.push(end);
	st.push(begin);
	//[begin keyi-1] keyi [keyi+1 end]
	while (!st.empty())
	{
		//顺序问题
		int left = st.top();
		st.pop();
		int right = st.top();
		st.pop();
		int keyi = PtrSort(a, left,right);
		if (left < keyi - 1)
		{
			st.push(keyi - 1);
			st.push(left);
		}
		if (keyi + 1 < right)
		{
			st.push(right);
			st.push(keyi + 1);
		}
	}
}

2.5特性总结

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

五归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

 

 

1代码实现

数据在进行处理时要将元素进行不断的分组...直到每组只有一个元素才来进行组与组之间的合并处理——形成一个新的有序数组(用新开辟的数组tmp来接收)，在将它拷贝到原数组中...

来模拟一下其中一趟： 

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;
	int keyi = (begin + end) / 2;
    //[begin,keyi][keyi+1 end]
	_MergeSort(a, begin, keyi, tmp);//keyi-1
	_MergeSort(a, keyi+1, end, tmp);//keyi
	//归并
	int i = begin;
	int begin1 = begin, end1 = keyi;
	int begin2 = keyi+1, end2 = end;
	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");
		return;
	}
	_MergeSort(a,0 ,n - 1, tmp);
	free(tmp);
}

 2非递归实现

能不能再用栈来实现它的非递归(与快排一样)？？

不能！！因为数据是再递归到最后一层才进行处理，再一次往回返的过程：

如果用栈来存储；在往回返处理数据的过程中栈为空！！

既然这种方法不行，我们就来想想新的方法；

在实现斐波那契的递归中，我们是采用从后向前的方法进行累加的：

int Fac(int N)
{
	if (N <= 2)
		return 1;
	else
		return Fac(N - 1) + Fac(N - 2);
}

但我们说这种方法有缺陷，所以我们采用循环的方式解决问题：(从前往后进行累加)

int Facs(int N)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (N > 2)
	{
		c = a + b;
		a = b;
		b = c;
		N--;
	}
	return c;
}

借助于它的非递归实现的思路：我们是否也可以这样呢？？ 

 

用gap来表示每组的位置，直接进行归并！！（省略了递归的步骤从后面来进行排序）

void MergeSortNOTR(int* a, int n)
{
	int* tmp = (int*)calloc(n, sizeof(int));
	int grap = 1;//每组的元素
	while(grap<n)
	{ 
		for (int i = 0; i < n; i += 2*grap)
		{
			int begin1 = i, end1 = i + grap - 1;
			int begin2 = i + grap, end2 = i + 2 * grap - 1;
			int j = begin1;
			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 + i, tmp + i, sizeof(int) * (end2-i+1));//拷贝的个数
		}
		grap *= 2;
	}
	free(tmp);
}

实现出来代码以后，上面的代码会有问题吗？？ 

答案是：有：越界问题！

end1,begin2,end2都有越界的风险：

进行代码的改进： 

 

void MergeSortNOTR(int* a, int n)
{
	int* tmp = (int*)calloc(n, sizeof(int));
	int grap = 1;//每组的元素
	while(grap<n)
	{ 
		for (int i = 0; i < n; i += 2*grap)
		{
			int begin1 = i, end1 = i + grap - 1;
			int begin2 = i + grap, end2 = i + 2 * grap - 1;
			int j = begin1;
            //说明已经排好了，跳出循环
			if (end1 > n-1 || begin2 > n-1 )
			{
				break;
			}
            //越界，将end2指向最后一个元素
			if (end2 > n-1)
			{
				end2 = n - 1;
			}
			//printf("grap->[%d][%d][%d][%d]\n", begin1, end1,begin2,end2);
			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 + i, tmp + i, sizeof(int) * (end2-i+1));//拷贝的个数
		}
		grap *= 2;
	}
	free(tmp);
}

这样一个非递归的归并排序就"简单"地完成了 

 3特性总结

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

 六非比较排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

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

1代码实现 

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}
	int range = max - min + 1;//开辟range范围的空间
	int* count = (int*)calloc(range, sizeof(int));
	int i = 0;
    //相对映射(多种情况都顶得住)
	for (i = 0; i < n; i++)
	{
		count[a[i]-min]++;
	}
	int b = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[b++] = j + min;
		}
	}
	free(count);
}

2性能测试

// 测试排序的性能对比
void TestOP()
{
	srand(time(0));
	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()+i;//+i减少重复数据
		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();
	QuickSort(a6,0, N-1);
	int end6 = clock();
	int begin7 = clock();
	MergeSort(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);
}
int main()
{
	TestOP();
	return 0;
}

 

3特性总结

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

它只适合整数的排列，数据范围更集中的数组
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定

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

 

以上便是我们在学习排序中所总结的有关知识点，有错误欢迎在评论区指正，感谢您的的观看！