首页 > 编程语言 >排序算法：快速排序

排序算法：快速排序

时间：2022-12-04 21:34:26浏览次数：58  
标签：arr right 基准值 int keyi 算法 排序 快速 left

简介

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！

至于为什么就是比相同时间复杂度的算法快，参考《算法艺术与信息学竞赛》如下信息：

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

算法

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

  1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
  2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
  3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

算法图示：

挑选基准值

选取基准值有数种具体方法，我们从最基本的开始。

基准值是可以任意选取的，那么最简单的我们通常选用待排序序列中的第一个元素作为基准值，但是伴随着一些问题，所以常常采用如下两种方式：

  1. 随机选取基准值。
  2. 选取区间两端和中间的数据中的中位数作为基准值。

分割

升序序列：

将比基准值大的数都放在基准值后面，比基准值小的数放在基准值的前面

降序序列：

将比基准值大的数都放在基准值前面，比基准值小的数放在基准值的后面

常用方法：

  1. hoare
  2. 挖坑法
  3. 快慢双指针

递归子序列

递归的可靠性

基准的左边全都是小于基准的值，而基准的右边全是大于基准的数，说明基准数在排序后的位置是不变的，那么将左子序列和右子序列分别排序，那么这个序列一定是有序的。于是我们递归调用快排将左子序列和右子序列排序，就可以完成排序。

结束条件

如果当前序列已经没有元素或者仅仅只有一个元素，那么我们认为此序列已经有序，无需排序，结束递归。

递归优化

定义排序n个元素问题为 T(n)。

递归的最好情况是每一此递归的序列选取的基准值都是中位数，那么相当于每次将序列二分，分成两个子问题T(n/2)，因此可以看作递归一颗高度为 log(n) 的二叉树，每一层分割时间复杂度都是O(n)，所以时间复杂度为O(nlog(n)).

最坏情况是每一次递归的序列选取的基准值都是当前序列中的最大值或最小值，那么它会被分割子问题T(1)和T(n - 1)，那么那么递归次数是线性的，每一层分割的时间复杂度都是O(n)，所以时间复杂度为O(n2)。

因此对于一些特殊情况下需要排序的序列，例如本就是单调的序列，那么应避免使用序列两端的值作为基准。

有如下处理方法。

  1. 三数取中法选基准值
  2. 随机取基准值

观察log(n)的图像：

image-20220518221351079

随着x的增大斜率是逐渐减小的，也就是说在x较大时，x的变化引起的y的变化更小，因此，在数值较大时，log(n)比n要小得多，而在x较小时（通常为x < 8），它们之间得差别并不大，但是栈帧的开辟的开销是比较大的，这时候只需要排序几个数时，递归所带来的栈帧开销就显得比较浪费资源。

所以在数据个数较少时，为了减少栈帧得开销，可以选择插入排序的策略。（个人认为不会带来很大的效率提升，在release版本下栈帧的开辟优化后与使用插入法效率上的差异并不大。）

如下处理方法：

  1. 递归序列元素个数较少时采用插入排序

挑选基准值以及分割子区间

既然有用到递归，那么代码通常会比较简洁，我们先统一选取第一个元素为基准值作为示范，展示几种不同的方法分割序列。

hoare

考虑定义双指针 left , right 分列数组左右两端，循环执行：

  1. 指针 right 从左向右寻找比基准值大的数；
  2. 指针 left 从右向左寻找比基准值小的数；
  3. 将 arr[left] 和 arr[right] 交换。

可始终保证： 指针 left 左边都是小于基准值的数，指针 right 右边都是大于基准值的数。

算法流程：

  1. 初始化： 初始化left, right 双指针，分别指向数组 arr 左右两端；
  2. 循环交换： 当 left = right 时跳出；
    1. 指针 right 遇到比基准值小的值则执行 right-- 跳过，直到找到大于基准的值；
    2. 指针 left 遇到比基准值大的值则执行 left++ 跳过，直到找到小于基准的值；
    3. 交换 arr[left] 和 arr[right] 值；

注意：left指针和right指针的谁先移动很重要，这决定了最终left和right会停留在小于基准的最后一个位置还是停留在此位置的下一个位置。

动图如下：

代码：

int PartSort(int* arr, int left, int right)
{
	int keyi = left;
	int key = arr[keyi];
	while (left < right)
	{
		while (left < right && arr[right] >= key)
			--right;
		while (left < right && arr[left] <= key)
			++left;
		swap(arr + left, arr + right);
	}
	swap(arr + keyi, arr + left);
	return left;
}

优化

三数取中法选基准值

int GetMid(int* arr, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (arr[left] < arr[mid])
		swap(arr + left, arr + mid);
	if (arr[left] < arr[right])
		swap(arr + left, arr + right);
	if (arr[mid] < arr[right])
		swap(arr + mid, arr + right);
	return mid;//返回中间值的下标
}

int PartSort(int* arr, int left, int right)
{
	int keyi = GetMid(arr, left, right);
	int key = arr[keyi];
	swap(arr + keyi, arr + left);//将key与left交换，后面的过程即与前面相同
	keyi = left;
	while (left < right)
	{
		while (left < right && arr[right] >= key)
			--right;
		while (left < right && arr[left] <= key)
			++left;
		swap(arr + left, arr + right);
	}
	swap(arr + keyi, arr + left);
	return left;
}

随机选取基准值

int PartSort(int* arr, int left, int right)
{
	int keyi = left + rand() % (right - left + 1);
	int key = arr[keyi];
	swap(arr + keyi, arr + left);
	keyi = left;
	while (left < right)
	{
		while (left < right && arr[right] >= key)
			--right;
		while (left < right && arr[left] <= key)
			++left;
		swap(arr + left, arr + right);
	}
	swap(arr + keyi, arr + left);
	return left;
}

注意：此方法的两指针的遍历顺序和基准值的选取位置有关，基准值在最右和最左边是是不相同的两种情况。

挖坑法

考虑定义双指针 left , right ，和分列数组左右两端和变量key，循环执行：

  1. 将第一个数据存储在key中，形成一个坑位；
  2. 指针 right 从右向左寻找比基准值小的数；
  3. 找到后将数据填入之前的坑位，并且此数据的位置形成新的坑位；
  4. 指针 left 从左向右寻找比基准值大的数；
  5. 找到后将数据填入之前的坑位，并且此数据的位置形成新的坑位；

可始终保证left的左边都是小于基准的值，right右边都是大于基准的值

算法流程：

  1. 初始化 left，right双指针，分别指向数组arr的左右两端，key存储arr[left]的值作为基准；
  2. 循环填坑，当left=right时跳出；
    1. 指针 right 遇到比基准大的数则 right--跳过，直到遇到比基准小的值；
    2. 将找到的值填坑，并更新坑的位置为当前位置；
    3. 指针 left 遇到比基准小的数则 left++跳过，直到遇到比基准大的值；
    4. 将找到的值填坑，并更新坑的位置为当前位置；

动图如下：

代码：

int PartSort(int* arr, int left, int right)
{
	int keyi = left;
	int key = arr[left];
	int pit = left;
	while (left < right)
	{
		while (left < right && arr[right] >= key)
			right--;
		arr[pit] = arr[right];
		pit = right;
		while (left < right && arr[left] <= key)
			left++;
		arr[pit] = arr[left];
		pit = left;
	}
	arr[pit] = key;
	return pit;
}

优化

三数取中法选基准值

int GetMid(int* arr, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (arr[left] < arr[mid])
		swap(arr + left, arr + mid);
	if (arr[left] < arr[right])
		swap(arr + left, arr + right);
	if (arr[mid] < arr[right])
		swap(arr + mid, arr + right);
	return mid;
}

int PartSort(int* arr, int left, int right)
{
	int keyi = GetMid(arr, left, right);
	swap(arr + left, arr + keyi);
	int key = arr[left];
	int pit = left;
	while (left < right)
	{
		while (left < right && arr[right] >= key)
			right--;
		arr[pit] = arr[right];
		pit = right;
		while (left < right && arr[left] <= key)
			left++;
		arr[pit] = arr[left];
		pit = left;
	}
	arr[pit] = key;
	return pit;
}

随机选取基准值

int PartSort(int* arr, int left, int right)
{
	int keyi = rand() % (right - left + 1) + left;	
	swap(arr + left, arr + keyi);
	int key = arr[left];
	int pit = left;
	while (left < right)
	{
		while (left < right && arr[right] >= key)
			right--;
		arr[pit] = arr[right];
		pit = right;
		while (left < right && arr[left] <= key)
			left++;
		arr[pit] = arr[left];
		pit = left;
	}
	arr[pit] = key;
	return pit;
}

快慢双指针

考虑定义前后双指针于序列头部，循环执行：

  1. 双指针 cur 和 prev ，cur 在前， prev 在后 ；

  2. cur 的作用是向前搜索比基准值小位置 ，prev 的作用是指向存放当前小于基准值的最后一个位置；

  3. cur 向前移动，当它搜索到大于基准值的数时，将它和 arr[++prev] 交换，此时 prev 向前移动一个位置 ；

可始终保证prev的左边全为比基准值小的数，prev和cur之间全为比基准值大或者等于基准的数；

算法流程：

  1. 初始化：prev指向序列的第一个元素，cur指向序列的第二个元素；
  2. 循环交换：直到cur遍历完所以元素；
    1. 指针cur遇到大于基准的数则cur++跳过，直到遇到小于基准的数；
    2. ++prev，交换arr[cur] 和 arr[prev]的值，++cur继续遍历;

动图如下：

代码：

int PartSort(int* arr, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int key = arr[left];
	while (cur <= right)
	{
		if (arr[cur] <= key && arr[++prev] != arr[cur])//这里也可以写成++prev != cur
			swap(arr + prev, arr + cur);
		++cur;
	}
	swap(arr + prev, arr + left);
	return prev;
}

优化

三数取中法选基准值

int GetMid(int* arr, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (arr[left] < arr[mid])
		swap(arr + left, arr + mid);
	if (arr[left] < arr[right])
		swap(arr + left, arr + right);
	if (arr[mid] < arr[right])
		swap(arr + mid, arr + right);
	return mid;
}

int PartSort(int* arr, int left, int right)
{
	int keyi = GetMid(arr, left, right);
	swap(arr + left, arr + keyi);
	int prev = left;
	int cur = left + 1;
	int key = arr[left];
	while (cur <= right)
	{
		if (arr[cur] <= key && arr[++prev] != arr[cur])//这里也可以写成++prev != cur
			swap(arr + prev, arr + cur);
		++cur;
	}
	swap(arr + prev, arr + left);
	return prev;
}

随机选取基准值

int PartSort(int* arr, int left, int right)
{
	int keyi = rand() % (right - left + 1) + left;
	swap(arr + left, arr + keyi);
	int prev = left;
	int cur = left + 1;
	int key = arr[left];
	while (cur <= right)
	{
		if (arr[cur] <= key && arr[++prev] != arr[cur])//这里也可以写成++prev != cur
			swap(arr + prev, arr + cur);
		++cur;
	}
	swap(arr + prev, arr + left);
	return prev;
}

由于cur要找的是小于基准的值，而prev和cur之间都是大于等于基准的值，只有prev和cur紧挨着才会出现arr[++prev]=arr[cur]的情况，因此条件可改为++prev != cur；

递归子序列

代码实现：

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	int pos = PartSort3(arr, left, right);
	QuickSort(arr, left, pos - 1);//递归左子序列
	QuickSort(arr, pos + 1, right);//递归右子序列
}

image-20220518222754335

如图所示，随着递归深度的增加，栈帧的开辟个数也逐层递增，最终会变成只拥有一个元素或者零个元素的子问题，而对于这些一个元素的序列甚至零个元素的序列，也开辟了一块栈帧，而这是完全没有必要的，栈区的资源非常有限，这样做实在浪费，因此我们在处理这种较少规模的问题时，可以采用数据量少时（通常是元素个数小于8）可以使用整体性能比较好的插入排序作为小规模问题的补充。

递归优化：

void InsertSort(int* arr, int sz)
{
	int i = 0;
	for (i = 1; i < sz; i++)
	{
		int j = 0;
		int tmp = arr[i];
		for (j = i - 1; j >= 0; j--)
		{
			if (arr[j] < tmp)//遇到了比目标小的数，不在向前遍历，break
				break;
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = tmp;//插入到最后一个比较数据的后面
	}
}

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)//只有一个或0个元素时已经有序，无需排序
		return;
	if (right - left + 1 <= 8)//子序列元素较少时停止递归而采用插入排序，减少栈帧的开销。
	{
		InsertSort(arr + left, right - left + 1);//插入排序序列的首地址以及元素个数
		return;
	}
	int pos = PartSort3(arr, left, right);
	QuickSort1(arr, left, pos - 1);
	QuickSort1(arr, pos + 1, right);
}

非递归版

模拟压栈

快速排序的递归方法是先对当前序列进行分割，在递归的去分割基准的左右子序列，就像是二叉树的前序遍历或者是层序遍历，因此我们可以自己写出一个栈来模拟逐层分割这个过程。

每一次递归我们的传参都是序列的首地址以及左右边界区间，因此我们模拟这个过程时压入栈中的是需要分割序列的区间。

总之我们的目的是达到对于每个序列都是先分割当前序列，再分割两个子序列。

使用栈模拟：

类比二叉树前序遍历

将左右区间值压入栈，循环执行：

  1. 取栈顶的区间值，然后分割此区间；
  2. 如果子区间的序列无序则分别将两个子区间的值压入栈；
//栈的定义
typedef int DataType;
typedef struct Stack
{
	DataType* a;
	int top;
	int capacity;
}Stack;

void StackInit(Stack* ps);
void StackPush(Stack* ps, DataType x);
void StackPop(Stack* ps);
DataType StackTop(Stack* ps);
void StackDestory(Stack* ps);
bool StackEmpty(Stack* ps);
void StackPrint(Stack* ps);

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//以双指针分割法为例
int PartSort(int* arr, int left, int right)
{
	int keyi = left + rand() % (right - left + 1);
	swap(arr + left, arr + keyi);
	int key = arr[left];
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (arr[cur] < key && arr[++prev] != arr[cur])
			swap(arr + prev, arr + cur);
		cur++;
	}
	swap(arr + left, arr + prev);
	return prev;
}
//快排非递归
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	//PartSort(arr, left, right);
	Stack s;
	StackInit(&s);
	StackPush(&s, left);
	StackPush(&s, right);
	while (!StackEmpty(&s))
	{
		int end = StackTop(&s);
		StackPop(&s);
		int begin = StackTop(&s);
		StackPop(&s);
		int keyi = PartSort(arr, begin, end);
		if (begin < pos - 1)
		{
			StackPush(&s, begin);
			StackPush(&s, keyi - 1);
		}
		if (pos + 1 < end)
		{
			StackPush(&s, keyi + 1);
			StackPush(&s, end);
		}
	}
	StackDestory(&s);
}

使用队列模拟：

类比二叉树层序遍历

将左右区间值入队，循环执行：

  1. 取队列前端的区间值，然后分割此区间；
  2. 如果子区间的序列无序则分别将两个子区间的值入队；
typedef int DataType;
typedef struct QNode
{
	DataType val;
	struct QNode* next;

}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* tail;
}Queue;
//链表结构
void QueueInit(Queue* pq);
void QueuePush(Queue* pq, DataType val);
void QueuePop(Queue* pq);
size_t QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
void QueueDestory(Queue* pq);
DataType QueueFront(Queue* pq);
DataType QueueBack(Queue* pq);

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
		return;
	Queue q;
	QueueInit(&q);
	QueuePush(&q, left);
	QueuePush(&q, right);
	while (!QueueEmpty(&q))
	{
		int begin = QueueFront(&q);
		QueuePop(&q);
		int end = QueueFront(&q);
		QueuePop(&q);
		int keyi = PartSort(arr, begin, end);
		if (begin < keyi - 1)
		{
			QueuePush(&q, begin);
			QueuePush(&q, keyi);
		}
		if (keyi + 1 < end)
		{
			QueuePush(&q, keyi + 1);
			QueuePush(&q, end);
		}
	}
	QueueDestory(&q);
}

标签：arr,right,基准值,int,keyi,算法,排序,快速,left
From： https://www.cnblogs.com/ncphoton/p/16950874.html

相关文章

  • 排序算法：比较排序
    算法简介：排序排序是一个非常经典的问题，它以特定顺序（递增、非递减（递增或扁平））对数组（或列表）的项目（可以比较，例如整数、浮点数、字符串等）进行重新排序)、递减、非递增（递减或平......
  • 排序算法：非比较排序
    堆排序voidAdjustDown(int*arr,intsz,introot)//向下调整{ intparent=root; intchild=root*2+1; while(child<sz) { if(child+1<sz&&ar......
  • 排序算法：归并排序
    递归实现void_MergeSort(int*arr,intleft,intright,int*tmp){ if(left>=right) return; intmid=left+(right-left)/2; _MergeSort(arr,left,......
  • 快速创建spring boot 项目
    因为我装的是社区版idea, 不能安装springinitializer插件，所以只能在网站上create.GENERATE 然后下载下来即可：https://start.spring.io/ ......
  • 卡尔曼滤波之最优状态估计和最优状态估计算法
    1.最优状态估计情景1：假设一个一个比赛中，不同队伍的自动驾驶汽车使用GPS定位，在100种不同的地形上各行驶1公里。每次都尽可能停在终点。然后计算每只队伍的平均最终......
  • 页式存储管理--两种置换算法的实现
    一.实验目的1.了解虚拟存储技术，通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。2.掌握FIFO和LRU等置换算法，加强对地址转换过程的了解。二.实验内容......
  • sm-crypto密码算法库
    一、环境配置在之前的node.js库配置中，我们已经配置好了node和npm，再次检查配置情况node-vnpm-vnpminstall--saveminiprogram-sm-crypto二、进入工作目录/usr/l......
  • 第二章 算法基础
    第2章算法基础第二周记于2022/12/4如何描述算法使用一致性符号来分析算法的运算时间通过归并排序来学习分而治之方法插入排序......
  • 如何用JDK优雅的实现几个算法
    今天给大家介绍下八股文中的两个重要成员，LinkedHashMap和TreeMap。 这两者都实现了Map接口，也经常会在面试中被拿来与HashMap比较。 到底它们能使用哪些魔法呢，接下来......
  • 排序链表 重排链表 最接近目标价格的甜点成本 环形链表
    148.排序链表弄到数组里，数组排序，再弄个新链表Listlist=newArrayList<>();ListNodepre=head;while(pre!=null){list.add(pre.val);pre=pre.next;}int[......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99