|
快速排序解释
快速排序 Quick Sort 与归并排序一样，也是典型的分治法的应用。 (如果有对 归并排序还不了解的童鞋，可以看看这里哟~ 归并排序)❤❤❤
(本文作者： Amαdeus，未经允许不得转载哦。)
快速排序的分治模式
1、选取基准值，获取划分位置。将原数组 a[l, r] 划分为两个子数组 a[l, mid - 1] 和 a[mid + 1, r]。在前一个数组中所有元素都小于等于 a[mid]，后一个数组中所有元素都大于等于 a[mid]。而此时的 a[mid] 的值就是我们所取的基准值，mid 就每次划分的位置；
2、递归调用快速排序函数，分别对两个子数组 a[l, mid - 1] 和 a[mid + 1, r] 排序；
3、快速排序我们是在原数组上进行操作的，所以我们并不需要合并，最后 a[l, r] 已经有序。
快速排序的三种写法
快速排序比较普及的有三种写法，分别是 左右指针法 挖坑法 和 前后指针法。主要是取得划分位置实现的方法有所不同。
接下来会逐个介绍这三种快速排序的写法。
左右指针法
左右指针法步骤
1、首先 我们一般选取最左边的元素作为基准值 key。
2、然后我们需要定义两个变量 i 和 j。
其中 i 为左指针(其实不是指针啦，只是为了方便这么叫它😋)，初始 i = 0。 j 为右指针，初始 j = r - 1，向左遍历不断找到小于基准值 key 的元素。
3、我们先动右指针 j 向左遍历直到找到小于当前基准值 key 的元素；然后我们再动左指针 i 向右遍历直到找到大于当前基准值 key 的元素。
当 i 和 j 分别找到它们要找的元素时，我们需要将两个元素进行位置交换。( 在这个过程中我们要保持 i < j )
4、重复步骤3，直到最后我们可爱的左右指针相遇，这时我们再将基准值 key，放到这两个指针指向的位置。此时我们就得到了当前划分的位置，基准值 key 也完成了归位。
左右指针法移动指针先后顺序问题
在上述步骤中，有些人会感到疑惑，那就是我们再移动指针时，每次都要 先移动右指针，再移动左指针。为什么呢？😕😕😕
在取基准值时，我们一般都是将序列的最左边位置的元素作为基准值。我们每次交换完元素后，左右指针都会继续寻找他们要找的值，观感上就是相互靠近。而问题就出在我们退出循环的那一刻。
我们一直保持 i < j，也就是说，我们会在 i == j 时退出循环。假设 在某次交换之后，此时 j 指向的是交换之后的一个大于基准值的元素，如果我们先动左指针 i 去寻找一个大于基准值的元素，然鹅还未找到就已经和右指针 j 相遇了，这个时候我们需要退出循环，交换基准值 key 到当前两个指针指向的位置。
但是!!!，此时 i 和 j 指向的是大于基准值的元素，那么我们进行交换基准值位置操作后，这个大于基准值的元素就被换到了序列的最左端，很明显，这时候出现了非常非常非常严重的错误。
那如果我们先动右指针 j，去寻找一个小于基准值的元素，然鹅没有找到就已经和左指针 i 相遇了，这个时候退出循环，i 和 j 指向的一定是一个小于等于基准值的值。
究其原因，这其实是我们取最左边的元素作为基准值导致的。我们需要保证每次交换过来的元素是小于等于基准值的，所以我们先动右指针，再动左指针。
左右指针法动态演示
我们以序列 [3,14,6,1,2,17,7] 为例进行动态演示。(后面还会有先动左指针的错误演示)
左右指针法正确演示
左右指针法错误演示
左右指针法核心代码
//左右指针法
int Partition_Hoare(vector &a, int left, int right){
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key) //向左找到小于基准值的值的下标
j--;
while(i < j && a[i] = key) //必须先动右边的 因为取的基准值在左边
j--; //向左寻找直到找到比基准值小的
a[i] = a[j]; //挖坑 填入比基准值小的值
while(i < j && a[i] = key) //必须先动右边的 因为取的基准值在左边
j--; //向左寻找直到找到比基准值小的
swap(a[i], a[j]); //交换
i++; //看下一个（可以省略）
while(i < j && a[i] >1;
if(a[left] < a[mid])
if(a[mid] < a[right])
return mid; //mid为中间值
else
if(a[left] < a[right])
return right; //right为中间值
else
return left; //left为中间值
else
if(a[mid] > a[right])
return mid; //mid为中间值
else
if(a[left] > a[right])
return right; //right为中间值
else
return left; //left为中间值
}
完整程序源代码
#include
#include
#include
using namespace std;
/* 1 */
//左右指针法
int Partition_Hoare(vector &a, int left, int right){
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key) //向左找到小于基准值的值的下标
j--;
while(i < j && a[i] = key) //必须先动右边的 因为取的基准值在左边
j--; //向左寻找直到找到比基准值小的
a[i] = a[j]; //挖坑 填入比基准值小的值
while(i < j && a[i] = key) //必须先动右边的 因为取的基准值在左边
j--; //向左寻找直到找到比基准值小的
swap(a[i], a[j]); //交换
i++; //看下一个（可以省略）
while(i < j && a[i] >1;
if(a[left] < a[mid])
if(a[mid] < a[right])
return mid; //mid为中间值
else
if(a[left] < a[right])
return right; //right为中间值
else
return left; //left为中间值
else
if(a[mid] > a[right])
return mid; //mid为中间值
else
if(a[left] > a[right])
return right; //right为中间值
else
return left; //left为中间值
}
//左右指针法 三数取中优化
int Partition_Better(vector &a, int left, int right){
int pos = GetMid(a, left, right);
swap(a[pos], a[left]); //将取得的基准值和第一个位置交换
int i = left;
int j = right;
int key = a[left];
while(i != j){
while(i < j && a[j] >= key)
j--;
while(i < j && a[i] = right )
return;
//int i = Partition_Hoare(a, left ,right); //分割 C(n) = n - 1
//int i = Partition_DigI(a, left, right);
//int i = Partition_DigII(a, left, right);
//int i = Partition_PreAndCurr(a, left, right);
int i = Partition_Better(a, left, right);
Quick_Sort(a, left, i - 1); //递归左边的部分
Quick_Sort(a, i + 1, right); //递归右边的部分
}
void show(vector &v){
for(auto &x : v)
cout |