快速排序的三种方法

目录

1. hoare法

2.  挖坑法

3. 前后指针法

---

1. hoare法

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，我们先来介绍的就是他所创建的方法。

方法步骤：

1. 选择数组最左边(最右边)为基准数key

2. 从右边开始(从左边)开始进行筛选，右边(从左边)选出小于key的数

3. 然后从左边(从右边)开始选择出大于key的数

4. 两者进行交换

5. 重复上述循环，直到左边和右边相遇

这里有个难点：为什么选取左边为基准数就要从右边开始寻找？

因为从右边开始可以保证最后相遇处的数是小于key的，这样才满足最终结果：左边都小于key，右边都大于key

代码实现如下：

void swap(int*a,int i,int j){
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
//hoare版本 
int Partition2(int*a,int left,int right){
	int key=left; //从最左边开始 
	while(left<right){
		//先从右边开始找 
		while(left<right&&a[right]>=a[key]){//找到右边的小于a[key]的值 
			right--;
		}
		while(left<right&&a[left]<=a[key]){ //找到左边的大于a[key]的值 
			left++;
		}
		swap(a,left,right); //找到了就交换
	} 
	swap(a,left,key);  //最后基准数和相遇点进行交换，返回相遇点
	return left; 
} 
void QuickSort(int*a,int left,int right){
	if(right<=left){ //数组中只有一个元素，或者不存在该数组
		return;
	} 
		//单趟排序后pivot就是最终确定的位置 
		int pivot=Partition3(a,left,right);
		//利用分治的思想 
		QuickSort(a,left,pivot-1);
		QuickSort(a,pivot+1,right);
	
}

2.  挖坑法

挖坑法是快速排序的一种更新版。

实现步骤：

1. 以最左边为基准数key，并保留其数据。

2. 可以视基准数的位置空出来了，那从最右边开始寻找小于key的数放置在此坑位上。

3. 当从右边找到合适的数放置左边的坑位时，那右边就多了一个坑位，然后就从左边开始找一个大于key的数放在此坑位。

4. 重复上述步骤，直到最终左边和右边相遇。

代码实现：

void swap(int*a,int i,int j){
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
int Partition(int*a,int left,int right){
	//挖坑法 
    int key=a[left];
    //挖坑 
    int pit=left; //开始选择坑位left
	while(left<right){
		while(left<right&&a[right]>=key){ //找到小于key的数
			right--;
		}
		if(left<right){
			a[pit]=a[right];//填在坑位上
			pit=right; //坑位变成right位置
		}
		while(left<right&&a[left]<=key){ //找到大于key的数
			left++;
		} 
		if(left<right){  //同理
			a[pit]=a[left];
			pit=left;
		}
	} 
	a[pit]=key; //最后的坑位就是left==right的位置
	return pit;
}

 使用了局部变量pit让代码更有可读性，那精简版是什么？

//快速排序 
int Partition(int*a,int left,int right){
	//挖坑法 
    int key=a[left];
	while(left<right){
		while(left<right&&a[right]>=key){
			right--;
		}
		if(left<right){
			a[left]=a[right]
		}
		while(left<right&&a[left]<=key){
			left++;
		}
		if(left<right){
			a[right]=a[left]
		}
	} 
    a[left]=key;
	return left;
	
}

这里舍去了pit变量，代码更加简洁。

3. 前后指针法

与挖坑法相同也是一种更新版本。

实现步骤：

1. 使用指针prev指向第一个位置，指针cur指向下一个位置。

2. 当cur所指的数据不小于key时，cur指针后移

3. 当cur所指的数据小于key，prev指针后移并与cur指针进行数据交换，然后cur后移。

4. 重复上述操作，直到cur超出界限。

代码实现如下：

void swap(int*a,int i,int j){
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
int Partition3(int*a,int left,int right){
	int key=a[left];//基准数 
	int prev=left;//指向第一位 
	int cur=1+left;//指向下一个位置 
	int temp=0; 
	while(cur<=right){
		//如果prev紧邻cur，交换无意义 
		if(a[cur]<key&&a[++prev]!=a[cur]){
			swap(a,cur,prev);
		}
		cur++; //cur后移
	}
	swap(a,left,prev);//交换prev和left的位置 
	return prev;//返回prev 
}

为什么当cur小于key还要保证prev+1!=cur才进行交换呢？

因为当prev紧邻cur时，则说明两个指针之间没有大于key的数据，无需进行自我交换

当prev+1!=cur时，则说明两个指针之间有大于key的数据，当prev+1则找到了大于key的数，跟cur所指小于key的数进行交换则满足了小于key的在左边，大于key的在右边。

直到cur大于right,则说明之后没有小于key的数，则将prev与left进行交换，完成小于key的在左边，大于key的在右边。