【八大经典排序算法】快速排序

在这里插入图片描述

一、概述

说到快速排序就不得不提到它的创始人 hoare了。在20世纪50年代，计算机科学家们开始研究如何对数据进行排序，以提高计算机程序的效率。当时，常用的排序算法包括冒泡排序、插入排序和选择排序等。

然而，这些算法的效率都相对较低，特别是在处理大量数据时。于是，人们开始寻找更快速的排序算法。Tony Hoare 在研究中发现了一种基于分治思想的排序方法，即快速排序。

二、思路实现

快速排序的思想是任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

代码如下：

// 假设按照升序对array数组中[left, right]区间中的元素进行排序
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	// 按照基准值对数组的 [left, right)区间中的元素进行划分
	int keyi = PartSort(a, begin, end);
	//分成[begin,keyi-1] keyi [keyi+1,end]
	
	 // 递归排[left, div)
	QuickSort(a, begin, keyi - 1);
	 // 递归排[div+1, right)
	QuickSort(a, keyi + 1, end);
}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，接下来只需分析如何按照基准值来对区间中数据进行划分的方式即可。
待排序集合分割时，将区间按照基准值划分为左右两半部分的常见方式有以下3种。

2.1 hoare版本

思路：

  1. 选择一个基准元素（key），可以是最左边也可以是最右边。
  2. 定义两个指针，一个指向数组的第一个元素（左指针），一个指向数组的最后一个元素（右指针）。（需要注意的是：若选择最左边的数据作为key，则需要right先走；若选择最右边的数据作为key，则需要left先走）
  3. 移动左指针,直到找到一个大于等于基准元素（key）的元素；移动右指针，直到找到一个小于等于基准元素（key）的元素。之后交换交换左右指针所指向的元素。然后不断重复上述步骤直到左指针大于右指针
  4. 最后将基准元素与右指针所指向的元素交换位置，此时基准元素位于正确的位置。此时左边元素>=key，右边元素<=key。

Tips：博主在这里解释一下为什么“若选择最左边的数据作为key，则需要right先走；若选择最右边的数据作为key，则需要left先走”，后续其他方法同理。
① :左边作key，右边先走，保证了相遇位置的值小于key或就是key的位置。
②：右边作key，左边先走，保证了相遇位置的值大于key或就是key的位置。
以①为例，L和R相遇无非就两种情况：L遇R，R遇L。
情况一：L遇R。在R停下来后，L还在走。由于R先走，R停下来的位置一定小于Key。相遇位置为R停下来的位置，一定比key小。
情况二：R遇L。再相遇的这一轮，L就不动了，R在移动。相遇位置即为L的位置。而L的位置就是key的位置 or 已经交换过一些轮次了，此时相遇位置一定比key小。

【动画演示】：
在这里插入图片描述
代码如下：

 //[left, right]--采用左闭右闭
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		//找到右边比key小的数
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}

		//找到左边比key大的数
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[left]);
	return left;
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

2.2 挖坑法

思路：

  1. .选出一个数据（一般是最左边或是最右边的）存放在key变量中，同时该数据位置形成一个坑。
  2. 还是左右指针left和right，left从左向右走，right从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）
  3. 移动右指针找到第一个比key小的数并填到坑位，此时右指针所在位置变成新的坑。然后移动左指针找到第一个比key大的数并填到坑位，此时左指针所在位置变成新的坑。然后和hoare版本一样，不断重复上述步骤即可

【动画演示】：
在这里插入图片描述
代码如下：

//挖坑法
int PartSort(int* a, int left, int right)
{
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//找到右边比key小的值
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;

		//左边比key大的值
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	return hole;
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

2.3 前后指针版本

思路：

  1. 选出一个key，一般是最左边或是最右边的。
  2. 起始时，prev指针指向序列开头，cur指针指向prev+1。
  3. 若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的内容交换即可。

【动画演示】：
在这里插入图片描述
代码如下：

//前后指针法
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

三、优化

虽然已经可以解决问题了，但还有一个问题：
当选取的key每次都是中位数时，效率最好，时间复杂度为O(N*logN)；但当数组有序时变成最坏，时间复杂度变为O(N^2)！
对于上述情况，这里有两种优化方式：

  1. 三数取中法选key
  2. 递归到小的子区间时，可以考虑使用插入排序

3.1 三数取中

这里博主给出一直最简单的方法：

int GetMidIndix(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[mid] > a[right])
			return right;
		else
			return left;
	}
	else//a[left]>=a[mid]
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[mid] < a[right])
			return right;
		else
			return left;
	}
}

3.1.1 最终代码

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

int GetMidIndix(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[mid] > a[right])
			return right;
		else
			return left;
	}
	else//a[left]>=a[mid]
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[mid] < a[right])
			return right;
		else
			return left;
	}
}

// hoare
// [left, right]
//int PartSort(int* a, int left, int right)
//{
//	int midi = GetMidIndix(a, left, right);
//	Swap(&a[left], &a[midi]);
//
//	int keyi = left;
//	while (left < right)
//	{
//		//找到右边比key小的数
//		while (left < right && a[right] <= a[keyi])
//		{
//			right--;
//		}
//
//		//找到左边比key大的数
//		while (left < right && a[left] >= a[keyi])
//		{
//			left++;
//		}
//		Swap(&a[left], &a[right]);
//	}
//	Swap(&a[keyi], &a[left]);
//	return left;
//}


//挖坑法
//int PartSort(int* a, int left, int right)
//{
//	int midi = GetMidIndix(a, left, right);
//	Swap(&a[left], &a[midi]);
//
//	int key = a[left];
//	int hole = left;
//	while (left < right)
//	{
//		//找到右边比key小的值
//		while (left < right && a[right] >= key)
//		{
//			right--;
//		}
//		a[hole] = a[right];
//		hole = right;
//
//		//左边比key大的值
//		while (left < right && a[left] <= key)
//		{
//			left++;
//		}
//		a[hole] = a[left];
//		hole = left;
//	}
//	a[hole] = key;
//	return hole;
//}


//前后指针法
int PartSort(int* a, int left, int right)
{
	int midi = GetMidIndix(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int keyi = PartSort(a, begin, end);
	//分成[begin,keyi-1] keyi [keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

3.1.2 快速排序的特性总结

  1. 时间复杂度：O(N*logN)

在这里插入图片描述

  1. 空间复杂度：O(logN)
  2. 稳定性：不稳定

四、非递归实现快排

思路：

  1. 定义一个栈，然后将待排序的数组的起始索引和结束索引入栈。
  2. 通过前面将的三种分割区间的方法将数组的起始索引和结束索引之间的元素分成两部分，左边部分小于等于基准元素，右边部分大于等于基准元素。
  3. 由于非递归实现时，我们是通过从栈中两两取出维护待排序数组的下标，所以接下来就是如果左边部分的长度大于1，则将左边部分的起始索引和结束索引入栈；如果右边部分的长度大于1，则将右边部分的起始索引和结束索引入栈。最后循环此操作，直到栈为空。

代码如下：

//前后指针法
int PartSort(int* a, int left, int right)
{
	int midi = GetMidIndix(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

//快排非递归
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	STInit(&st);
	STPush(&st, end);
	STPush(&st, begin);

	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);

		int right = STTop(&st);
		STPop(&st);

		int keyi = PartSort(a, left, right);
		//[left,keyi-1] keyi [keyi+1,right]
		if (keyi + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, keyi + 1);
		}

		if (keyi - 1 > left)
		{
			STPush(&st, keyi - 1);
			STPush(&st, left);
		}
	}

	STDestroy(&st);
}

五、快排优化稳定为O（N）

5.1 “数组分3块”思想，实现快排

 假设我们现在有一数组（只包含0， 1， 2），现在我们要对他排升序！那如何排了？
 其实我们发现排完序后，整个数组可分为3部分，第一部分全为0，第二部分全为1，第三部分全为2。所以我们直接遍历数组，然后分别用left和right两个指针用于标记第一部分的结尾和第三部分的开头位置（初始值left= - 1, right = n）。所以最终分类讨论如下：
在这里插入图片描述

5.2 “随机基准值 + 快排”将快速选择算法复杂度稳定到O(N)

 数组分三块 + 随机选择基准元素！！！

int findKthLargest(vector<int>& nums, int k) {
    srand(time(nullptr));
    qsort(nums, 0, nums.size() - 1);
}

void qsort(vector<int>& nums, int l, int r)
{
	if(l >= r) return;
    //获得随机基准值
    int key = getRandom(nums, l, r);

    //元素分3块
    int left = l - 1, right = r + 1, i = l;
    while(i < right)
    {
        if(nums[i] < key)
            swap(nums[++left], nums[i++]);
        else if(nums[i] > key)
            swap(nums[--right], nums[i]);//i不要++，右边还未排序
        else 
           i++;
    }
    qsort(l, left);
    qsort(r, right);
}

int getRandom(vector<int>& nums, int l, int r)
{
    return nums[rand() % (r - l + 1) + l];
}

六、非递归版本

int PartSort(std::vector<int>& arr, int left, int right)
{
	int keyi = left;
	int prev = left, cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			std::swap(arr[cur], arr[prev]);
		}
		cur++;
	}
	std::swap(arr[keyi], arr[prev]);
	return prev;
}

void QSortNonR(std::vector<int>& arr, int left, int right)
{
	std::stack<std::pair<int, int>> st;
	st.push(std::make_pair(left, right));
	while (!st.empty())
	{	
		// C++17新增语法，更方便，但我的编译器不支持， 该行和下面两行代码等价
		//auto [begin, end] = st.top(); 
		auto top = st.top(); st.pop(); 
		int begin = top.first, end = top.second;
		if (begin >= end) continue;
		int keyi = PartSort(arr, begin, end);
		// [begin, keyi - 1] prev [keyi + 1, end]
		st.push(std::make_pair(keyi + 1, end));
		st.push(std::make_pair(begin, keyi - 1));
	}
}

在这里插入图片描述
在这里插入图片描述

# 排序算法 # 算法 # 数据结构 # c语言 # c++
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

OpenLoong项目通过技术监督委员会（TOC）评审

OpenLoong项目通过技术监督委员会（TOC）评审

avatar 开放原子开发者工作坊

开发者谈开源：KWDB开源数据库的未来路径与生态构建实践

开发者谈开源：KWDB开源数据库的未来路径与生态构建实践

avatar 开放原子开发者工作坊

开发者谈开源：洞悉协作创新背后的机遇与挑战

近日，在2024开放原子开发者大会暨首届开源技术学术大会开幕式上，开放原子开源基金会与openKylin、EasyAda、KWDB开源项目举行捐赠签约仪式。 一场捐赠签约仪式，让三个开源项目及其背后的开发者们受到瞩目。本次，我们与“龘”（EasyAda）核心维护者王伶卓开启了对话。

avatar 开放原子开发者工作坊