[数据结构 -- 手撕排序算法第六篇] 递归实现快速排序（集霍尔版本，挖坑法，前后指针法为一篇的实现方法，很能打）

末蓝、 2023-10-13 19:43 5阅读 0赞

**目录**

1、常见的排序算法

1.1 交换排序基本思想

2、快速排序的实现方法

2.1 基本思想

3 hoare（霍尔）版本

3.1 实现思路

3.2 思路图解

3.3 为什么实现思路的步骤2、3不能交换

3.4 hoare版本代码实现

3.5 hoare版本代码测试

4、挖坑法

4.1 实现思路

4.2 思路图解

4.3 挖坑法代码实现

4.4 挖坑法代码测试

5、前后指针版本

5.1 实现思路

5.2 思路图解

5.3 前后指针法代码实现

5.4 前后指针法代码测试

6、时间复杂度分析

6.1 最好情况

6.2 最坏情况

7、优化快速排序

7.1 选 key 优化

7.2 小区间优化

--------------------

## 1、常见的排序算法 ##

### 1.1 交换排序基本思想 ###

冒泡排序属于交换排序之一，我们先来了解以下冒泡排序思想。

> **基本思想：**所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

![ab46612bb81f8a9b434cfcafb5eb98cf.png][]

## 2、快速排序的实现方法 ##

递归实现与二叉树的前序遍历很相似，将区间划分为左右两半部分的常见方式有三种：**1.hoare版本；2.挖坑法；3.左右指针法。**

### 2.1 基本思想 ###

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

## 3 hoare（霍尔）版本 ##

### 3.1 实现思路 ###

**我们规定排****升序****，排序****数组名称为a，基准值 key，基准值下标 keyi，左 left，右 right。**

> **1.选出一个key，key可以是需要排序的数组中任意一个元素，我们****本篇文章选key为a\[left\]****；**
> 
> **2.从数组右端（尾部）往左走，当a\[right\] < key(a\[keyi\])，right停下来；**
> 
> **3.然后从数组左端（首部）往右走，当a\[left\] > key(a\[keyi\])，left停下来；**
> 
> **4.交换a\[left\], a\[right\]；**
> 
> **5.循环步骤2、3、4，当 left与right 走到相同位置时，交换此位置的元素与 key，key 的位置就确定了。**
> 
> **6.此时 key 就将数组分为了左右两个区间，我们对左右两个区间分别使用前5步，然后再次确定了左右区间的key，递归左区间，再递归右区间，就实现了排序。**
> 
> **注意：步骤2、3的顺序不能换。至于为什么，我们思路图解后再说。**

### 3.2 思路图解 ###

**我们的图解就是按照实现思路来画的。**

![ca6920e0a04b2c84a22bb44f95bc9af3.png][]

### 3.3 为什么实现思路的步骤2、3不能交换 ###

**我们可以看到，思路图解里，当最后找到 3 时候是 R 先走，R先遇到 3，如果是 L 先走，左找大，L 遇见 3 不会停下来，会直接走到R的位置，R 位置是 9，这时候相遇，就交换，一旦交换，左区间就不是全部小于 key（6）了，这就会出现错误。****因此，key 如果选在左边，右边先走。**

**Q：hoare版本我们是理解了，如果key选在右边，那是不是左边先走呢？**

**A：答案是一定的。这里其实就是** **L遇到R** **还是** **R遇到L** **的问题。我们依然可以用上面的解法来想这问题，当L遇到R 时，说明 R 已经停下，R 停下就是 a\[right\]<key，这时 L遇到R，相遇位置就是小于 key 的位置，交换（key，a\[left\]），这时最后一个小于 key 的元素就放在了最左边，而 key 就到了确定的位置，不用再调了，以key 为中点的左区间全部小于 key，右区间全大于 key；**

**key在右边，当 R遇到L 时，说明 L 已经停下，L 停下就是 a\[left\]>key，这时 R遇到L，相遇位置就是大于 key 的位置，交换（a\[left\]，key），这时最后一个大于 key 的元素就放在了最右边，而 key 就到了确定的位置，不用再调了，以 key 为中点的左区间全部小于 key，右区间全大于 key。**

**所以如果 key 选在左边，就先走右边；key 选在右边，就先走左边。**

### 3.4 hoare版本代码实现 ###

// 快速排序hoare版本
    int PartSort1(int* a, int left, int right)
    {
    	int keyi = left;
    	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]);
    
    	return left;
    }
    void QuickSort(int* a, int left, int right)
    {
    	if (left >= right)
    		return;
    
    	int keyi = PartSort1(a, left, right);
    	QuickSort(a, left, keyi - 1);
    	QuickSort(a, keyi + 1, right);
    }

### 3.5 hoare版本代码测试 ###

void Swap(int* p1, int* p2)
    {
    	int tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    void Print(int* a, int n)
    {
    	for (int i = 0; i < n; i++)
    	{
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    }
     //快速排序递归实现
     //快速排序hoare版本
    int PartSort1(int* a, int left, int right)
    {
    	int keyi = left;
    	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 left, int right)
    {
    	if (left >= right)
    		return;
    
    	int keyi = PartSort1(a, left, right);
    	QuickSort(a, left, keyi - 1);
    	QuickSort(a, keyi + 1, right);
    }
    void test()
    {
    	int a[] = { 6,3,2,1,5,7,9 };
    	QuickSort(&a, 0, sizeof(a) / sizeof(int) - 1);
    	Print(&a, sizeof(a) / sizeof(int));
    }
    int main()
    {
    	test();
    
    	return 0;
    }

![a7fed03807dc528a627488db787f4ba2.png][]

## 4、挖坑法 ##

### 4.1 实现思路 ###

**我们规定排****升序****，排序****数组名称为a，基准值 key，左 left，右 right。**

> **1.选出一个key，key可以是需要排序的数组中任意一个元素，我们****依然选key为a\[left\]，将a\[left\]交给key保存起来，被选为key的元素位置就是坑位****；**
> 
> **2.从数组右端（尾部）往左走，当a\[right\] < key，right停下来，将a\[right\]放到坑位中，坑位就换为下标为 right 的位置，此时right不动；**
> 
> **3.然后从数组左端（首部）往右走，当a\[left\] > key，left停下来，将a\[left\]放到坑位中，坑位就换为下标为 left 的位置，此时left不动；**
> 
> **4.循环步骤2、3，当 left与right 走到相同位置时，这个位置就是最后一个坑位，将key放到这个坑位中，key的最终位置就确定下来了，后面就不用再调整了。**
> 
> **5.此时 key 就将数组分为了左右两个区间，我们对左右两个区间分别使用前4步，然后再次确定了左右区间的key，递归左区间，再递归右区间，就实现了排序。**

**挖坑法与hoare版本的区别：**

> 1.挖坑法不需要去想最后的 L与R 相遇的位置的元素要小于key，因为最终相遇位置是坑位，直接将 key 放入坑位就好了；
> 
> 2.不用去想为什么选左边为 key 要右边先走，选右边为 key 要左边先走，当选左边为 key 时，因为需要填左边的坑，所以肯定是右边先走。**左边找小，右边找大来理解这句话更合适。**

### 4.2 思路图解 ###

![1396edb37c55f31d75a9b0e2a40fc299.png][]

### 4.3 挖坑法代码实现 ###

// 快速排序挖坑法
    int PartSort2(int* a, int left, int right)
    {
    	int key = a[left];
    	int hole = left;
    	while (left < right)
    	{
    		//右边找小
    		while (left < right && a[right] >= key)
    		{
    			right--;
    		}
    		a[hole] = a[right];
    		hole = right;
    
    		//左边找大
    		while (left < right && a[left] <= key)
    		{
    			left++;
    		}
    		a[hole] = a[left];
    		hole = left;
    	}
    	a[hole] = key;
    
    	return hole;
    }
    void QuickSort(int* a, int left, int right)
    {
    	if (left >= right)
    		return;
    
    	int keyi = PartSort2(a, left, right);
    	QuickSort(a, left, keyi - 1);
    	QuickSort(a, keyi + 1, right);
    }

### 4.4 挖坑法代码测试 ###

void Swap(int* p1, int* p2)
    {
    	int tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    void Print(int* a, int n)
    {
    	for (int i = 0; i < n; i++)
    	{
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    }
    // 快速排序挖坑法
    int PartSort2(int* a, int left, int right)
    {
    	int key = a[left];
    	int hole = left;
    	while (left < right)
    	{
    		//右边找小
    		while (left < right && a[right] >= key)
    		{
    			right--;
    		}
    		a[hole] = a[right];
    		hole = right;
    
    		//左边找大
    		while (left < right && a[left] <= key)
    		{
    			left++;
    		}
    		a[hole] = a[left];
    		hole = left;
    	}
    	a[hole] = key;
    
    	return hole;
    }
    void QuickSort(int* a, int left, int right)
    {
    	if (left >= right)
    		return;
    
    	int keyi = PartSort2(a, left, right);
    	QuickSort(a, left, keyi - 1);
    	QuickSort(a, keyi + 1, right);
    }
    void test()
    {
    	int a[] = { 6,3,2,1,5,7,9 };
    	QuickSort(&a, 0, sizeof(a) / sizeof(int) - 1);
    	Print(&a, sizeof(a) / sizeof(int));
    }
    int main()
    {
    	test();
    
    	return 0;
    }

![ddb13aef2c991a214d10d9220b203425.png][]

## 5、前后指针版本 ##

### 5.1 实现思路 ###

**我们规定排****升序****，排序****数组名称为a，基准值 key。**

> **1.选出一个key，key可以是需要排序的数组中任意一个元素，我们****依然选key为a\[left\]；**
> 
> **2.定义一个prev指针，和一个cur指针，初始化 prev 指向数组首部位置，cur 指向 prev 的下一个位置。cur先走，cur 找小于 key 的元素，找到之后停下来，让 prev++，然后交换 (a\[cur\], a\[prev\])。交换完继续往后走，cur 找的值不小于 key，cur继续往后走，找到后让 prev++，交换 (a\[cur\], a\[prev\])，不断重复此步骤；**
> 
> **3.当cur走完整个数组的时候，交换(a\[left\], a\[prev\])，这时key的最终位置就确定下来了。key 将数组分为左右两个子区间，左子区间小于 key，右子区间大于 key；**
> 
> **4.左右子区间继续重复前 3 步骤，递归下去就实现了数组的排序。**

### 5.2 思路图解 ###

![6ab402e4c6e4ce9d8fdaf78ed7917597.png][]

**这里不断交换其实是将小于 key 的值一直在往前抛，把大于 key 的值往后抛，cur与prev 之间的值其实就是大于 key 的所有值，不断交换就实现了最终以 key 划分的左右区间，左区间小于 key，右区间大于 key。**

### 5.3 前后指针法代码实现 ###

// 快速排序前后指针法
    int PartSort3(int* a, int left, int right)
    {
    	int prev = left;
    	int cur = left + 1;
    	int keyi = left;
    	while (cur <= right)
    	{
    		if (a[cur] < a[keyi] && ++prev != cur)
    		{
    			Swap(&a[prev], &a[cur]);
    		}
    
    		cur++;
    	}
    	Swap(&a[keyi], &a[prev]);
    	return prev;
    }
    void QuickSort(int* a, int left, int right)
    {
    	if (left >= right)
    		return;
    
    	int keyi = PartSort3(a, left, right);
    	QuickSort(a, left, keyi - 1);
    	QuickSort(a, keyi + 1, right);
    }

### 5.4 前后指针法代码测试 ###

![d4e5cdd64c86756e154f19fe97b2b58d.png][]

## 6、时间复杂度分析 ##

### 6.1 最好情况 ###

上面的三种情况下，最好情况时间复杂度是**O(N\* logN)**。

每次 key 被排到区间的中间位置，像二叉树一样要递归 logN 次，每一次的子区间排序的时间复杂度是O(N)，所以最好的情况就是O(N \* logN)。

![5788dbc71f8d989b981c5ff51861af83.png][]

### 6.2 最坏情况 ###

当数组有序的时候排序，无论 key 选最左边还是最右边，时间复杂度都是**O(N^2)。**

![78364acb2dfc4824187bbebe650c1154.png][]

## 7、优化快速排序 ##

> 快速排序的优化有两种思想：
> 
> 1.我们对选key法可以进行优化；
> 
> 2.递归到小的子区间，我们可以考虑使用插入排序，也称小区间优化。

### 7.1 选 key 优化 ###

**选 key 优化主要是针对数组有序，或者是接近有序。**

> 对选 key 的优化我们有两种思路：
> 
> 1.随机选 key；
> 
> 2.三数取中选 key。（拿出left, mid, right，在下标为这三个位置的数中选出一个中间值作为 key）。

第一种思路是不可控的，所以第二种选 key 的思路才是最合适的。

**下面是三数取中的优化代码：**

int GetMidIndex(int* 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[left] < a[right])
    			return right;
    		else
    			return left;
    	}
    	else //a[left] > a[mid]
    	{
    		if (a[mid] > a[right])
    			return mid;
    		else if (a[left] > a[right])
    			return right;
    		else
    			return left;
    	}
    }
    int PartSort3(int* a, int left, int right)
    {
    	int midi = GetMidIndex(a, left, right);
    	Swap(&a[left], &a[midi]);
    
    	int prev = left;
    	int cur = left + 1;
    	int keyi = left;
    	while (cur <= right)
    	{
    		if (a[cur] < a[keyi] && ++prev != cur)
    		{
    			Swap(&a[prev], &a[cur]);
    		}
    		cur++;
    	}
    	Swap(&a[prev], &a[keyi]);
    	keyi = prev;
    	return keyi;
    }

**我们取到中后，将该数字与 a\[left\]交换，依旧用之前的前后指针法的思路是没有问题的。霍尔版本与挖坑法是一样的优化方法。**

如果我们不做三数取中的优化，当数组是有序或者接近有序的时候，时间复杂度会是最坏情况，O(N^2)。经过三数取中后，如果数组是有序的，时间复杂度仍是O(N \* logN)。

### 7.2 小区间优化 ###

> 在递归的时候，我们之前画的图中不难看到，在不断的划分的时候，到后面划分的越来越多了，当数据量特别大的时候，对栈的消耗会很大，会造成栈溢出的风险。因此，当划分到一定的程度，我们不再划分，直接选择插入排序。一般的情况下，当我们的子区间数据个数为10的时候，我们就不再递归了，直接就用插入排序。

![81f1e2032bf35a1cf9b1461b550484d1.png][]

**实现代码：**

// 插入排序
    //时间复杂度（最坏）：O(N^2) -- 逆序
    //时间复杂度（最好）：O(N) -- 顺序
    void InsertSort(int* a, int n)
    {
    	for (int i = 0; i < n - 1; i++)
    	{
    		int end = i;
    		int tmp = a[i + 1];
    		
    		while (end >= 0)
    		{
    			if (a[end] > tmp)
    			{
    				a[end + 1] = a[end];
    				end--;
    			}
    			else
    			{
    				break;
    			}
    		}
    		a[end + 1] = tmp;
    	}
    }
    int GetMidIndex(int* 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[left] < a[right])
    			return right;
    		else
    			return left;
    	}
    	else //a[left] > a[mid]
    	{
    		if (a[mid] > a[right])
    			return mid;
    		else if (a[left] > a[right])
    			return right;
    		else
    			return left;
    	}
    }
    // 快速排序前后指针法
    //[left, right]
    int PartSort3(int* a, int left, int right)
    {
    	int midi = GetMidIndex(a, left, right);
    	Swap(&a[left], &a[midi]);
    
    	int prev = left;
    	int cur = left + 1;
    	int keyi = left;
    	while (cur <= right)
    	{
    		if (a[cur] < a[keyi] && ++prev != cur)
    		{
    			Swap(&a[prev], &a[cur]);
    		}
    		cur++;
    	}
    	Swap(&a[prev], &a[keyi]);
    	keyi = prev;
    	return keyi;
    }
    void QuickSort(int* a, int left, int right)
    {
    	//子区间只有一个值，或者子区间不存在的时候递归结束
    	if (left >= right)
    		return;
    
    	//小区间优化
    	if (right - left + 1 < 10)
    	{
    		InsertSort(a + left, right - left + 1);
    	}
    
    	int keyi = PartSort3(a, left, right);
    	QuickSort(a, left, keyi - 1);
    	QuickSort(a, keyi + 1, right);
    }

**这两种优化的方式在****时间****与****空间****两个方面都有一定程度的提升，但快速排序的本质没有改变，优化只是在原有的思想上锦上添花。**

[ab46612bb81f8a9b434cfcafb5eb98cf.png]: https://img-blog.csdnimg.cn/img_convert/ab46612bb81f8a9b434cfcafb5eb98cf.png
[ca6920e0a04b2c84a22bb44f95bc9af3.png]: https://img-blog.csdnimg.cn/img_convert/ca6920e0a04b2c84a22bb44f95bc9af3.png
[a7fed03807dc528a627488db787f4ba2.png]: https://img-blog.csdnimg.cn/img_convert/a7fed03807dc528a627488db787f4ba2.png
[1396edb37c55f31d75a9b0e2a40fc299.png]: https://img-blog.csdnimg.cn/img_convert/1396edb37c55f31d75a9b0e2a40fc299.png
[ddb13aef2c991a214d10d9220b203425.png]: https://img-blog.csdnimg.cn/img_convert/ddb13aef2c991a214d10d9220b203425.png
[6ab402e4c6e4ce9d8fdaf78ed7917597.png]: https://img-blog.csdnimg.cn/img_convert/6ab402e4c6e4ce9d8fdaf78ed7917597.png
[d4e5cdd64c86756e154f19fe97b2b58d.png]: https://img-blog.csdnimg.cn/img_convert/d4e5cdd64c86756e154f19fe97b2b58d.png
[5788dbc71f8d989b981c5ff51861af83.png]: https://img-blog.csdnimg.cn/img_convert/5788dbc71f8d989b981c5ff51861af83.png
[78364acb2dfc4824187bbebe650c1154.png]: https://img-blog.csdnimg.cn/img_convert/78364acb2dfc4824187bbebe650c1154.png
[81f1e2032bf35a1cf9b1461b550484d1.png]: https://img-blog.csdnimg.cn/img_convert/81f1e2032bf35a1cf9b1461b550484d1.png