快速排序常见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-1
	int 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法2：挖坑法

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

代码如下:

int _Partition_2(vector<int> &arr, int left, int right)
{
//这里的right是长度，所以high的值是right-1
	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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法3：快慢指针法

两个指针：slow和fast。

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

int _Partition_3(vector<int> &arr, int left, int right)
{
//这里的right是长度，所以high的值是right-1
	int 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); // 右子序列`
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

测试代码:

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-1
	int 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
10
11
12

快排的改进：

基准值的选择很重要，理想情况下：希望通过基准值可以将序列划分大小相等的两部分序列，但最糟糕的情况下，当数据完全有序的情况下，例如为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-1
	int 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

以上是自己的一部分理解，若有错误之处，希望大家多多指教！