快速排序详解_快速排序快慢指针法

作者：Cpp五条 | 2024-04-27 22:33:58

踩

快速排序快慢指针法

快速排序（Quick Sort）

相关概念

快速排序的最好情况为O(NlogN)，最差情况为O(N^2)
选一个主元将集合分为2个独立子集，分而治之的思想

一、快慢指针

参考链接：https://www.bilibili.com/video/BV1q4411u72L?spm_id_from=333.999.0.0

以最后一个元素为主元，使用快慢指针的方法，当遇到小于主元的元素时将vec[i]和vec[i]进行交换。这样永远都是比主元大的值被交换到右侧，即i的左侧小于主元，而右侧大于主元。


template<typename T>
void QuickSort(vector<T>& vec, int low, int high) {
	if (low >= high) // 只有单个元素时返回
		return;
	int pivot = vec[high]; // 取最后一个元素作为主元
	int i = low - 1, j = low; // i为慢指针,j为快指针
	for (; j &

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/499029

快速排序 详解_快速排序快慢指针法

快速排序（Quick Sort）

一、快慢指针

快速排序详解_快速排序快慢指针法