排序的概念及其运用

排序的概念

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

排序运用

常见的排序算法

// 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void Quicksort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
// 归并排序递归实现
void MergeSort(int* a, int n)
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
// 计数排序
void CountSort(int* a, int n)
// 测试排序的性能对比
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);
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];
}
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();
QuickSort(a5, 0, N-1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
PRintf("InsertSort:%dn", end1 - begin1);
printf("ShellSort:%dn", end2 - begin2);
printf("SelectSort:%dn", end3 - begin3);
printf("HeapSort:%dn", end4 - begin4);
printf("QuickSort:%dn", end5 - begin5);
printf(";mergeSort:%dn", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}

排序OJ(可使用各种排序跑这个OJ) OJ链接 (插入、选择、冒泡、前后指针法超时)

插入排序

插入排序的思想就像我们打扑克牌，摸完所有牌之后，要将牌进行排序，通常都是将牌插在对应的位置

比如一个数组a,从a[0],a[1]…a[k],a[k+1]…一直到a[n]，使用插入排序的话，就是先将a[0],a[1]…a[k]看成一个有序数列，然后将a[k+1]与a[k]比较，如果比a[k]小，则继续向前比较，直到a[k]大于其中某个数，就将a[k]插在该数的后面

整体流程:

• 将a[0]看成有序数列，a[1]向前比较，再插入

• 将a[0],a[1]看成有序数列，a[2]向前比较，再插入

• 将a[0],a[1],a[2]看成有序数列，a[3]向前比较，再插入

• 将a[0],a[1],a[2],a[3]看成有序数列，a[4]向前比较，再插入

• …
• 将a[0],a[1],a[2],a[3]…a[k]看成有序数列，a[k + 1]向前比较，再插入

• …
• 将a[0],a[1],a[2],a[3]…a[k],a[k+1]…a[n-1]看成有序数列，a[n]向前比较，再插入

思路： 使用一个end来表示每次插入位置，每次需要插入的元素就在a[end]之后，也就是a[end]是小于需要插入的元素的

代码：

//插入排序  @R_591_1304@O(N^2)
void InsertSort(int* a, int n)
{
	if (n < 2)
		return;

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

		//两种情况
		if (end < 0)//元素插入到数组的第一位
			a[0] = tmp;
		else//元素插入到end之后
			a[end + 1] = tmp;
        
        //实际上，不加判断，直接写成a[end + 1]也是一样的，因为end<0时，也就是end == 1，end+1就是数组的第一个位置了
	}

}

插入排序的时间复杂度：最坏情况下：O(N^2 )，如果我们的插入排序是要排成升序，则完全是降序的情况下时间复杂度为O(N^2)

​ 最好情况：O(N)，即已经是有序的情况下，就只需要遍历数组，时间复杂度O(N)

希尔排序

希尔排序本质上是插入排序的变种，我们来看机组几组例子：

我们观察到这两个例子都是接近有序的，所以只移动了几次，时间复杂度近似为O(N)

希尔排序就是利用这个特点，先将数组排成近似有序的，再进行一次插入排序。

大致分为两个步骤：

1. 预排序
2. 插入排序

那么如何实现预排序呢？

可以利用一个间隙gap，每隔gap个元素分成一组，再对每组元素进行排序，最后即可得到一个接近有序的数组。

将数组分为gap部分:

然后蓝色的线为一组，红色的线为一组，绿色的线为一组，分别对三组数据进行插入排序，即为预排序过程。

预排序好后，就变成了下图的样子：

此时的数组就是一个接近有序的数组，再次对数组整体进行插入排序，得到有序数组。

实际上，当gap为1时，就可以将预处理过程看成是插入排序了。

基于以上分析，我们可以将gap设置为数组长度n的三分之一、四分之一或者五分之一都行，经过一轮预处理后，再对gap进行缩小，直到最后gap等于1，就可以看作是插入排序了。

关于代码里有几个问题需要大家回答：

1. 为什么gap要以gap = (gap / 3 + 1)的方式缩小而不是gap = gap / 3
2. 为什么for循环里循环条件要写成i < n - gap而不是i < n，更新条件是++i而不是i += gap呢？

代码：

void ShellSort(int* a, int n)
{
	int gap = n;//先初始化gap

	while (gap > 1)
	{
		gap = (gap / 3 + 1);//gap大约为数组长度的三分之一

		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)//查找插入的位置
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];/
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}

	}


}

问题一：如果使用gap = gap / 3的方式缩小gap的话，有可能就不能使gap缩小到1。比如n = 6时，一开始gap = 2，随后根据gap = gap / 3，gap就变成0了，就没有完成整体的插入排序，所以要使用gap = (gap / 3 + 1)的形式

问题二：因为我们的tmp是设置为a[end + gap]，而end == i，当tmp小于前面的元素时，就向前插入，所以只需要将i控制在n - gap就行。那么为什么更新条件是++i而不是i+=gap呢？如果是i+=gap的话，以上面的图为例，就只能对蓝色小组进行预排序，之后就结束循环了。

而++i的方式则是挨个处理蓝红绿三个小组，可以确保每个小组都被处理到。

选择排序

我们可以观察到，选择排序是遍历数组，选择一个最小的数，然后与数组开头元素交换，以此循环下去。

时间复杂度O(N^2)。

我们可以用一种更快的方式，但并不能改变时间复杂度：在找最小数的同时找最大数，将最大数放在数组末尾，最小数放在数组开头。我们是以下标来标记对应最大值最小值的位置的。

但是这样写有一个需要注意的地方，即当数组的开头就是最大数时，达不到我们想要的效果。比如[4,2,1,3]，最小值为1，最大值为4，我们先将最小值与数组开头元素交换，得到[1,2,4,3]，接下来我们还想将最大值与数组末尾元素交换，但此时，原本最大元素的位置以及不是最大值了，而是1，此时就需要更新最大值的位置：maxindex = minindex(新的4的位置)

既然当最大值在数组开头时需要处理，那当最小值在数组末尾时需要处理吗？以[2,4,3,1]为例，最小值为1，最大值为4，先将1和2交换，得到[1,4,3,2]，此时maxindex位置处的元素仍然是4，直接交换4，2即可，不需要进行特殊处理。

代码：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void SelectSort(int* a, int n)
{
	int left = 0;
	int right = n - 1;

	while (left < right)
	{
		int maxindex = left;//一开始初始化最大最小值均为数组开头元素
		int minindex = left;
		for (int i = left; i <= right; ++i)
		{
			if (a[maxindex] < a[i])//查找最大值
				maxindex = i;
			if (a[minindex] > a[i])//查找最小值
				minindex = i;
		}
		
        //将最大值最小值归位
		Swap(&amp;a[left], &a[minindex]);
		if (left == maxindex)
			maxindex = minindex;
		Swap(&a[right], &a[maxindex]);

		++left;
		--right;
	}
}

堆排序

在了解堆排序之前需要先了解一下什么是堆，堆就类似一棵二叉树。不过堆是相对更有序的二叉树，有大堆和小堆之分。

可以先了解一下作者的上一篇文章：堆的实现及应用

了解了堆后，如果我们想要实现排升序，就要先建大堆。

为什么建大堆而不是小堆呢？

我们来看建小堆的话是怎么一个情况：

以[43,12,3,77,14,2,10,56]为例

建好小堆后：[2,12,3,56,14,43,10,77]

堆顶最小的元素，所以我们需要拿出第二小的数，就要将2从堆中分离出来，也就是剩下的元素从成组成堆。2是根节点，将2脱离出来后，意味着又要重新建堆，时间复杂度O(N)，如果反复这样的话，整个排序的时间复杂度就为O(N^2)，堆的优点就没有被体现出来。

所以，要想排升序的话需要建大堆(排降序是小堆)

我们建好大堆后，堆顶就是最大的数了，将最大的数与堆底的数交换，将堆的大小减1，再进行向下调整，如此往复，当堆只剩下一个元素时，排序就完成了。

也许大家会觉得，那建小堆的话，也将堆顶与堆底的数据进行交换不就可以了。这么做确实可以完成排序，不过完成的是降序，因为最小值在数组末尾，然后依次类推…

整体过程如下：

代码：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y; 
	*y = tmp;
}

//向下调整算法
void AddJustDown(int*a, int n, int parent)
{
	int child = 2 * parent + 1;
	
	while (child < n)//控制孩子节点不能越界
	{	
		//将左右孩子中较小的与父亲比较
		//右孩子不能越界
		if ((child + 1) < n && a[child] < a[child + 1])
		{
			++child;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}

	}
}

//堆排序——s
void HeapSort(int* a, int n)
{
	//建大堆
	//时间复杂度O(n)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AddJustDown(a, n, i);
	}

	int end = n - 1;
	//总体时间复杂度O(n*LOGn)
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AddJustDown(a, end, 0);
		--end;
	}
}

冒泡排序

冒泡排序的思想类似于选择排序，冒泡是对数组里的元素逐一比较，如果前一个元素大于后一个元素，则调换两者的位置，以此类推，可以将数组中的最大值放到数组末尾，下一轮排序时数组末尾就不用再进行比较了。经过n-1轮调换，就可以将数组排好序。

两者的时间复杂度都为O(N^2)，但在数组接近有序的情况下，冒泡的效率是要高于选择排序的。因为冒泡可以对数组有序进行判断，如果有序就不再接着排序了。而选择排序是无法判断数组是否有序的，也就是需要无条件遍历数组。

代码：

void BubbleSort(int* a, int n)
{
	int i = 0;
	int j = 0;
	int flag = 0;//用来判断数组是否有序
	for (i = 0; i < n - 1; ++i)
	{
		flag = 0;
		for (j = 0; j < n - i - 1; ++j)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
	}
}

快速排序

快速排序有四种实现方法：

1. 左右指针法
2. 挖坑法
3. 前后指针法
4. 非递归实现

左右指针法

我们先解释左右指针法。

大概思路是选出一个key，key一般是最左边或者最右边的元素，将key放到正确的位置上去，比如key是第六大的数，就将key放在数组的第六个位置，而key左边的数小于key，右边的数大于key，依次再分别对左右两边数组进行递归，当数组缩小到只有1个或0个元素时，就停止递归。

所以我们可以定义一个左指针left，一个右指针right，right先从右向左查找小于key的元素，找到了就停下来，left就开始从左向右查找大于key的元素，找到了也停下来，再交换right、left处的元素。由此再继续right和left的查找，直到left与right相遇，此时将相遇处的元素与key交换，再进行递归。

我们必须要注意：相遇处的元素是一定小于key的，因为是right先走，如果是left先走就不是了。

观察一个示例：

right先走，找到比key(6)小的数字，也就是1，left再查找比key大的数字，也就是7

交换7和1的位置，再继续进行查找

再查找的话，right就指向了4，left再向右查找，此时left还未找到比key大的数字就与right相遇了，相遇元素就是4，4<6，交换4、6的位置。而此时，6的位置就被找好了，再对6左边的数组与右边的数组进行相同的处理即可完成排序。

我们看到，相遇元素4是小于key的，这不是巧合，因为是right先走，所以相遇的元素一定是right先找到的。

相遇时有两种情况：

1. 右遇左：

   a.数组有序

   b.左右位置的值刚进行交换，所以左指针指向的值小于key，而右指针向左没有找到小于key的元素，遇到左指针，所以相遇值小于key

2. 左遇右：右指针已经找到小于key的元素，左指针向右没有找到大于key的元素，遇见了右指针，所以相遇值小于key

但是，如果是left先走，相遇元素就一定大于key了，并且key要是最右边的元素。

由于有三种方法，我们将每种方法单独写成一个函数SingleWaySorting，再共用一个函数QuickSort包装进行递归。

看下面的代码，大家思考一下为什么这里的循环需要加上left < right的限制呢？

while (left < right && a[right] >= a[keyi])//查找小于key的元素
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])//查找大于key的元素
		{
			++left;
		}

代码：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//单趟排序——左右指针法
int SingleWaySorting1(int* a, int begin, int end)
{
	int left = begin + 1;
	int right = end;
	int keyi = begin;

	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])//查找小于key的元素
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])//查找大于key的元素
		{
			++left;
		}
		
        //交换left、right
		Swap(&a[left], &a[right]);
	}

	//相遇元素与key元素交换
	Swap(&a[left], &a[keyi]);

	return left;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	
	int keyi = SingleWaySorting1(a, begin, end);//接收key元素的位置，即分界位置
	QuickSort(a, begin, keyi - 1);//对key左边进行排序
	QuickSort(a, keyi+1, end);//对key右边进行排序

}

为什么要加left < right呢？

当数组有序时，我们看一下如果不加限制，会是什么结果？

right向左查找小于1的数

我们发现，如果不加限制的话，right会有越界的行为，所以加上限制是防止数组越界的现象发生。

同样，正是因为有序，快速排序的效率反而变低了，甚至是最坏的情况，该情况下时间复杂度为O(N^2)

当key刚好为数组有序情况下的中位数时，效率最高，时间复杂度为O(N * logN)

我们对上面两种情况进行分析：

当key刚好为数组有序情况下的中位数时

每次递归就是以key为分割点，将左右数组近似均等地分开，最后分开的形状就是一颗二叉树。N为数组的长度，所以树的高度就是logN

单趟排序的时间复杂度为O(N)，所以每一层的排序的时间复杂度总和为O(N)，而每一层的时间复杂度相加，就得到了O(N * logN)

当数组有序时，key为数组中最小的元素

同样，每一层单趟排序的时间复杂度为O(N)，共有N层，所以时间复杂度总和为O(N^2)

我们来看一下排序有序和无序数组的区别：

图中数字代表排序所用时间(单位：毫秒)，结果在releas版本下测量得到

我们看到，此时快排对有序数组的排序是用了1274毫秒的，而对一个随机的无序数组则用了6毫秒，差距是十分明显的。

既然这样，我们有没有什么办法来优化呢？

答案是：有的。

三数取中法

我们采用三数取中法就可以完成对有序数组排序的优化。

三数取中法的思路：对于数组a，我们取出数组的最左边的元素left，最右边的元素right以及中间的元素mid，然后取这三者中既不是最大、也不是最小的元素来作为key。

代码：

int GetMidIndex(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int mid = (left + right) / 2;

	if (a[left] > a[right])
	{
		if (a[mid] < a[right])
			return right;
		else if (a[mid] > a[left])
			return left;
		else
			return mid;
	}
	else//left<=right
	{
		if (a[mid] < a[left])
			return left;
		else if (a[mid] > a[right])
			return right;
		else
			return mid;
	}

}

加入到SingWaySorting1中：

int SingleWaySorting1(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int keyi = begin;//key的下标
    //将三数取中的结果与begin指向的元素交换
	Swap(&a[keyi], &a[GetMidIndex(a, begin, end)]);

	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])//查找小于key的元素
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])//查找大于key的元素
		{
			++left;
		}

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

	//相遇元素与key元素交换
	Swap(&a[left], &a[keyi]);

	return left;
}

这时再分别对有序和无序的数组排序：

现在我们看到，两者的差距只有几毫秒了，所以三数取中的优化效果是十分明显的。

接下来我们讲第二种快排思路：

挖坑法

挖坑法与左右指针法很类型，不过比较好理解。

我们同样取最左边或最右边的元素作为key，接下来的讲解以最左边元素作为key。

保存key的值，将key视为一个坑，随后也是用一个右指针right查找小于key的元素，找到后，将该元素填入到前面的key的坑中，此时right指向的地方就成为了一个新坑。再用左指针left查找大于key的元素，找到后，将该元素填入right指向的坑中，此时left指向的位置就变成了一个坑。随后再用右指针查找下一个小于key的元素…依次类推，当right、left相遇时，left指向的相遇处已经是hole了，将key填入相遇的位置处，就完成了单趟排序

以[3,1,7,4,5,2,6]为例，初始情况如下：

right向左查找小于3的数，也就是2，将2填入hole中，right指向的位置就变成了新的hole

left向右查找大于3的数，也就是7，将7填入hole中，left所指的位置就变成了新的hole

right再向左查找，发现left之后没有小于3的数了，就与left相遇了，再将key填入hole中，3的位置就被固定好了，于是就完成了单趟排序

代码：

int SingleWaySorting2(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int keyi = begin;
	Swap(&a[keyi], &a[GetMidIndex(a, begin, end)]);
	int tmp = a[keyi];

	while (left < right)
	{
		while (left < right && a[right] >= tmp)//查找小于key的数
		{
			--right;
		}
		//填坑
		a[keyi] = a[right];
		while (left < right && a[left] <= tmp)//查找大于key的数
		{
			++left;
		}
		//填坑
		a[right] = a[left];
		//更新坑
		keyi = left;
	}

	//将key填入相遇位置
	a[left] = tmp;
	
	return left;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	
	int keyi = SingleWaySorting3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);

}

最后我们来讲快排的最后一种思路：

前后指针法

前后指针法就是我们一开始的动图采用的方法。与前两种都有相似之处。

前后指针法有两种实现方式。

一种是key是第一个元素，一种是key是最后一个元素

两者思路相似

第一种：

第二种：

cur要从第一个元素开始，将小于key的元素放前面，大于key的元素抛后面

key还是最左边的值，设置前指针prev，后指针cur，cur和prev一开始保持一前一后的位置，prev指向数组首元素。

cur去找比key小的值，把小的放在前面，大的放后面，找到以后，++prev，再交换prev和cur对应位置处的值。当cur>end时，key与prev的值交换，单趟排序结束，

以[5,1,7,4,5,2,6]为例，初始情况如下：

cur查找小于5的数，也就是1，找到后，++prev，对cur和prev指向的值进行交换，此时他俩指向同一位置。

cur再向后找，找到了4，++prev，对cur和prev指向的值进行交换

cur再向后找，找到了2，++prev，对cur和prev指向的值进行交换

cur再向后已经找不到小于5的数了，于是cur>end，循环结束，key与prev的值互换。

这样就完成了单趟排序，再将key左右两边的数组进行递归，就完成了排序。

代码：

int SingleWaySorting3(int*a, int begin, int end)
{

	int cur = begin + 1;
	int prev = begin;
	int keyi = begin;

	while (cur <= end)
	{
		while (cur <= end && a[cur] >= a[keyi])
		{
			++cur;
		}
        
		if (cur <= end)//当cur>end时不需要再++，因为此时的prev要与key交换
		++prev;
		if (cur <= end && cur != prev)//当prev和cur指向同一元素时可以不进行交换
		{
			Swap(&a[prev], &a[cur]);
			
		}
		//交换完需要++cur，否则cur一直指向该位置，代码会陷入死循环
		++cur;
	}

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

	return prev;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	
	int keyi = SingleWaySorting3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);

}

方法二：

先看代码：

int SingleWaySorting4(int* a, int begin, int end)
{
	//因为key是数组末尾的元素，所以第一个元素也要经过判断
	int prev = begin - 1;
	int cur = begin;
	int keyi = end;

	while (cur <= end)
	{
		if (a[cur] >= a[keyi])
		{
			++cur;
		}

		if (cur <= end && a[cur] < a[keyi])
		{
			++prev;
			Swap(&a[prev], &a[cur]);
			++cur;
		}	

	}

		//最后prev指向的是小于key的元素，所以prev要++，指向大于等于key的元素，从而将key放到正确的位置
		++prev;
		Swap(&a[prev], &a[keyi]);
		return prev;
	
}

如果cur指向的元素大于key，则cur向后走，prev不动直到cur找到小于key的元素，prev++，此时prev指向的就是大于key的元素，两者交换，再继续查找。

当cur>end时跳出循环，此时prev指向的是小于key的元素，所以最后需要++，使其指向大于key的元素，再交换key和prev指向的元素，就可以使key放到正确的位置上。

但存在一种特殊情况，也就是key是最小的元素，所以key应该放到第一个位置。当循环结束时，prev还是等于begin - 1，所以++prev，prev就指向了第一个元素，从而交换元素，使key位于第一个位置。

因此，

		++prev;
		Swap(&a[prev], &a[keyi]);
		return prev;

这段代码起到了两个作用，处理了两种情况。

除了我们讲的三数取中可以优化快排，还有一种小区间优化法也可以对其进行优化。小区间优化法是减少递归调用的次数，现代cpu已经使递归的效率非常高了，递归程度太深时程序本身没问题，但是栈空间不够，导致栈溢出。

小区间优化法

小区间优化法是当递归至数组只有小部分元素时，比如10、20、30等等，我们就不再用快排了，而是选择用其他的排序，比如InsertSort

使用：

int SingleWaySorting3(int*a, int begin, int end)
{

	int cur = begin + 1;
	int prev = begin;
	int keyi = begin;

	while (cur <= end)
	{
		while (cur <= end && a[cur] >= a[keyi])
		{
			++cur;
		}
        
		if (cur <= end)//当cur>end时不需要再++，因为此时的prev要与key交换
		++prev;
		if (cur <= end && cur != prev)//当prev和cur指向同一元素时可以不进行交换
		{
			Swap(&a[prev], &a[cur]);
			
		}
		//交换完需要++cur，否则cur一直指向该位置，代码会陷入死循环
		++cur;
	}

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

	return prev;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	if (end - begin > 10)
    {
        int keyi = SingleWaySorting3(a, begin, end);
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi+1, end);
	}
    else
    {
        //a+begin是排序开始的地方
        //end-begin+1是排序的长度
        InsertSort(a, a + begin, end - begin + 1);
    }
	

}

非递归实现快排

非递归实现快排就需要我们借用栈来作为辅助了。

将每个数组的begin、end入栈，然后进行单趟排序得到排序后的key的位置，再pop掉begin、end。将被分割后的数组的begin、end入栈，再循环进行单趟排序。循环的终止条件是栈为空时。

代码：

Stack.h:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
#include<assert.h>

tyPEdef int tp;

typedef struct Stackmember {
	tp capacITy;
	tp top;
	tp* a;
}s;

//栈的初始化
void StackInit(s* phead);

//栈的摧毁
void StacKDEstroy(s* phead);

//进栈
void StackPush(s* phead, tp x);


//出栈
void StackPop(s* phead);

//返回栈顶数据
tp StackTop(s* phead);

//判断栈是否为空
bool StackEmpty(s* phead);

//返回栈的大小
tp StackSize(s* phead);

Stack.c：

#include"Stack.h"

void StackInit(s* phead)
{
	phead->a = (tp*)malloc(4 * sizeof(tp));
	if (phead->a == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	phead->capacity = 4;
	phead->top = 0;
}

void StackDestroy(s* phead)
{
	assert(phead != NULL);

	free(phead->a);
	phead->a = NULL;
	phead->top = phead->capacity = 0;
}

void StackPush(s* phead, tp x)
{
	assert(phead != NULL);

	if (phead->top == phead->capacity)//判断栈是否已满，满了就扩容
	{
		tp* tmp = (tp*)realloc(phead->a, 2 * (phead->capacity) * sizeof(tp));
		if (tmp == NULL)
		{
			perror("realloc");
			StackDestroy(phead);
			exit(-1);
		}

		phead->a = tmp;
		phead->capacity *= 2;
		tmp = NULL;
	}

	phead->a[phead->top] = x;
	phead->top++;
}


void StackPop(s* phead)
{
	assert(phead != NULL);
	assert(!StackEmpty(phead));

	phead->top--;
}

tp StackTop(s* phead)
{

	assert(phead != NULL);
	assert(!StackEmpty(phead));
	return phead->a[phead->top - 1];
}

//判断栈是否为空
bool StackEmpty(s* phead)
{
	return phead->top == 0;
}

tp StackSize(s* phead)
{
	assert(phead != NULL);
	assert(!StackEmpty(phead));
	return phead->top;
}

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//三数取中
int GetMidIndex(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int mid = (left + right) / 2;

	if (a[left] > a[right])
	{
		if (a[mid] < a[right])
			return right;
		else if (a[mid] > a[left])
			return left;
		else
			return mid;
	}
	else//left<=right
	{
		if (a[mid] < a[left])
			return left;
		else if (a[mid] > a[right])
			return right;
		else
			return mid;
	}

}


int SingleWaySorting1(int* a, int begin, int end)
{
	int left = begin;
	int right = end;
	int keyi = begin;
	Swap(&a[keyi], &a[GetMidIndex(a, begin, end)]);

	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])//查找小于key的元素
		{
			--right;
		}
		while (left < right && a[left] <= a[keyi])//查找大于key的元素
		{
			++left;
		}

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

	//相遇元素与key元素交换
	Swap(&a[left], &a[keyi]);

	return left;
}

void NonRecursiveQSort(int*a, int begin, int end)
{
	s s1;
	StackInit(&s1);
	StackPush(&s1, begin);
	StackPush(&s1, end);

	while (!StackEmpty(&s1))
	{
		int end = StackTop(&s1);
		StackPop(&s1);
		int begin = StackTop(&s1);
		StackPop(&s1);
		int keyi = SingleWaySorting1(a, begin, end);//用左右指针法排序

		if (begin < end)//当数组长度符合要求时将对应的begin和end入栈
		{
			if (begin < keyi - 1)//当数组长度符合要求时将对应的begin和end入栈
			{
				StackPush(&s1, begin);
				StackPush(&s1, keyi - 1);
			}
			if (keyi + 1 < end)//当数组长度符合要求时将对应的begin和end入栈
			{
				StackPush(&s1, keyi + 1);
				StackPush(&s1, end);
			}
			
		}

	}
	StackDestroy(&s1);
}

归并排序

原理：将子数组排成有序的，再将子数组合并。

思路：将数组分为两部分，分别对两部分进行排序，随后合并左右两部分(即合并两个有序数组)，但我们要一直向下二分，直到只剩下一个元素无法二分。

同样也是递归实现。

代码：

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

	int mid = (begin + end) >> 1;
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	int left1 = begin;
	int left2 = mid + 1;
	int i = begin;

	//合并有序数组
	while (left1 <= mid && left2 <= end)
	{
		if (a[left1] < a[left2])
			tmp[i++] = a[left1++];
		else
			tmp[i++] = a[left2++];
	}

	//处理剩余的元素
	while (left1 <= mid)
	{
		tmp[i++] = a[left1++];
	}

	//处理剩余的元素
	while (left2 <= end)
	{
		tmp[i++] = a[left2++];
	}

	//拷贝回原数组
	for (i = begin; i <= end; ++i)
	{
		a[i] = tmp[i];
	}

}

void MergeSort(int* a, int size)
{
	int* tmp = (int*)malloc(sizeof(int) * size);
	if (tmp == NULL)
	{
		printf("malloc errorn");
		exit(-1);
	}

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

	free(tmp);
}

非递归实现

非递归实现稍微复杂一点，因为有几种特殊情况需要考虑。

思路：先对数组两两一组排序，再四四一组排序，直到对整个数组完成排序。因此我们要用到一个熟悉的变量gap来进行分组。

gap一开始为1，所以一开始是两两一组的元素进行排序，排好之后，gap翻倍进行两两一组的排序，依次类推，当gap大于数组长度时就完成排序了

确认每一组的begin、end：

gap为1时：

gap为2时：

我们可以观察到，每一个进行排序的组begin、end都与下标i有关，对下一组排序时需要将i加上2*gap，这样就得到了新的begin，由此可以进行迭代排序，直到i大于数组长度

大致思路我们知道了，但是还有三种特殊情况需要我们处理：

1. 最后一组中，需要归并的两个区间中，第一个小区间存在，第二个不存在

   

2. 最后一组中，需要归并的两个区间中，第一个小区间存在但不足gap个

   

3. 最后一组中，需要归并的两个区间中，第一个小区间存在，第二个存在但不足gap个

   

这三种情况会出现数组越界访问的情况。

情况1、2其实本质是一样的，第一组已经有序了，可以直接停止归并。

情况3则需要将第二组的end更新成size-1(size是数组的长度)，再进行归并。

代码：

//复用了递归的一部分代码
void _IterateMergeSort(int*a,int begin1,int end1, int begin2, int end2, int*tmp)
{
	int left1 = begin1;
	int left2 =begin2;
	int i = begin1;

	//合并有序数组
	while (left1 <= end1 && left2 <= end2)
	{
		if (a[left1] < a[left2])
			tmp[i++] = a[left1++];
		else
			tmp[i++] = a[left2++];
	}

	//处理剩余的元素
	while (left1 <= end1)
	{
		tmp[i++] = a[left1++];
	}

	//处理剩余的元素
	while (left2 <= end2)
	{
		tmp[i++] = a[left2++];
	}

	//拷贝回原数组
	for (i = begin1; i <= end2; ++i)
	{
		a[i] = tmp[i];
	}
}

void IterateMergeSort(int*a, int size)
{
	int* tmp = (int*)malloc(sizeof(int) * size);
	if (tmp == NULL)
	{
		printf("malloc errorn");
		exit(-1);
	}

	int gap = 1;

	while (gap < size)
	{
		for (int i = 0; i < size; i+=2*gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;

			if (begin2 >= size)//说明此时已经不需要归并了，直接停止当前循环
			{
				break;
			}
			if (end2 >= size)//更新end2
			{
				end2 = size - 1;
			}

			_IterateMergeSort(a, begin1, end1, begin2, end2, tmp);
		}

		gap *= 2;
	}
	
	free(tmp);
}

归并排序的时间复杂度为O(N * logN)

内排序与外排序

内排序：指在排序期间数据对象全部存放在内存的排序。

外排序：指在排序期间全部对象太多，不能同时存放在内存中，必须根据排序过程的要求，不断在内，外存间移动的排序。

根据排序元素所在位置的不同，排序分: 内排序和外排序 。

归并排序既属于又属于内排序又属于外排序。

使用外排序的一道例题：

假设有10亿个整数，放到文件A中，但需要排好序，我们只能使用512M的内存。

思路：10亿个整数的大小为4G，我们可以将这4G内存分成8份，也就是512M到内存中进行排序，注意，在内存中排序时不能用归并排序，因为归并还需要O(N)的空间，512M装不下这么多数据，所以要使用其他不需要额外空间的排序。

先将512M数据排好序放到一个小文件中，再在内存中进行下一个512M的排序，也存放在一个小文件中，以此类推，需要创建8个小文件，再用归并排序将这8个小文件合并。

如上图所示，最后归并成一个4GB的文件，放在文件A中。

最后一种排序：

计数排序

计数排序的思想就是先遍历一遍数组，用另一个数组count统计出每个数字出现的次数，统计方法为数字本身作为count的下标，然后对该元素的统计就存放在改下标对应的元素中。

随后按照count的下标将这些数按个数输出，就得到了一个有序数列。

如果原数组的数字很大，使用数组下标对应数字的绝对映射方法的话，我们需要开辟的空间也会变得很大，所以我们使用相对映射。

代码：

//计数排序
void CountSort(int*a, int size)
{
	int max = a[0];
	int min = a[0];
	
	for (int i = 0; i < size; ++i)
	{
		if (max < a[i])
			max = a[i];
		if (min > a[i])
			min = a[i];
	}

	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));//要将count内的元素初始化为0

	for (int i = 0; i < size; ++i)
	{
		//相对映射在count中对应的下标为a[i] - min
		++count[a[i] - min];
	}

	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		while (count[i]--)//将每个元素打印出来
		{
			a[j++] = i + min;
		}
	}

}

时间复杂度O(N+range)

空间复杂度O(range)

计数排序适合一组范围比较集中的数据，如果范围集中，则效率很高，并且只适合整数。