一、排序的相关概念

排序：根据数据中关键字的大小，来进行升序或者降序排列。比如按照英文字母顺序排序，按照商品价格或者销量来排序等。

稳定性：如果存在两个或多个相同的数据，若经过排序后，它们的相对次序保持不变，则称这种排序算法是稳定的；否则就是不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多，不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

本篇介绍的是内部排序。

二、排序类型

三、排序算法实现

可用各种排序算法跑这个OJ—>排序OJ链接

插入排序

1.直接插入排序

基本思想：将待排序的元素逐个插入到一个已经排好序的有序序列中，直到所有元素插入完为止，得到一个新的有序序列 。

初始序列是无序的，怎么将待排元素插入有序序列呢？

第一个元素本身可以看做一个有序序列，所以从第二个元素开始，从后往前遍历比较，插入前面已经排好的有序序列中。将大于该元素的所有元素位置向后挪动一位，在比较的过程中边比较边挪动。

以升序为例

可以发现，假设待排序的序列长度为n，插入排序需要进行n-1趟。

时间复杂度：O(N²)。趟数为n-1，每趟待排序元素需要在前面的有序序列中从后往前比较挪动数据。

最好情况：O(N)；有序，判断一次直接break出来，总共n-1趟，每趟不用挪动数据，量级为。
最坏情况：O(N²)；逆序，每趟都头插，次数1+2+3+…N-1，所以时间复杂度量级是。

元素集合越接近有序，直接插入排序算法的效率越高。

空间复杂度：O(1)。 没有使用额外空间。

稳定性：稳定。 如果是大于等于某个位置的元素，则在其后面插入，相对位置不变。

//插入排序 稳定 时间复杂度O(N^2) 空间复杂度O(1)
void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;//有序序列的末尾位置
		int x = a[i];//待排序元素
		//将x插入到[0, end]区间中，并保持有序
		while (end >= 0)
		{
			if (x < a[end])
			{
				a[end + 1] = a[end];//往后挪一个位置
				end--;
			}
			else
			{
				break;
			}
		}
		//while循环结束有两种情况:
		//1.end = -1也即x比前面所有数都小;
		//2.x >= a[end] 这两种都是在end后面插入
		a[end + 1] = x;
	}
}

2.希尔排序

希尔排序法又称缩小增量法。是对插入排序的优化方案，效率比直接插入排序要高。

基本思想：将待排序列以间隔gap划分为gap个不同的组，对同组内的元素进行直接插入排序，然后缩小gap，重复上述分组和排序，直到gap=1，也就是直接插入排序，就会得到一个有序序列。

gap取多少合适？

gap初始值一般取n / 2，每趟排序完gap / 2，直到gap=1，即直接插入排序，此时序列接近有序，直接插入效率O(N)。gap也可以每次 ÷ 3，只要保证gap最后一次能取到1。

排升序，gap越大，大的数更快到后面，小的数更快到前面，但是越不接近有序；gap越小，越接近有序，gap=1时，就是直接插入排序。

时间复杂度：平均为O(N^1.3)。希尔排序的时间复杂度至今还没有精确的分析结果，经过大量的实验推出，n在某个特定范围内，希尔排序的比较和移动次数约为N^1.3。

空间复杂度：O(1)。 没有使用额外空间。

稳定性：不稳定。 希尔排序是分组排序的，且每个组内的数据不连续，无法保证相同数据的相对位置不被改变。比如上图中紫色4和橙色4在第一趟排序后，相对位置就发生了变化，所以希尔排序是不稳定排序。

//希尔排序 不稳定  效率比直接插入排序高 
void ShellSort(int* a, int n)
{
	//gap > 1 预排序
	//gap == 1 直接插入排序
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 3 + 1;//也可以,除3后别忘了+1，否则gap为2时除3结果为0
		gap /= 2;
		for (int i = gap; i < n; i++)
		{
			int end = i - gap;
			int tmp = a[i];
			//将x插入到[0, end]区间中，保持有序
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];//往后挪一个位置，方便x插入
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

选择排序

3.简单选择排序

基本思想：每次从剩下的待排序列中标记最小（最大）值的下标位置，遍历完后存放到未排序列的起始位置（也是已排好的序列的下一个位置），直到全部待排序的数据排完。

实际上，我们每趟可以选出两个值，一个最大值，一个最小值，然后分别与序列的起始和末尾元素交换。这样排序的趟数可以减少一半，但比较和交换的次数会×2，整体效率没有太大变化。

时间复杂度：O(N²)。一共选择n趟，每趟与n-1个数进行比较；如果是每次同时选出最大值和最小值，一共需要n/2趟，每趟比较2×(n-1)次，量级都是O(N²)。

选择排序没有最好情况和最坏情况，不管有序还是逆序，都需要进行O(N²)次比较。所以选择排序的性能很差。因为不管是有序还是逆序，选择排序的效率都是最差的O(N²)。

空间复杂度：O(1)。 没有使用额外空间。

稳定性：不稳定。 因为每次是将待排序列的起始位置与序列中最小值（或最大值）进行交换，只保证了最小值的稳定性，但起始位置的稳定性可能会被破坏。（如果同时找出最大值并交换，例如图中一样，最小值表示的元素的稳定性也可能会被破坏，比如上图中第二趟排序4的相对位置就发生了变化）

//选择排序 不稳定 时间复杂度O(N^2) 空间复杂度O(1)
void SelectSort(int* a, int n)
{
	int l = 0, r = n - 1;
	while (l < r)
	{
		int minPos = l, maxPos = l;//标记最小值和最大值的下标
		for (int i = l + 1; i <= r; i++)
		{
			if (a[i] < a[minPos])
				minPos = i;
			if (a[i] > a[maxPos])
				maxPos = i;
		}
		//C语言没有库函数，交换函数需要自己写
		Swap(&a[l], &a[minPos]);
		//如果最大值maxPos与左边界l重合，在l与minPos交换后，最大值转移到了minPos位置
		if (l == maxPos)
			maxPos = minPos;
		Swap(&a[r], &a[maxPos]);
		l++;
		r--;
	}
}

4.堆排序

堆排序在数据结构——堆中已经详细讲过了，这里可能讲的没有那么细致。想详细了解堆的具体原理和使用可以看看这篇博客。

堆排序是利用数据结构堆（Heap）的特性所设计的一种算法，是选择排序的一种。它是通过堆来选择数据。

基本思想： 依次将将堆顶的数据与堆尾的数据交换，然后向下调整成堆，重复上述步骤直到数据完全有序。比如一个大根堆，我们取出堆顶元素（最大数）与最后一个数交换，交换后的最大数不看作在堆里面，那么堆顶元素的左右子树仍满足堆的性质，堆的结构并没有被破坏，然后堆顶元素向下调整成堆，即可选出第二大的数，以此类推到最后一个元素，就可以成功实现堆排序了。

升序：建大堆
降序：建小堆

时间复杂度：O(N*logN)。向下调整建堆的时间复杂度为O(N)（过程在数据结构堆篇），堆顶元素一共进行n-1次交换，每次交换后向下调整为O(logN)，所以最大量级是O(N*logN)。

堆排序也没有最好情况和最坏情况，堆排序不受初始序列顺序的影响，有序或者逆序时间复杂度都是O(N*logN)。

空间复杂度：O(1)。 没有使用额外空间。

稳定性：不稳定。 建堆时数据的相对顺序就可能被改变，在选数时堆顶与堆尾数据交换也可能导致稳定性被破坏。

//C语言没有库函数，交换函数需要自己写
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//堆排序向下调整（排升序建大堆）
void AdjustDown(int* a, int n, int parent)
{
	int child = 2 * parent + 1;//先赋值左孩子
	while (child < n)
	{
		//右孩子存在且右孩子比左孩子更大
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

//堆排序 不稳定 时间复杂度O(N*logN)
void HeapSort(int* a, int n)
{
	//倒着调整，从最后一个非叶子结点开始向下调整建堆 效率O(N)
	for (int i = (n - 2) / 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);//堆顶再向下调整，范围[1,end]
		end--;
	}
}

交换排序

5.冒泡排序

基本思想：从前往后遍历序列，每相邻两个数比较大小，前一个比后一个大就交换，直到将最大元素交换到末尾位置，继续从前往后遍历，重复上述操作，直到所有元素有序。

冒泡排序和选择排序一样都非常容易理解，也不上图演示了（画图太费时间），一切都在代码中。

时间复杂度：O(N²)。一共n趟，每趟比较交换次数递减，总共比较1+2+3+…+n-1次，量级为O(N²)。

最好情况：O(N) ；有序情况下只用进行一趟比较（flag标记），就退出循环。
最坏情况：O(N²)；每趟都进行交换。

空间复杂度：O(1)。 没有使用额外空间。

稳定性：稳定。 前后两个元素相同则不用交换，相对位置没有改变。

//冒泡(交换)排序 稳定 时间复杂度O(N^2)
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		bool flag = false;//判断是否交换过
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = true;
			}
		}
		if (flag == false)//一趟下来没有交换说明已经有序
		{
			break;
		}
	}
}

6.快速排序

快速排序整体的综合性能和使用场景都是比较好的，这也是大多数人使用快排的原因。
快速排序算法应该算是排序算法中的重点了。

快速排序是一种二叉树结构的交换排序方法。

基本思想：任取待排序的序列中的某元素作为key值，按照key值将待排序集合分割成两个子序列，左子序列中所有元素均小于key，右子序列中所有元素均大于key，然后最左右子序列重复该过程，直到所有元素有序。

快速排序的过程与二叉树的前序遍历相似，因此可以采用递归的方式。但在某些极端情况下可能会出现栈溢出，因此有时也会使用非递归的形式实现。

递归实现

快速排序的细节问题有很多，区间问题、key值的选取、交换细节等等，这些细节不注意很容易会造成超时(无限循环)、排序出错等问题。因此也衍生了很多版本：hoare版本、挖坑法、前后指针版本等，还有一些优化key值选取的方法例如“三数取中法”，这些代码有些地方不是那么容易理解，并且冗长，有的版本在排序OJ会跑不过。

上述所有版本这里不再总结，其他博主有更详细的介绍。下面介绍一种AcWing上大佬总结的快排模板，非常厉害，代码简洁易懂，在排序OJ也能跑过。

思路：

我们选取一个key值，使用双指针i和j分别从区间左右两边往中间走，将>=key的数换到右区间，将<=key的数换到左边界，当i>=j时，j（或i）的左边区间都<=key，右边区间都>=key，然后再递归左区间和右区间按照此方法排序。

void QuickSort(int* a, int l, int r)
{
	//递归的终止情况
	if (l >= r) return;
	//最好不选左右端点作key,否则有序或逆序情况下效率很差
	int key = a[(l + r) / 2];
	int i = l - 1, j = r + 1;
	while (i < j)
	{
		while (a[++i] < key);//左边找大
		while (a[--j] > key);//右边找小
		if (i < j)
			Swap(&a[i], &a[j]);
	}
	QuickSort(a, l, j);
	QuickSort(a, j + 1 , r);
}

下面需要证明两个问题：无限循环和无限递归的边界问题。

key的取值会影响后面递归的区间，下面四种写法都是正确的。

上面代码是右边第一种写法。

我们先分析递归区间的取法：

再来分析key的取法
虽然下面这两种区间划分都可以，但具体哪种要看key的取法：

这四种写法取一种即可

但建议写左边两种，因为key取到边界的话，有序或逆序情况下效率很差。
总结：

1.key取a[l]或者a[(l+r)/2]递归区间为QuickSort(a,l,j)和QuickSort(a,j+1,r);
2.key取a[r]或者a[(l+r+1)/2]递归区间为QuickSort(a,l,i-1)和QuickSort(a,i,r);
3.key不建议取边界，最好从中间选取，否则有序或者逆序情况下，效率很差。

时间复杂度：O(N*logN)。时间复杂度=每层的操作次数×树的深度=nlogn

最好情况：O(N*logN) ；有序，只判断不进行交换。
最坏情况：O(N²)；并非逆序，每次划分，key都是最小(最大)的。

空间复杂度：O(logN)。 递归的栈帧开销。

稳定性：不稳定。 快排前后交换数据会导致相对位置 发生改变。

非递归实现

快排的递归过程是将大区间划分为两个小区间，这两个小区间再分别划分成两个更小区间，直到递归到边界条件，结束然后回退到上一层。

所以快排的非递归可以借助队列或者栈的方式来实现。

队列的话可以参考二叉树的层序遍历。

思路：先取队头区间排序处理，再将队头的左右子区间入队，再取队头区间，再将左右区间入队，重复直到队列为空。

下面介绍快排非递归采用栈的实现方法。类似二叉树的前序遍历。

思路：每次取栈顶区间进行快排的单趟排序，然后将该区间的左右子区间入栈，再取栈顶区间处理，重复直到栈空。

//非递归快排
void QuickSortNonRe(int* a, int left, int right)
{
	ST st;
	STInit(&st);
	STPush(&st, left);//左端点入栈
	STPush(&st, right);//右端点入栈
	while (!STEmpty(&st))
	{
		//注意顺序，和入栈顺序相反
		int r = STTop(&st);
		STPop(&st);
		int l = STTop(&st);
		STPop(&st);

		//单趟排序
		int key = a[(l + r) / 2];
		int i = l - 1, j = r + 1;
		while (i < j)
		{

			while (a[++i] < key);//左边找大
			while (a[--j] > key);//右边找小
			if (i < j)
				Swap(&a[i], &a[j]);
		}

		//分为[l, j]和[j + 1, r]区间
		if (l < j)//l == j 说明该区间只有一个值，无需入栈
		{
			STPush(&st, l);
			STPush(&st, j);
		}
		if (j + 1 < r)
		{
			STPush(&st, j + 1);
			STPush(&st, r);
		}
	}
	STDestroy(&st);
}

7.归并排序

递归实现

归并排序的递归实现属于分治算法，分治算法都有三步：

1.分成子问题；
2.递归处理子问题；
3.子问题合并。

归并排序是不断将区间分解成子区间，一分二，二分四…，直到每个区间只有一个元素，然后开始向上合并有序区间，分而治之。实现过程与二叉树的后序遍历类似，先递归再合并处理元素。

时间复杂度：O(N*logN)。与快排一样，时间复杂度=每层的操作次数×树的深度=nlogn

归并排序不受初始数据顺序的影响，不管有序还是无序，时间复杂度都是O(N*logN)。因为每次都递归到最小区间开始合并区间。

空间复杂度：O(N)。 需要额外开辟数组空间。

稳定性：稳定。 归并过程左右区间有两个数相同时，先从左区间取数据。

//归并排序 稳定 时间复杂度O(N*logN) 空间复杂度O(N)
void Merge(int* a, int l, int r, int* tmp)//tmp临时存放合并好的数据
{
	//递归的终止情况
	if (l >= r)
		return;
	//第一步：分成子问题
	int mid = (l + r) / 2;
	//第二步：递归处理子问题
	Merge(a, l, mid, tmp);
	Merge(a, mid + 1, r, tmp);
	//第三步：合并子问题；将[l, mid]和[mid + 1, r]区间归并
	int i = l, j = mid + 1;
	int k = 0;
	while (i <= mid && j <= r)
	{
		if (a[i] <= a[j])//可见稳定性
			tmp[k++] = a[i++];
		else
			tmp[k++] = a[j++];
	}
	//左区间剩余
	while (i <= mid)
		tmp[k++] = a[i++];
	//右区间剩余
	while (j <= r)
		tmp[k++] = a[j++];

	//将归并好的tmp数组的内容交给数组a的[l,r]区间
	memcpy(a + l, tmp, sizeof(int) * k);// k == r - l + 1
	//i = l, k = 0;
	//while (i <= r)
	//	a[i++] = tmp[k++];
}

//归并排序
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (NULL == tmp)
	{
		perror("malloc");
		return;
	}
	Merge(a, 0, n - 1, tmp);
	free(tmp);
}

非递归实现

归并排序的非递归是可以直接从最小区间开始合并的，所以省去了递归划分子区间的过程，使用一个gap值来实现区间的跨度，gap从1开始每循环一次乘2,；区间的跨度从1到2，再到4…以2的指数增长。如果数据个数不满足2ⁿ个，则左右区间可能会发生越界，这就是需要处理的细节问题。

修正区间边界：（左区间的左端点一定不会越界，不用考虑）当左区间的右端点越界，或者右区间的左端点越界，则后面的元素（有序）不再合并，等待下一轮。
否则如果右区间的右端点越界，则使右端点=n-1，进行修正。

//非递归
void MergeSortNonRe(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (NULL == tmp)
	{
		perror("malloc");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int left1 = i, right1 = i + gap - 1;
			int left2 = i + gap, right2 = i + 2 * gap - 1;
			
			if (right1 >= n || left2 >= n)//不再归并
			{
				break;
			}
			if (right2 >= n)//第二区间右端点越界
			{
				right2 = n - 1;
			}
			//合并子区间
			int k = i;
			while (left1 <= right1 && left2 <= right2)
			{
				if (a[left1] <= a[left2])
					tmp[k++] = a[left1++];
				else
					tmp[k++] = a[left2++];
			}
			while (left1 <= right1)
				tmp[k++] = a[left1++];
			while (left2 <= right2)
				tmp[k++] = a[left2++];
			//合并一次，拷贝一次
			memcpy(a + i, tmp + i, sizeof(int) * (right2 - i));
		}
		gap *= 2;
	}
	free(tmp);
}

8.计数排序

前面七种排序算法都属于比较排序，而计数排序是一种非比较排序。并不是通过两个数相比来进行排序的。

计数排序本质就是用数组存储一个映射关系把它的位置保存起来，然后再遍历原先的数组从位置数组中把它拿出来进行排序。

基本思想：统计相同元素出现次数，然后根据统计的结果将序列回收到原来的序列中。

遍历一边序列，元素每出现一次，就将以该元素为下标的数组的值+1，类似哈希表。

但是，如果序列中只有几个数，但这几个数并不算很小，例如{100, 100,101}；我们就需要开辟101个空间来存储，会造成空间的大量浪费。所以对此可以进行优化，利用序列中最大值和最小值的差值来开辟空间。这样只需开辟2个整型空间即可。

时间复杂度：O(N+range)。只需要遍历几遍数组。

归并排序不受初始数据顺序的影响，不管有序还是无序，时间复杂度都是O(N*logN)。因为每次都递归到最小区间开始合并区间。

空间复杂度：O(range)。 需要额外开辟空间。range=最大值-最小值+1

稳定性：不稳定。 没有进行数据交换，本质上是修改了原始数据。

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

//计数排序 时间复杂度O(N+range) 空间复杂度O(range)
void CountSort(int* a, int n)
{
	//第一遍，找出最大值和最小值
	int maxVal = a[0], minVal = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] > maxVal)
			maxVal = a[i];
		if (a[i] < minVal)
			minVal = a[i];
	}
	//开辟数组空间
	int range = maxVal - minVal + 1;
	//calloc自动初始化为0
	int* count = (int*)calloc(sizeof(int), range);
	if (NULL == count)
	{
		perror("malloc");
		return;
	}
	//第二遍，计数
	for (int i = 0; i < n; i++)
		count[a[i] - minVal]++;
	//排序
	int i = 0;
	for (int x = minVal; x <= maxVal; x++)
	{
		while (count[x - minVal]-- > 0)
			a[i++] = x;
	}
	free(count);
}

四、总结

对这八种算法进行性能测试，随机生成10万个数据，统计排序所消耗时间如下：

可以看出，三种基本排序：插入排序、选择排序、冒泡排序所花费的时间明显更多。它们的时间效率都是O(N²)，但是它们的效率却有明显差别。

插入排序最快；选择排序扫描一遍数组，只需要换两次位置；而冒泡排序需要不断交换相邻的元素。因此，选择排序在大型数据集中的性能比冒泡排序更好。

剩下五种排序算法跟它们不是一个量级，数据量太小看不出明显差别，我们单独用100万个数据来测试这五种排序算法的性能。

计数排序最快，但是计数排序的使用场景也有限，本质是拿空间换时间，而且当空间效率O(range)>O(nlog(n))的时候其效率反而不如基于比较的排序；所以计数排序不归在常见的排序算法中。

剩下四种常见算法中，希尔排序、堆排序、归并排序是相差不大的；快速排序是比较突出的，要比其余算法（除了计数排序）都快，快速排序整体的综合性能和使用场景都是比较好的。

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

排序方法		时间复杂度			空间复杂度	稳定性
		平均情况	最好情况	最坏情况
插入排序	插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
	希尔排序	平均 O(n1.3)			O(1)	不稳定
选择排序	选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
	堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
交换排序	冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
	快速排序	O(nlogn)	O(nlogn)	O(n²)	O(nlogn)	不稳定
归并排序		O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
计数排序		O(n+range)	O(n+range)	O(n+range)	O(range)	不稳定

快速排序：一般情况时排序速度最块，但是不稳定，当有序时，反而不好；
归并排序：效率非常不错，在数据规模较大的情况下，比希尔排序和堆排序要好；
堆排序：适合Tok-K问题；例：找出一千万个数中最小的前一百个数；

算法的时间复杂度与初始序列初态无关的算法有：选择排序、堆排序、归并排序。

完整代码：八大排序算法