快速排序挖坑法

118 阅读 0 评论 78 点赞

我是靠谱客的博主怡然黑裤，最近开发中收集的这篇文章主要介绍快速排序挖坑法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

快速排序是一种高效的排序算法，不管是考研还是公司面试，快速排序算法都是我们必不可少的知识点。

本解析为快速排序的挖坑法（快排还有交换法）。

快速排序的挖坑法是快速排序的原理的实现。

具体的步骤：

设定一个基准值（一般为序列的最左边元素，也可以是最右变的元素）此时最左边的是一个坑。
开辟两个指针，分别指向序列的头结点和尾结点（选取的基准值在左边，则先从右边出发。反之，选取的基准值在右边，则先从左边出发）。
从右指针出发依次遍历序列，如果找到一个值比所选的基准值要小，则将此指针所指的值放在坑里，左指针向前移。
后从左指针出发（选取的基准值在左边，则后从左边出发。反之，选取的基准值在右边，则后从右边出发），依次便利序列，如果找到一个值比所选的基准值要大，则将此指针所指的值放在坑里，右指针向前移。
依次循环步骤4,5，直到左指针和右指针重合时，我们吧基准值放入这连个指针重合的位置。

例如序列5,3,6,2,7

我们以a[1]=5作为基准值（Key=5），进行排序，则根据挖坑法的原理，序列则变为：

定义两个指针，i,j分别指向组号为1和组号为5的节点上（如图3）：

从后往前遍历，即当j==4时即a[j]=2<key时，将a[j]的值填到坑中，即a[i]=a[j],i++;将a[j]中元素去掉，此时的序列状态如图4。

从前往后遍历找到i==3时即a[i]=6>keys时，将a[i]的值填到坑中，即a[j]=a[i],j--;将a[i]中元素去掉，此时的序列状态如图5。

此时i==j,将key值放入序列中即可完成一次排序。

此时key的左边元素都小于key右边的元素都大于key。

递归此序列，此时的左边序列和右边序列都是原来要解决的问题即排序。

关于边界问题：

此方法的边界一定为i==j，不可能出现j<i的情况，因为我们每执行一个i++或j--就判断是否到达边界。

在递归的时候会出现e>=f，出现大于原因是当i和j在序列的边界上即e处或者f处时要结束；等于的原因是递归一个序列它不需要再递归了。此时为递归边界，需要结束。

关于重复元素问题：

此方法可以解决重复元素问题，因为在遍历序列中我们找的仅仅是比key大或小的元素，如果等于的话就直接跳过。

题目引入：https://www.luogu.com.cn/problem/P1177

代码：

#include<bits/stdc++.h>
using namespace std;
void Qsort(int e,int a[],int f){
	if(e>=f)return; 
	int i=e,j=f,key=a[i];
	while(1){
		while(1){
			if(a[j]<=key){//这里a[j]<key也行，只不过在递归的时候如果出现大量的与key相同的值的话就会递归许多次而导致时间复杂度偏高。
				a[i]=a[j],i++;
				break;
			}
			j--;
			if(i==j){//指针动一次就判断一次
				a[i]=key;
				break;
			}
		}
		if(i==j){//同理
			a[i]=key;
			break;	
		}		
		while(1){
			if(a[i]>=key){//同理
				a[j]=a[i],j--;
				break;
			}
			i++; 
			if(i==j){
				a[i]=key;
				break;
			}
		}
		if(i==j){
			a[i]=key;
			break;
		}
	}
	Qsort(e,a,i-1);
	Qsort(i+1,a,f);
}
int main(){
	int a[100006];
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
//	random_shuffle(a+1,a+n+1);
	//srand(time(0));
	Qsort(1,a,n); 
	for(int i=1;i<=n;i++)printf("%d ",a[i]);
	return 0;
}