快速排序常见3种方法(hoare、挖坑法、前后指针法)以及改进。

本文主要是介绍快速排序常见3种方法(hoare、挖坑法、前后指针法)以及改进。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快速排序

快速排序的思路:

通过一趟快速排序：找到基准值正确的索引位置，将序列划分为2部分，左侧序列小于基准值，右侧序列大于基准值。然后再对左右两侧的序列分别进行递归处理，最终左右两侧的序列均为有序序列，排序即可完成。
整体思路如下:

给定low 和high分别代表第一个元素和最后一个位置元素的索引，

假定基准值key是最左侧的元素，比较的时候从数组的尾部进行比较，

(1).当最右侧的元素大于基准值key的时候，high–.如果arr[high]<key的时候，就交换arr[low]和arr[high]的值。交换比较的方向，即从数组的头部low的位置向后扫描。

(2).如果arr[low]的值小于基准值key的话，low++，当arr[low]>=key的时候，交换arr[low]和arr[high]的值。再次交换比较的方向，数组从尾部high的位置从后往前扫描。

(3)不断重复1.2步，最终直到(low==high)的时候，low的位置就是该基准值在数组中的正确索引位置。

方法1：hoare法

int _Partition_1(vector<int> &arr, int left, int right)
{
//这里的right是长度，所以high的值是right-1int low = left, high = right - 1;//基准值是左侧值int key = arr[low];while (low < high){while (low<high &&arr[high]>key)high--;swap(arr[low], arr[high]);while (low < high && arr[low] <= key)low++;swap(arr[low], arr[high]);}return low;
}

方法2：挖坑法

由于需要不断的调动交换函数，对效率是一种损耗，因此可以将基准值存储在临时变量key里面，通过赋值的方法，避免交换，循环结束之后，将key值赋给arr[low]，即low处是正确的索引位置。这样做的好处就是始终有一个坑等待去填。
具体的思路如下:
在这里插入图片描述
代码如下:

int _Partition_2(vector<int> &arr, int left, int right)
{
//这里的right是长度，所以high的值是right-1int low = left, high = right - 1;int key = arr[left];while (low < high){while (low<high &&arr[high]>key)high--;arr[low]=arr[high]while (low < high && arr[low] <= key)low++;arr[high]=arr[low]}arr[low]=key;return low;
}

方法3：快慢指针法

两个指针：slow和fast。

假设基准值还是为最左边的一个元素,slow指向第一个元素，当arr[low]<key的时候，快指针一直向前移动，快慢指针不重合的时候，交换快慢指针索引处的元素。不满足该条件的时候：快指针一直++,慢指针保持不动。遍历完整个数组之后，将慢指针处的元素和基准值所在的元素进行交换，保证基准值左侧的元素均小于等于基准值，右侧元素均大于该基准值。

int _Partition_3(vector<int> &arr, int left, int right)
{
//这里的right是长度，所以high的值是right-1int low = left,key=arr[low],slow=low;for(int fast=slow+1;fast<right;++fast){if(arr[fast]<key){slow++;if(slow!=fast)swap(arr[slow],arr[right]);}}//注意这里交换的是慢指针的位置和基准值的位置。swap(arr[slow],arr[low]);return slow;
}
总的代码:```cpp
void QuickSort(vector<int> &ar , int left, int right)
{if (left >= right)return;else{int pos = _Partition_1/2/3(ar, left, right);QuickSort(ar, left, pos);    // 左子序列，这里是pos哦，因为内部进行right-1:其实就是基准值左侧的那个元素值。QuickSort(ar, pos + 1, right); // 右子序列`}
}

测试代码:

int main()
{/*vector<int> arr{ 1, 2, 3, 4, 5 };*/vector<int> arr{ 49, 38, 65, 97, 3,13,28,34,75,42 };//right是数组的长度。另外一种版本给定的right的值是arr.size()-1，递归的时候左子序列为(ar,left,pos-1)。//内部的high=right，而非right-1int left = 0, right =arr.size();PrintArray(arr, 0, right);QuickSort(arr, 0, right);PrintArray(arr,0,right);return 0;
}

快排的改进：

基准值的选择很重要，理想情况下：希望通过基准值可以将序列划分大小相等的两部分序列，但最糟糕的情况下，当数据完全有序的情况下，例如为1，2，3，4，5，6，7，8，9.每次选择基准值之后，会导致基准值的左侧只有元素本身，不断的递归调用栈，当数据量非常大的情况下，时间复杂度为O(N2),在力扣上测试的时候，会出现超出时间限制的提示。

改进的方法：基准值三折取中算法

比较第一个元素，中间元素，最后一个元素的大小，将中间值元素作为基准值，这样做的好处是：可以始终保证基准值的左右两侧始终都有元素存在。代码如下：

int GetMidIndex(vector<int> &ar, int left, int right){int mid = (left + right - 1) / 2;// 这种情况：mid是中间值if (ar[left]<ar[mid] && ar[mid]<ar[right - 1])return mid;//这种情况left是中间值if (ar[left]>ar[mid] && ar[left]<ar[right - 1])return left;return right - 1;}
int _Partition_2(vector<int> &arr, int left, int right)
{
//这里的right是长度，所以high的值是right-1int mid_index = GetMidIndex(arr, left, right);if (mid_index != left)//将中间值放在最左侧。swap(arr[mid_index],arr[left])int low = left, high = right - 1;int key = arr[left];while (low < high){while (low<high &&arr[high]>key)high--;arr[low]=arr[high]while (low < high && arr[low] <= key)low++;arr[high]=arr[low]}arr[low]=key;return low;
}