排序算法在我们校招考察中很常见，所以今天咋也对很常见的快速排序做出总结，希望能够帮助朋友们理解！

文章目录

• 一：快速排序
• 二：基本框架
• 三：单趟逻辑
• • 3.1：hoare版本
  • 3.2：挖坑法
  • 3.3：前后指针法
• 四：快速排序的优化
• 五：快速排序的非递归实现（非常重要）
• 六：快速排序的特性总结

一：快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

二：基本框架

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
 	if(right - left <= 1)
 		return;
 
 // 按照基准值对array数组的 [left, right)区间中的元素进行划分
 	int div = partion(array, left, right);
 
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
 // 递归排[left, div)
 	QuickSort(array, left, div);
 
 // 递归排[div+1, right)
 	QuickSort(array, div+1, right);
}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来。

三：单趟逻辑

选出一个基准值，一般是第一个数或者是最后一个数，经过单趟排序后的结果是左边的值都比基准值小，右边的值都比基准值大。
将区间按照基准值划分为左右两半部分的常见方式有：

3.1：hoare版本

动图演示：

💡💡💡思想：从右边开始找比基准值小的值，从左边找比基准值大的值，等都找到时，交换，再继续上述过程，相遇以后，再把相遇位置的值跟基准值做交换！

int hoare(vector<int>& v, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		while (left < right && v[right] >= v[keyi])
		{
			right--;
		}
		while (left < right && v[left] <= v[keyi])
		{
			left++;
		}
		swap(v[left], v[right]);
	}
	swap(v[keyi], v[left]);
	return left;
}
void QuickSort(vector<int>& v, int left, int right)
{
	//双闭区间
	if (left >= right)
	{
		return;
	}

	int div = hoare(v, left, right);

	QuickSort(v, left, div - 1);
	QuickSort(v, div + 1, right);
}

💡💡思考：如何保证相遇的位置一定比基准值小呢？

• 如果选第一个数作为基准值，那么让右边先走，可以保证。
• 如果选最后一个数作为基准值，那么让左边先走，可以保证。

3.2：挖坑法

先将第一个数据存放在临时变量中，形成一个坑位，比如说找最左边的值作为key，形成一个坑位，那么从右边先走，找比key值更小的值，找到之后把该值放到坑位，形成新的坑位，又从左边找新的比key值大的值放到坑位，依次循环，相遇的位置一定在坑上，再把key值放到坑上。
动图演示：

代码示例：

int DigPit(vector<int>& v, int left, int right)
{
	int key = v[left];
	while (left < right)
	{
		while (left < right && v[right] >= key)
		{
			right--;
		}
		v[left] = v[right];
		while (left < right && v[left] <= key)
		{
			left++;
		}
		v[right] = v[left];
	}
	v[left] = key;
	return left;
}
void QuickSort(vector<int>& v, int left, int right)
{
	//双闭区间
	if (left >= right)
	{
		return;
	}

	int div = DigPit(v, left, right);

	QuickSort(v, left, div - 1);
	QuickSort(v, div + 1, right);
}

相比于版本一的好处在于：

• 不需要去理解为什么左边做基准值时，要让右边先走。
• 相遇位置一定在坑位上，再把基准值扔到坑位上。

3.3：前后指针法

初始时，选取第一个值作为基准值，prev指针指向序列开头，cur指针指向prev指针的后一个位置，然后cur指针一直向后找比基准值小的值，找到后，先把prev指针向后移动一位，再交换prev和cur位置的值，最后当cur越界结束，再把prev处的值与序列开头值交换。

int QSPtr(vector<int>& v, int left, int right)
{
	int key = v[left];
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (v[cur] < key && v[prev] != v[cur])
		{
			prev++;
			swap(v[cur], v[prev]);
		}
		cur++;
	}
	swap(v[prev], v[left]);
	return prev;
}
void QuickSort(vector<int>& v, int left, int right)
{
	//双闭区间
	if (left >= right)
	{
		return;
	}

	int div = QSPtr(v, left, right);

	QuickSort(v, left, div - 1);
	QuickSort(v, div + 1, right);
}

注意到prev指针和cur指针中间间隔的是一段比基准值大的区间！

四：快速排序的优化

• 我们首先思考快速排序的最优情况是什么？

那就是每次选出的key值都大致单趟排序后位于序列中部，那么这时时间复杂度就是n*logn。

• 其实思考快速排序的最坏情况是什么？
  那就是每次取出的key值都是序列中的最大值或者最小值，此时时间复杂度就是o(n^2)。

所以我们提出一种优化策略，那就是每次取出的数字都是大致是中位数！

💡💡💡首先

• 三数取中法选key。

int GetmidIndex(vector<int>& v, int left, int right){
	int mid = (left + right) / 2;//left + (right - left) / 2;
	if (v[left] < v[mid])
	{
		if (v[mid] < v[right]){
			return mid;
		}
		else if (v[left] > v[right]){
			return left;
		}
		else{
			return right;
		}
	}
	else{
		if (v[mid] > v[right]){
			return mid;
		}
		else if (v[left] > v[right]){
			return right;
		}
		else{
			return left;
		}
	}
}


int QSPtr(vector<int>& v, int left, int right)
{
	int midi = GetmidIndex(v, left, right);
	swap(v[left], v[midi]);

	//以下步骤都是一样
	int key = v[left];
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (v[cur] < key && v[prev] != v[cur])
		{
			prev++;
			swap(v[cur], v[prev]);
		}
		cur++;
	}
	swap(v[prev], v[left]);
	return prev;
}


void QuickSort(vector<int>& v, int left, int right)
{
	//双闭区间
	if (left >= right)
	{
		return;
	}

	int div = QSPtr(v, left, right);

	QuickSort(v, left, div - 1);
	QuickSort(v, div + 1, right);
}

💡💡💡其次

• 小区间优化，递归到小的子区间时，可以考虑使用插入排序。

void QuickSort(vector<int>& v, int left, int right)
{
	//双闭区间
	if (left >= right)
	{
		return;
	}
	if (right - left < 10){
		//插入排序
	}

	int div = QSPtr(v, left, right);

	QuickSort(v, left, div - 1);
	QuickSort(v, div + 1, right);
}

当区间很小时，不再使用递归划分的思想让他有序，而是直接使用插入排序对小区间排序，减少递归调用。（我们知道插入排序在小区间大致有序的情况下效率是比较高的）。

五：快速排序的非递归实现（非常重要）

void NonQuickSort(vector<int>& v)
{
	int left = 0, right = v.size() - 1;
	stack<int> st;
	st.push(left);
	st.push(right);

	while (!st.empty())
	{
		int right = st.top();
		st.pop();
		int left = st.top();
		st.pop();

		int div = DigPit(v, left, right);

		if (div - 1 > left)//说明该区间至少两个元素
		{
			st.push(left);
			st.push(div - 1);
		}
		if (right - 1 > div)
		{
			st.push(div + 1);
			st.push(right);
		}
	}
}
int main()
{
	vector<int> v = { 2, 1, 4, 3, 4, 9, 8, 7, 0 };
	NonQuickSort(v);

	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

六：快速排序的特性总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定