数据结构之排序（下）

片头

嗨！小伙伴们，咱们又见面啦，在上一篇数据结构之排序(上)中，我们学习了直接插入排序、冒泡排序和希尔排序，今天我们继续学习排序这一块，准备好了吗？Ready Go ! ! !

一、选择排序

1.1 基本思想

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

1.2 直接选择排序

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

1.3 动图演示

通过动图，我们可以发现：

遍历一遍数组,我们找到最小值“2”,将“2”和第1个元素“3”进行交换,于是“2”成为第一个元素；

再次遍历“2”后面的元素,找到最小值“3”,将“3”和第2个元素“44”进行交换,“3”成为了第二个元素；

接着遍历“3”后面的元素,找到最小值“4”,将“4”和第3个元素“38”进行交换,“4”成为了第三个元素；

...........

当遍历到下标为n-2后面的元素时,说明前n-2个数已经有序,只需要将第n个元素（下标为n-1）和 第n-1个元素（下标为n-2）比较即可。

1.4 代码如下：

//交换
void Swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
 
//选择排序
void SelectSort(int* a, int n) {
	//j从下标为0开始，一直到下标为n-2
	for (int j = 0; j < n - 1; j++) {
	//将j后面的元素依次和j指向的元素进行比较
		for (int i = j+1; i < n; i++) {
	//如果后面的数比j指向的元素小，进行交换
			if (a[i] < a[j]) {
				Swap(&a[i], &a[j]);
			}
		}
	}
}

我们还可以进行算法优化，每次遍历同时选出最小值和最大值。

①定义一个变量begin,初始时指向下标为0的位置；定义一个变量end,初始时指向下标为n-1的位置。

②在begin~end这个区间，我可以遍历一遍，同时选出最小的和最大的，把最小的值放在最左边，把最大的值放在最右边，然后将begin和end同时往前挪动一个位置，再去这个区间里面选出最小值和最大值 （假设最小值和最大值都为第一个元素，将剩余的元素依次和第一个元素进行比较）

③当begin和end相遇时，循环结束

先写一个容易犯错的代码~

//交换
void Swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
 
//选择排序
void SelectSort(ElemType* a, int n) {
	int begin = 0;   //begin指向下标为0的位置
	int end = n - 1; //end指向下标为n-1的位置
 
	while (begin < end) //当begin和end相遇时,循环结束
	{
		int mini = begin;//假设最小值的下标为begin
		int maxi = begin;//假设最大值的下标为begin
		for (int j = begin + 1; j <= end; j++)
		{
			if (a[j] < a[mini]) {
			//将后面的值依次与a[mini]进行比较,选出最小值的下标
			//更新mini
				mini = j;
			}
			if (a[j] > a[maxi]) {
			//将后面的值依次与a[maxi]进行比较,选出最大值的下标
			//更新maxi
				maxi = j;
			}
		}
		Swap(&a[begin], &a[mini]);//将mini位置的值和begin位置的值进行交换
		Swap(&a[end], &a[maxi]);  //将maxi位置的值和end位置的值进行交换
		begin++;//每交换完一次,begin就自增一次
		end--;  //每交换完一次,end就自减一次
	}
}

测试一下:

 我们依次将每一次比较的结果打印一遍:

通过对比,我们可以发现,第四次的比较出现了问题,应该是"4"和"6","4"应该在"6"的前面。这是哪里出现问题了呢?

由图可知,begin指向下标为3的位置,maxi也指向下标为3的位置; end指向下标为5的位置,mini也指向下标为5的位置。①先将begin位置的值和mini位置的值进行交换,也就是 a[3] = 4, a[5] = 6。②再将end位置的值和maxi位置的值进行交换,(这里的maxi仍然指向下标为3的位置)交换完毕后, a[3] = 6, a[5] = 4。

 因此,当maxi和begin重合的时候,将begin位置的值和mini位置的值进行交换,max就被换到了下标为mini的位置。因此maxi等于mini。

1.5 优化代码如下：

//交换
void Swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
 
//选择排序优化版
void SelectSort1(int* a, int n) {
	int begin = 0;	//begin初始时指向下标为0的位置
	int end = n - 1;//end初始时指向下标为n-1的位置
 
	//当begin和end相遇时，循环结束
	while(begin < end){
	int mini = begin;//假设最小值的下标为begin
	int maxi = begin;//假设最大值的下标为begin
	for (int i = begin + 1; i <= end; i++) {
	//将后面每一个值依次和第一个值进行比较,选出最小的值
		if (a[i] < a[mini]) {
				mini = i;
		}
	//将后面每一个值依次和第一个值进行比较,选出最大的值
		if (a[i] > a[maxi]) {
				maxi = i;
		}
	}
	//将最小的数和下标为begin位置的值进行交换
	//将最小的数放在最左边
		Swap(&a[begin], &a[mini]);
	//如果maxi和begin重叠,说明此时maxi已经被换走了
	//此时maxi为mini
		if (maxi == begin) {
			maxi = mini;
		}
	//将最大的数和下标为end位置的值进行交换
	//将最大的数放在最右边
		Swap(&a[end], &a[maxi]);
	//每交换完一次,将begin和end同时往前挪动一个位置
		begin++;
		end--;
	}
}

---

二、堆排序 

堆排序（HeapSort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，是选择排序的一种，通过堆来进行选择排序。

在前面堆排序以及TOP-K问题这一章中，我们已经介绍过堆排序了，这里不再重复赘述。

2.1 基本思想

（1）先建堆，升序建大堆，降序建小堆

（2）将堆顶元素和堆尾元素互换，并且将堆尾元素不看作堆里面。

（3）此时除了第一个元素（堆顶元素）以外，都满足堆的特性，通过向下调整算法调整成新的堆，重复操作（2）直至序列有序。

2.2 动图演示

 2.3 代码如下：

//将数据类型int重命名为ElemType,方便以后修改
typedef int ElemType;
//堆的结构体类型
typedef struct Heap {
	ElemType* arr;
	int capacity;
	int size;
}Heap;
 
//交换
void Swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
 
//向下调整算法（大堆）
void AdjustDown(ElemType* arr, int size, int parent) {
	assert(arr);
	int child = parent * 2 + 1;//假设左孩子比右孩子大
	while (child < size) 
	{		//还没有遍历到叶子结点的时候，进入循环
		if (child + 1 < size && arr[child + 1] > arr[child])
		{	//如果右孩子存在，并且右孩子的值大于左孩子
			child = child + 1;
		}
		if (arr[child] > arr[parent])
		{	//如果子节点大于父节点，交换
			Swap(&arr[parent], &arr[child]);
			parent = child;//将子节点赋给父节点
			child = parent * 2 + 1;//寻找下一个子节点
		}
		else
		{	//如果父节点大于子节点，退出循环
			break;
		}
	}
}
 
//堆排序
void HeapSort1(int* a, int n) {
	assert(a);//断言，防止传入空指针
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) 
	{	//从最后一个结点的父节点开始，一直到根节点结束
		AdjustDown(a, n, i);//向下调整算法，调整成大堆
	}
 
	//这里的n-1有2层含义： 
	//①数组最后一个元素的下标为n-1
	//②数组总共有n个数，交换后将最后一个值不看作堆里面，共n-1个数
	int end = n - 1;
	while (end > 0) {
		Swap(&a[0], &a[end]);//将首尾元素交换
		AdjustDown(a, end, 0);//向下调整算法，从下标为0的元素开始
		end--;//每交换完一次，都要把最后一个数不看作堆里面
	}
}

---

三、快速排序

3.1 基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为: 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成2个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

简而言之：

（1）任选待排序序列中的某元素作为基准值，按照该值通过单趟排序将待排序的序列分为左右两个子序列，左子序列中的元素均小于基准值，右子序列中的元素均大于基准值（升序）

（2）分别对左右两个子序列重复步骤1，直至序列有序

3.2 单趟排序的实现

不同版本的快排核心思想是一样的，区别在于单趟排序的方式不同

3.2.1 hoare版本

大致思路

（1）选定待排序序列头部（或尾部）的元素作为key值，保存下标

（2）扫描待排序序列，一个从左到右寻找比key大的值，一个从右到左寻找比key小的值，找到后，将二者交换。

（3）当待排序序列扫描结束后，将序列头部的key与left位置处的元素交换。

3.2.2 动图演示

我们逐步分析：

第一步：

第二步：R往左走，找比key小的值，如果找到了，就停下

第三步：L往右走，找比key大的值，如果找到了，就停下，此时交换L和R的值

第四步：R再次往左移动，找比key小的值，如果找到了，就停下

第五步：L继续往右移动，找比key大的值，如果找到了，就停下，此时交换L和R的值

第六步：R向继续左移动，找比key小的值，如果找到了，就停下；

L向继续右移动，找比key大的值。此时L和R相遇，将该位置的值和key位置的值进行交换。

至此，第一趟排序结束。以key为分界线，左边的值比key小，右边的值比key大

3.2.3 代码如下：

//交换
void Swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
 
//单趟快速排序
void PartSort(int* a, int left, int right) {
//left从待排序序列头部往后走,right从待排序序列尾部往前走
 
	//初始时,key为第一个元素,keyi表示第一个元素的下标
	int keyi = left;
	//当left>=right时,单趟排序结束
	while (left < right) {
	//right位置的值大于或等于keyi位置的值时,往前走
		while (left < right && a[right] >= a[keyi]) {
			right--;
		}
	//left位置的值小于或等于keyi位置的值时,往后走
		while (left < right && a[left] <= a[keyi]) {
			left++;
		}
	//此时right位置的值比keyi位置的值小,left位置的值比keyi位置的值大
	//将二者交换
		Swap(&a[left], &a[right]);
	}
	//此时left和right相遇
	//将left指向的值和keyi指向的值进行交换
	Swap(&a[keyi], &a[left]);
}

 既然单趟快速排序我们已经实现了，那么整体的快速排序我们怎么实现呢？

我们再来回顾一下单趟排序的意义：①把key放到了最终位置②左边比key小③右边比key大

整体排序的思路： 以key为分界线，如果左边有序，右边也有序，排序就排完了，因为key自己到了最终位置，不需要再挪动了。

我们再回顾一下快速排序的定义：它是一种二叉树结构的交换排序方法。

Q1: 为啥它是二叉树结构的排序呢？

我们回想一下二叉树的前序遍历，先访问根，再访问左子树，再访问右子树。这里虽然不是二叉树，但它的结构和二叉树很相似。先单趟排序，排好序后，把一个值放在了它正确的位置，留下了左区间，留下了右区间，如果左区间和右区间都有序了，整个区间就有序了。

Q2: 怎么让左区间和右区间有序呢？

左边再继续选key,递归下来，也走刚才一样的单趟排序。利用分治思想，分治，分治，分而治之，先走左边，再走右边。左边选出了key的值，记录key值的下标keyi，right先走，寻找比key小的值，如果找到了，就停下；left再走，寻找比key大的值，如果找到了，此时发生交换。如果left和right相遇了，将left位置的值和keyi位置的值发生交换，key就排到了它正确的位置。左区间有序了，再递归右区间，直到左右区间都有序。

3.3 快排代码如下：

//交换
void Swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
 
//快速排序
void QuickSort(int* a, int left, int right) {
	//区间只有1个值或者不存在就是最小子问题,直接返回
	if (left >= right) {
		return;
	}
	//初始时,key为第一个元素,keyi表示第一个元素的下标
	int keyi = left;
	//因为后面left和right会发生变化,因此用变量保存起来
	int begin = left;
	int end = right;
	//当left>=right时,单趟排序结束
	while (left < right) {
	//right位置的值大于或等于keyi位置的值时,往前走
		while ( left < right && a[right] >= a[keyi]) {
			right--;
		}
	//left位置的值小于或等于keyi位置的值时,往后走
		while (left < right && a[left] <= a[keyi]) {
			left++;
		}
	//此时right位置的值比keyi位置的值小,left位置的值比keyi位置的值大
	//将二者交换
		Swap(&a[left], &a[right]);
	}
	//此时left和right相遇
	//将left指向的值和keyi指向的值进行交换
	Swap(&a[keyi], &a[left]);
	//交换完毕后,left的位置就是keyi的位置
	keyi = left;
	//[begin keyi-1]keyi[keyi+1 end]
 
	//将keyi的左区间进行排序
	QuickSort(a, begin, keyi - 1);
	//将keyi的右区间进行排序
	QuickSort(a, keyi + 1, end);
}

 首先，我们假设第一个元素确定为关键值key。这样做的目的：找到key的正确位置。第一个left给keyi， 将第一个元素的下标给keyi，然后right从后往前依次寻找比key小的值，left从前往后依次寻找比key大的值，找到了之后，left位置的值和right位置的值进行交换，一直到left和right相遇。

当left和right相遇时，将left位置的值和keyi位置的值进行交换，key就到了正确的位置，keyi也应该跟着发生变化，keyi就是现在left的位置。（第二次就是相遇的位置）

再让key的左区间和key的右区间有序，整个数组就有序了。

于是利用分治思想，先递归key的左区间，确定新的关键字key（左边第一个元素），以及关键字key的位置keyi，继续让left赋给keyi，此时的left是传递过来的值。然后再次让key回到正确的位置，keyi也应该跟着发生变化，keyi就是原来left的位置。（第二次就是相遇的位置）

左区间有序后，再递归key的右区间.......（这里不再重复赘述）

3.4 优化快速排序

那么快速排序的时间复杂度怎么计算呢?

快速排序的时间复杂度可以通过递归树的方法来推导。

    简单回顾: 快速排序的基本思想是：首先选择一个基准元素（通常选择第一个元素），然后将数组分为小于等于基准元素的子数组和大于基准元素的子数组。然后对这两个子数组分别进行快速排序。重复以上步骤直到数组完全有序。

    在每一次划分操作中，需要遍历整个数组来将元素划分到两个子数组之中。如果每次划分操作都将数组分成两个近乎相等的部分，那么总共需要进行log(n)次划分操作，其中n为数组的长度。而每次划分操作的平均时间复杂度为O(n)。

    然而，快速排序的时间复杂度并不完全由划分的次数决定，还受到划分的质量影响。如果每次划分都能将数组平均地分成两个近乎相等的部分，那么快速排序的时间复杂度为O(nlog(n))。但是，如果每次划分都将数组划分成一个较小的部分和一个较大的部分，那么快速排序的时间复杂度将接近于O(n^2)。

    因此，快速排序的时间复杂度的最坏情况为O(n^2)，平均情况为O(nlog(n))。通常情况下，快速排序的性能是非常好的，因此它是一种常用的排序算法之一。

那么,我们怎么避免快排的时间复杂度达到O(n^2)呢？

   方案一: 随机选key

   方案二: 三数取中选key

   方案三: 小区间优化

方案一:   随机选key

因为快排选key,一般选首/尾,如果是有序,首/尾都是最小的。因此,我们在[left,right]这个区间里面选取key,代码如下；

//交换
void Swap(int* a,int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
int randi = rand()%(right-left+1);   //[left,right]-->[0,right-left]-->right-left+1
randi = randi+left;                  //最终的结果再加上第一步减去的值
Swap(&a[left],&a[randi]);            //将这个随机的下标的元素和第一个下标的元素进行交换
int keyi = left;                     //再将left赋给keyi

方案二:   三数取中选key

   每次选择keyi的时候,如果这个keyi越接近中间,递归深度越接近logn,因此我们想到了三数取中的方法,这个方法是针对随机和有序综合而言的说法。

   我们定义left,mid,right这三个下标,取"中"的意思是: 选取这3个下标对应的值不是最大也不是最小的,大小是中间的那个值。这样做的优点: ①如果数组中的数字是无序的,三数取中可以保证取到的数字不是最小②如果数组中的数字是有序的,mid下标对应的这个值一定是中位数。

三数取中的代码如下:

//交换
void Swap(int* a,int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
//三数取中
int GetMidi(ElemType* a, int left, int right) {
	int mid = (left + right) / 2;
	if (a[left] < a[mid]) {
		if (a[mid] < a[right]) {
			return mid;
		}
		else if (a[right] < a[left]) {
			return left;
		}
		else {
			return right;
		}
	}
	else //a[left]>a[mid]
	{
		if (a[mid] > a[right]) {
			return mid;
		}
		else if (a[right] > a[left]) {
			return left;
		}
		else {
			return right;
		}
	}
}
 
 
void QuickSort(ElemType* a, int left, int right) {
    //如果区间只有一个值或者不存在就是最小子问题
	if (left >= right) {
		return;
	}
 
	//int keyi = left;
	int begin = left;
	int end = right;
 
	//随机选keyi
	//[left,right]-->[0,right-left]-->right-left+1
	//int randi = rand() % (right - left + 1);
	//randi = randi + left;
	//Swap(&a[left], &a[randi]);
	//int keyi = left;
 
 
	//三数取中
	int midi = GetMidi(a, left, right);//获取大小是中间值的下标
	Swap(&a[left], &a[midi]);//将第一个元素和中间值进行交换
	int keyi = left;//将left赋给keyi
 
	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[keyi], &a[left]);
	keyi = left;
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

方案三:  小区间优化

   如果区间元素个数比较少,我们可以选择走直接插入排序。小区间优化可以把递归次数减少，减少80%-90%的递归。

  快速排序在排序一个数据量为100万的无序序列时只需要递归20层，但排序一个8个数据的无序序列时就要递归3层。

  在递归出的二叉树结构中，最底部的三层的递归次数竟然占用了全部递归次数的87.5%!

因此我们可以对递归实现快排进行优化，当区间的数据量较小时，转变为直接插入排序方法。

本质上是为了减少递归调用次数来提高效率，这里我们可以使用直接插入排序来排序数据量较小的区间。

  代码如下:

//快速排序
//整体
//小区间优化
 
//交换
void Swap(int* a,int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
void QuickSort(ElemType* a, int left, int right) {
    //如果区间只有一个值或者不存在就是最小子问题
	if (left >= right) {
		return;
	}
 
	//小区间走插入排序,可以减少90%的递归
	if (right - left + 1 < 10) {
		InsertSort(a + left, right - left + 1);//因为表示的是一个区间,所以是a+left
	}
	else {
		int keyi = left;
		int begin = left;
		int end = right;
 
		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[keyi], &a[left]);
		keyi = left;
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

3.5 挖坑法

3.5.1 基本思想

(1)将待排序序列头部的元素存放到一个临时变量中作为key值，将key值原先的位置作为坑位

(2)从右往左寻找比key小的值，找到后将其填入坑中，并且其原来的位置成为新的坑

(3)从左往右寻找比key大的值，找到后将其填入坑中，并且其原来的位置成为新的坑

(4)重复步骤2~3直到待排序序列扫描完毕

(5)最后将key值填入坑中，返回key值下标

3.5.2 动图演示

3.5.3 代码如下

①单趟

//快速排序
//挖坑法
//单趟
void QuickSort(ElemType* a, int left, int right) {
	int temp = a[left];//将数组的第一个元素保存到temp临时变量中
	int hole = left;   //将left位置标记为hole
 
	while (left < right)//当left和right相遇时,循环结束
	{
		while (left < right && a[right] >= temp) //right先走,找比temp小的值
		{
			right--;
		}
		a[hole] = a[right];	//当right遇到比temp小的值,将这个值放入下标为hole的位置
		hole = right;	    //更新hole的位置
		while (left < right && a[left] <= temp) //left再走,找比temp大的值
		{
			left++;
		}
		a[hole] = a[left]; //当left遇到比temp大的值,将这个值放入下标为hole的位置
		hole = left;	   //更新hole的位置
	}
	a[hole] = temp;//当left和right相遇时,将temp放入下标为hole的位置
}

②整体

//快速排序
//挖坑法
//整体
void QuickSort(ElemType* a, int left, int right) {
    //如果区间只有一个值或者不存在就是最小子问题
	if (left >= right) {
		return;
	}
 
	int temp = a[left];//将数组的第一个元素保存到temp临时变量中
	int hole = left;   //将left位置标记为hole
    int keyi = left;
	int begin = left;
	int end = right;
 
 
	while (left < right)//当left和right相遇时,循环结束
	{
		while (left < right && a[right] >= temp) //right先走,找比temp小的值
		{
			right--;
		}
		a[hole] = a[right];	//当right遇到比temp小的值,将这个值放入下标为hole的位置
		hole = right;	    //更新hole的位置
		while (left < right && a[left] <= temp) //left再走,找比temp大的值
		{
			left++;
		}
		a[hole] = a[left]; //当left遇到比temp大的值,将这个值放入下标为hole的位置
		hole = left;	   //更新hole的位置
	}
	a[hole] = temp;//当left和right相遇时,将temp放入下标为hole的位置
	keyi = left;
	//[begin,keyi-1]keyi[keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

3.6 前后指针法

3.6.1 基本思想

(1)prev指针指向待排序数组的开头，cur指针指向prev的下一个位置,将数组第一个元素作为key值

(2)cur指针向后寻找比key小的值，如果找到了,prev指针向后走一步,同时将prev指向的元素和cur指向的元素进行交换，cur指针继续往后走

(3)cur指针如果遇到了比key大的值,则cur指针继续往后走

(4)重复步骤2~3直到cur指针走到结尾，将key值与prev位置的值交换并将prev作为新的keyi，递归左区间和右区间，直到数组完全有序。

3.6.2 动图演示

3.6.3 代码如下

①单趟

//快速排序
//前后指针法
//单趟
 
//交换
void Swap(int* a,int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
void QuickSort(ElemType* a, int left, int right) {
	int keyi = left;//将left位置标记为keyi
	int prev = left;//prev指针指向left
	int cur = prev + 1;//cur指针指向prev的下一个位置
 
	while (cur <= right)//当cur指针走出数组的下标范围时,循环结束
	{
		if (a[cur] < a[keyi]) //如果cur值比keyi值小
		{
			prev++;//prev向后走一步
			Swap(&a[prev], &a[cur]);//交换
			cur++;//cur向后走一步
		}
		else  //如果cur值比keyi值大
		{
			cur++;//cur向后走一步
		}
	}
}

emmmm,代码还可以优化一下!

  因为，不管pcur值是否比key值大，pcur都需要往后走一步，因此，我们可以省略else这个条件，单独把cur++这个语句拎出来~

//快速排序
//前后指针法
//单趟
 
//交换
void Swap(int* a,int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
void QuickSort(ElemType* a, int left, int right) {
	int keyi = left;//将left位置标记为keyi
	int prev = left;//prev指针指向left
	int cur = prev + 1;//cur指针指向prev的下一个位置
 
	while (cur <= right)//当cur指针走出数组的下标范围时,循环结束
	{
		if (a[cur] < a[keyi]) //如果cur值比keyi值小
		{
			prev++;//prev向后走一步
			Swap(&a[prev], &a[cur]);//交换
		}
			cur++;//cur向后走一步
	}
}

  我们还可以再优化，因为当prev和pcur指向同一块地址时，是不需要发生交换的。只有当prev和pcur指向不同的地址空间时，需要发生交换。

//快速排序
//前后指针法
//单趟
 
//交换
void Swap(int* a,int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
void QuickSort(ElemType* a, int left, int right) {
	int keyi = left;//将left位置标记为keyi
	int prev = left;//prev指针指向left
	int cur = prev + 1;//cur指针指向prev的下一个位置
 
	while (cur <= right)//当cur指针走出数组的下标范围时,循环结束
	{
       //如果cur值比keyi值小,并且prev和cur指向的不是同一块地址空间
		if (a[cur] < a[keyi] && ++prev!= cur) 
			Swap(&a[prev], &a[cur]);//交换
		
		cur++;//cur向后走一步
	}
}

OK，单趟的前后指针法的快速排序已经写好啦，那么整体的代码是怎样的呢？

//快速排序
//前后指针法
//整体
 
//交换
void Swap(int* a,int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
void QuickSort(ElemType* a, int left, int right) {
	//如果区间只有一个值或者不存在就是最小子问题
	if (left >= right) {
		return;
	}
 
	int keyi = left;//将left位置标记为keyi
	int prev = left;//prev指针指向left
	int cur = prev + 1;//cur指针指向prev的下一个位置
 
	while (cur <= right)//当cur指针走出数组的下标范围时,循环结束
	{
		if (a[cur] < a[keyi] && ++prev != cur) //如果cur值比keyi值小,并且prev和cur指向的不是同一块地址空间
			Swap(&a[prev], &a[cur]);//交换
 
		cur++;//cur向后走一步
	}
	Swap(&a[keyi], &a[prev]);		//将key值和prev值进行交换
	keyi = prev;					//prev作为新的keyi
 //[left,keyi-1]keyi[keyi+1,right]
	QuickSort(a, left, keyi - 1);	//递归左区间
	QuickSort(a, keyi + 1, right);	//递归右区间
}

3.7 递归实现快速排序

   快速排序是一种二叉树结构的交换排序方法，因此我们可以用递归来实现。完整代码如下：

//快速排序
void QuickSort(ElemType* a, int left, int right) {
	//如果区间只有一个值或者不存在就是最小子问题
	if (left >= right) {
		return;
	}
	int keyi = PartSort(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

3.8 非递归实现快速排序

我们都知道，实现快速排序普遍采用递归的方法，但是有一个缺陷: 如果递归的深度太深，容易出现栈溢出。因此，我们可以尝试采用非递归的方法

非递归的方式需要用到栈，通过对待排序区间的下标的压栈和出栈来实现快排

3.8.1 基本思想

(1)首先将待排序序列尾部的下标压入栈中,再将头部的下标压入栈中（因为后面出栈要先取头部再取出尾部，栈的特性是先进后出）

(2)取两次栈顶元素，分别取出序列头部和尾部的下标，对这一区间进行单趟排序后获取key值的下标

(3)当key值不与原区间头部或尾部相邻时，以key值为分界线将先前的区间拆分成两个部分，分别压入栈中。

(4)重复步骤2~3直到栈为空

3.8.2 代码如下

//快速排序
//非递归
void QuickSortNonR(ElemType* a, int left, int right) {
	Stack st;			  //创建一个栈
	StackInit(&st);		  //对这个栈进行初始化
	StackPush(&st, right);//将这个区间的结束位置先入栈
	StackPush(&st, left); //将这个区间的起始位置入栈
 
	while (!StackEmpty(&st)) //当栈为空时,循环结束
	{
		//先出栈的元素为起始位置
		int begin = StackTop(&st);
		StackPop(&st);
 
		//后出栈的元素为结束位置
		int end = StackTop(&st);
		StackPop(&st);
 
		//前后指针法
		//单趟
		int keyi = begin;
		int prev = begin;
		int cur = prev + 1;
 
		while (cur <= end) {
			if (a[cur] < a[keyi] && ++prev != cur) {
				Swap(&a[prev], &a[cur]);
			}
			    cur++;
		}
		Swap(&a[keyi], &a[prev]);
		keyi = prev;
		
	//[begin,keyi-1]keyi[keyi+1,end]
    //这里不是递归,因此利用栈先进后出的性质
    //先将keyi的右区间入栈
    //再将keyi的左区间入栈
 
		if (keyi + 1 < end)        //keyi+1不与end重合,意味着这个区间至少有2个元素
        {
			StackPush(&st, end);
			StackPush(&st, keyi + 1);
		}
	
		if (keyi - 1 > begin)      //keyi-1不与begin重合,也就是这个区间至少有2个元素
        { 
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}
	StackDestroy(&st);//销毁栈
}

具体有关栈的实现可以前往数据结构之栈查看（点击蓝色的字体可以跳转到相应的文章喔！）

---

四、归并排序

4.1基本思想

归并排序的核心思想:  分治

分治就是将一个复杂的问题分解成若干个子问题，子问题可以再分解成更小子问题，直到最后子问题可以简单分解。在求二叉树的节点个数和二叉树的高度时，我们也使用过这个思想。

将待排序的序列分解成2个子序列，再将子序列继续分解，直到每个子序列中只有1个元素，此时默认有序。再将有序的子序列逐渐归并到一起。

若将2个有序子序列合并成一个序列，称为二路归并。归并排序的逻辑图如下:

(1) malloc一块和待排序序列大小相同的空间，用来临时存放归并后的序列

(2)通过递归或迭代将待排序序列拆分成多个子序列

(3)子序列间两两归并到开辟出的空间中，2个子序列间的元素依次进行比较,取小的尾插到temp数组

(4)将归并后的子序列用memcpy拷贝到原序列中

(5)重复上述操作直到数组有序

4.2 动图演示

4.3 递归实现归并排序 

大致思路:

(1)通过递归将待排序序列不断对半分，直到分出的子序列中只有1个元素

(2)计算出相邻两个子序列区间的边界，对二者进行归并

比如:

第一次:

a[begin1]<a[begin2],将a[begin1]元素放入temp数组。操作完毕后,begin1往后走一步

第二次:

a[begin2]<a[begin1],将a[begin2]元素放入temp数组。操作完毕后,begin2往后走一步

第三次:

a[begin2]<a[begin1],将a[begin2]元素放入temp数组。操作完毕后,begin2往后走一步

第四次:

a[begin2]<a[begin1],将a[begin2]元素放入temp数组。操作完毕后,begin2往后走一步

第五次:

a[begin1]<a[begin2],将a[begin1]元素放入temp数组。操作完毕后,begin1往后走一步

第六次:

a[begin1]<a[begin2],将a[begin1]元素放入temp数组。操作完毕后,begin1往后走一步

第七次:

a[begin2]<a[begin1],将a[begin2]元素放入temp数组。操作完毕后,begin2往后走一步

第八次:

此时begin2已经超出end2，恰好begin1==end1,将a[begin1]放入temp数组

4.4 代码如下

我们不能每次递归都开辟一次空间，所以需要将主要的代码都放到子函数中，对子函数进行递归

//归并排序
//用递归实现归并排序
void _MergeSort(ElemType* a, int begin, int end, int* temp) {
	//如果区间只有1个值,直接返回
	if (begin == end) {
		return;
	}
 
	//mid为中间元素的下标
	int mid = (begin + end) / 2;
	//[begin,mid][mid+1,end]
	_MergeSort(a, begin, mid, temp);  //递归左区间
	_MergeSort(a, mid + 1, end, temp);//递归右区间
 
	//归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	//依次比较,取小的尾插到temp数组
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {
			temp[i++] = a[begin1++];
		}
		else {
			temp[i++] = a[begin2++];
		}
	}
	//如果begin1数组最后木有走完,直接尾插到temp数组的后面
	while (begin1 <= end1) {
		temp[i++] = a[begin1++];
	}
	//如果begin2数组最后木有走完,直接尾插到temp数组的后面
	while (begin2 <= end2) {
		temp[i++] = a[begin2++];
	}
	//最后将排好序的temp数组拷贝回a数组,拷贝元素的数量为end-begin+1
	memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}
 
void MergeSort(ElemType* a, int n) {
	//开辟一个temp数组存放元素
	int* temp =(int*) malloc(sizeof(int) * n);
	if (temp == NULL) {
		perror("malloc fail!\n");
		exit(1);
	}
	//定义一个子函数,传入第一个元素的下标和最后一个元素的下标
	_MergeSort(a, 0, n - 1, temp);
	//最后释放temp数组
	free(temp);
	//将temp数组置空
	temp = NULL;
}

4.5 非递归实现归并排序

通过非递归来实现归并排序，最难解决的是边界问题

具体步骤

(1)设定一个初始值为1的gap

(2)通过gap来分割子序列。每次分割出2个相邻的子序列进行归并，归并好一组就将其覆盖到原序列中

(3)重复步骤2直到第一轮归并结束

(4)gap乘2，重复步骤2~3，直到gap超过原序列的大小

对于边界问题，在分割子序列的时候可能会出现以下问题:

①两个子序列都越界

②只有第二个子序列越界

当相邻的两个子序列都越界时，我们就不对它们进行归并了，就把它们放在原序列就好。

当只有第二个子序列越界时，我们对越界的序列右侧进行修正即可。

4.6 代码如下

//归并排序(非递归)
void MergeSortNonR(ElemType* a, int n) {
	int* temp = malloc(n * sizeof(ElemType));//开辟存放n个数据的空间
	if (temp == NULL) {
		perror("malloc fail!\n");
		exit(1);
	}
	int gap = 1;//第一次时,gap为1
	while (gap < n) //当gap>n时,退出循环
	{
		for (int j = 0; j < n; j += 2 * gap) 
			//j的范围[0,n-1],
			//因为每次都是2个序列进行归并,所以j每次跳2*gap个
		{
			int begin1 = j, end1 = begin1 + gap - 1;
			int begin2 = begin1 + gap, end2 = begin2 + gap - 1;
 
			//如果end1和begin2超出数组的范围,最后的这个小组不用归并
			//直接退出循环
			if (end1 >= n || begin2 >= n) {
				break;
			}
			//如果end2越界,修正end2,这个小组需要归并
			if (end2 > n) {
				end2 = n - 1;
			}
 
			//i是数组temp的下标
			//要将左右两个区间的值合并到temp数组中
			//i和左区间的begin相同,也就是j
			int i = j;
			//依次比较,取小的尾插到temp数组
			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] < a[begin2]) {
					temp[i++] = a[begin1++];
				}
				else {
					temp[i++] = a[begin2++];
				}
			}
			//如果begin1没走到end1,直接尾插到temp数组后面
			while (begin1 <= end1) {
				temp[i++] = a[begin1++];
			}
			//如果begin2没走到end2,直接尾插到temp数组后面
			while (begin2 <= end2) {
				temp[i++] = a[begin2++];
			}
			//将temp数组里面的值拷贝回a数组,拷贝的范围:[j,end2]
			memcpy(a + j, temp + j, sizeof(int) * (end2 - j + 1));
		}
		//当前gap归并完数组一次,gap更新,gap=gap*2
		gap = gap * 2;
	}
	free(temp);//释放temp数组
	temp = NULL;//将数组置空
}

五、计数排序

计数排序是一个不基于比较的排序算法，又被称为鸽巢原理，是对哈希直接定址法的变形应用。

其优势在于对一定范围内较集中的序列排序时，其时间复杂度低于任何一个基于比较的算法。

其劣势在于是一种用空间换时间的算法，依赖数组范围，只适用于范围较集中的整型数组。

 5.1 基本思想

计数排序的本质是: 统计待排序序列中每种元素出现的次数，按照顺序和出现的次数依次放入原序列中

(1)首先遍历待排序序列找出最大值和最小值，算出序列元素的范围大小

(2)按照算出的范围开辟一块空间，用来存放统计出的元素个数

因为序列中元素的范围不一定从0开始，如果使用绝对映射（以元素的真实数值作为下标）就会浪费大量空间。当我们找出最大值和最小值后，将元素减去最小值就是它的相对位置

(3)遍历待排序序列，对每种元素出现的次数进行统计

(4)根据统计的结果，按照顺序放入原序列

5.2 动图演示

5.3 代码如下 

//计数排序
void CountSort(ElemType* a, int n) {
	int min = a[0];//假设最小值为第一个元素
	int max = a[0];//假设最大值为第一个元素
 
	//遍历数组,选出最小值和最大值
	for (int i = 1; i < n; i++) {
		if (a[i] > max) {
			max = a[i];
		}
		if (a[i] < min) {
			min = a[i];
		}
	}
	//计算[min,max]区间共有多少个数
	int range = max - min + 1;
	//根据这个范围开辟一个数组
	int* temp = malloc(range * sizeof(int));
	if (temp == NULL) {
		perror("malloc fail!\n");
		exit(1);
	}
	//将temp数组初始化全为0
	memset(temp, 0, range*sizeof(int));
 
	//计数
	for (int i = 0; i < n; i++) {
		temp[a[i] - min]++;
	}
	//排序
	int k = 0;
	for (int j = 0; j < range; j++) {
		while (temp[j]--) {
			a[k++] = j + min;
		}
	}
}

六、测试环节

通过下面这段代码，我们来测试一下以上8种排序算法

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);
	int* a8 = (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];
		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();
	SelectSort2(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();
 
	int begin7 = clock();
	BubbleSort(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("SelectSort2:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	printf("BubbleSort:%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);
 
}

这是1万个数据测试的结果

我们可以发现,不同的排序算法消耗的时间是不同的，时间复杂度O(n^2)和O(n*logn)的算法之间差距很大。 

片尾

今天我们学习了选择排序，堆排序，快速排序，归并排序还有计数排序，知识量有点大，希望看完这篇文章能对友友们有所帮助！！！

求点赞收藏加关注！！！

谢谢大家！！！