前言

在数据结构（六）：排序（一）中介绍了直接插入排序、希尔排序、选择排序、堆排序和冒泡排序，本文继续介绍剩下的快速排序、归并排序和计数排序

一、快速排序

快速排序的基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值（单趟排序），然后左右子序列重复该过程（递归），直到所有元素都排列在相应位置上为止。

将区间按照基准值划分为左右两半部分的常见方式有左右哨兵法、挖坑法。

1.单趟排序

以下的三种方法都是对[left,right]的闭区间进行排序，所以假设对n个元素的数组排序，传参时一定要使left=0,right=n-1。

（1）左右哨兵法

一般选择最左边的元素或最右边的元素做key，需要注意的是，若选最左边的元素作为key，则需要right先寻找比a[key]小的元素（下面的代码即是以最左边的元素作为key），若选最右边的元素作为key，则需要left先寻找比a[key]大的元素。

选最左边的元素作为key，则先从右边开始寻找比a[key]小的元素，找到后再从左边开始寻找比a[key]大的元素，找到后交换。重复寻找和交换直到left和right相遇，将相遇处meet_i的元素与key位置的元素交换，则可达到meet_i左边的元素都比a[meet_i]小、meet_i右边的元素都比a[meet_i]大的目的。

//左右哨兵法
int PartSort1(int* a, int left, int right)
{
	//下面两行代码为优化，后文会讲到
	int midIndex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midIndex]);
	
	
	int key_i = left;
	while (left < right)
	{
		//right找小
		//从右边开始寻找比a[key]小的元素
		//注意先判断left < right，否则可能越界
		//注意a[right] >= a[key_i]的等号，否则可能死循环
		while (left < right && a[right] >= a[key_i])
			right--;

		//left找大
		//再从左边开始寻找比a[key]大的元素
		while (left < right && a[left] <= a[key_i])
			left++;

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

	//left == right
	int meet_i = left;
	Swap(&a[key_i], &a[meet_i]);

	return meet_i;
}

void QuickSort(int* a, int left, int right)
{
	//[left,right]区间内只剩一个或0个元素，即有序，不需要排
	if (left >= right)
		return;

	int mid = PartSort1(a, left, right);
	//mid位置已经是最终的位置，对[left,mid-1]和[mid+1,right]排序
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid + 1, right);
}

（2）挖坑法

选定最左边（最右边也可以，以左为例）为坑hole并保存a[hole]的值，right从右边开始找比a[hole]小的数，找到后用a[right]的值覆盖hole位置，并把hole改为right位置；left从左边开始找比a[hole]大的数，找到后用a[left]的值覆盖hole位置，并把hole改为right位置。循环直到left>=right，跳出循环后，设置left和right相遇的位置为meet_i，将最开始保存的a[hole]的值覆盖meet_i位置。单趟排序结束。

代码如下（示例）：

//挖坑
int PartSort2(int* a, int left, int right)
{
	//下面两行代码为优化，后文会讲到
	int mid = GetMidIndex(a, left, right);
	Swap(&a[left], &a[mid]);

	int hole = left;//选定最左边为坑hole
	int key = a[hole];//保存a[hole]的值
	while (left < right)
	{
		while (left < right && a[right] >= key)//right从右边开始找比a[hole]小的数
			right--;
		a[hole] = a[right];//找到后用a[right]的值覆盖hole位置
		hole = right;//把hole改为right位置

		while (left < right && a[left] <= key)//left从左边开始找比a[hole]大的数
			left++;
		a[hole] = a[left];//找到后用a[left]的值覆盖hole位置
		hole = left;//把hole改为right位置
	}
	a[hole] = key;//将最开始保存的a[hole]的值覆盖meet_i位置
	return hole;
}

void QuickSort(int* a, int left, int right)
{
	//[left,right]区间内只剩一个或0个元素，即有序，不需要排
	if (left >= right)
		return;

	int mid = PartSort2(a, left, right);
	//mid位置已经是最终的位置，对[left,mid-1]和[mid+1,right]排序
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid + 1, right);
}

2.非递归实现快速排序

代码如下（示例）：

void QuickSortNonR(int* a, int begin, int end)
{
	stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		//左右区间入栈
		int right = StackTop(&st);
		StackPop(&st);
		int left = StackTop(&st);
		StackPop(&st);

		int key = PartSort1(a, left, right);//得到key
		
		//左右区间出栈后子区间再入栈，子区间入栈后会一一对该区间排序
		
		//left和key - 1之间还有元素
		if (left < key - 1)
		{
			StackPush(&st, left);
			StackPush(&st, key - 1);
		}

		//key + 1之间和right之间还有元素
		if (right > key + 1)
		{
			StackPush(&st, key + 1);
			StackPush(&st, right);
		}
	}
	StackDestroy(&st);
}

3.优化：三数取中法

当待排序的序列为递减数列时，是最坏的情况，快速排序的效率达到最低，每次选取的key都是最大值或者最小值，所以在right或left寻找时不发生交换，遍历整个区间，时间复杂度退化为O(N^2)。

通过三数取中法选出最左边、中间位置和最右边三个数中间的值，之后与key交换，当碰到上述情况时直接变成最好的情况。

代码如下（示例）：

//三数取中，逻辑简单，但实现起来较为复杂
int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) >> 1;
	int num1 = a[left];
	int num2 = a[mid];
	int num3 = a[right];

	if (num1 > num2)
	{
		if (num2 > num3)//num1 > num2 > num3
			return num3;
		else//num2 <= num3 && num2 < num1
		{
			if (num1 > num3)//num1 > num3 > num2
				return num3;
			else//num3 > num1 > num2
				return num1;
		}
	}
	else//num1 <= num2
	{
		if (num1 > num3)//num2 > num1 > num3
			return num1;
		else//num2 > num1 && num3 > num1
		{
			if (num2 > num3)
				return num3;
			else
				return num2;
		}
	}
}

快速排序：

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

二、归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。若将两个有序表合并成一个有序表，称为二路归并。

1.递归

代码如下（示例）：

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;

	//从中间分开，递归使左右两段区间有序
	int mid = (left + right) >> 1;
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	//左右两段区间已经有序，排序使整个区间有序
	int begin1 = left, end1 = mid;//区间1
	int begin2 = mid + 1, end2 = right;//区间2
	int begin = begin1;
	int i = begin1;//tmp的起点

	//在两段区间中找小的值尾插
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
			tmp[i++] = a[begin1++];
		else
			tmp[i++] = a[begin2++];
	}

	//把两个区间其中一个区间剩余的数据拷贝到tmp中，下面两个循环只走一个
	while (begin1 <= end1)
		tmp[i++] = a[begin1++];
	while (begin2 <= end2)
		tmp[i++] = a[begin2++];

	//归并结束，把tmp中对应位置的数据全部拷贝回a数组
	for (i = begin; i <= end2; i++)
		a[i] = tmp[i];
}

void MergeSort(int* a, int n)
{
	//申请临时空间
	int* tmp = (int*)malloc(sizeof(int)* n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tmp);//归并子函数

	free(tmp);
}

2.非递归实现

代码如下（示例）：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)* n);
	int i = 0, gap = 1;//每组gap个元素
	while (gap < n)
	{
		for (i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;//区间1
			int begin2 = i + gap, end2 = i + 2 * gap - 1;//区间2
			
			//第二个小组的开头就超出数组范围，说明数组中只有第一个小组，而第一个小组已经是排好序的，直接退出
			if (begin2 >= n)
				break;
			
			//第二个小组末尾超出数组范围，修正它的末尾保证不越界
			if (end2 >= n)
				end2 = n - 1;

			//合并两个已经有序的区间
			int begin = begin1;
			int i = begin1;//tmp的起点
		
			//在两段区间中找小的值尾插
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
					tmp[i++] = a[begin1++];
				else
					tmp[i++] = a[begin2++];
			}
		
			//把两个区间其中一个区间剩余的数据拷贝到tmp中，下面两个循环只走一个
			while (begin1 <= end1)
				tmp[i++] = a[begin1++];
			while (begin2 <= end2)
				tmp[i++] = a[begin2++];
		
			//归并结束，把tmp中对应位置的数据全部拷贝回a数组
			for (i = begin; i <= end2; i++)
				a[i] = tmp[i];
		}
		gap *= 2;
	}
}

归并排序：

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

三、计数排序

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

代码如下（示例）：

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	int i, j;

	//找到最大值、最小值
	for (i = 0; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
	}

	int* count = (int*)malloc(sizeof(int)* n);//辅助空间
	memset(count, 0, sizeof(int) * n);
	int range = max - min + 1;//最大的数据和最小的数据的跨度
	for (i = 0; i < n; i++)
		count[a[i] - min]++;
	
	i = 0;
	for (j = 0; j < range; j++)
	{
		while (count[j]--)
			a[i++] = j + min;
	}

	free(count);
}

计数排序：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定

排序算法的比较

感谢阅读，如有错误请批评指正