首页 > 编程语言 >算法与数据结构——快速排序

算法与数据结构——快速排序

时间:2024-09-26 16:35:48浏览次数:6  
标签:排序 nums 基准 算法 right 数组 数据结构 left

快速排序

快速排序(quick sort)是一种基于分治策略的排序算法,运行高效,应用广泛。

快速排序的核心操作是“哨兵划分”,其目标是::选择数组中的某个元素作为“基准数”,将所有小于基准数的元素移到其左侧,而大于基准数的元素移到其右侧。具体流程如下:

  1. 选取数组最左端元素作为基准数,初始化两个指针i和j分别指向数组的两端。
  2. 设置一个循环,在每轮中使用i(j)分别寻找第一个比基准数大(小)的元素,然后交换这两个元素。
  3. 循环执行步骤2.,直到i和j相遇时停止,最后将基准数交换至两个子数组的分界线。

哨兵划分

  • 给定一个左指针left和右指针right分别指向数组两端元素,再定义两个变量i,j分别指向leftright,并将left指向的元素设为基准数

  • 利用变量j,从右往左遍历,找到首个小于基准数的元素

  • 利用变量i,从左往右遍历,找到首个大于基准数的元素

  • 交换i和j指向的元素,保证j以及右边的数都大于基准数,保证i以及左边的数都小于基准数(不包括基准数)

  • 继续执行上述过程,对j继续向左寻找到首个小于基准数的元素,对i继续向右寻找首个大于基准数的元素,直至i和j相遇

  • 相遇时即保证了左侧(不包括基准数)都小于基准数,右侧都大于基准数,由于先对j执行向左遍历寻找小于基准数的元素,最后相遇处一定是小于基准数的元素,此时交换相遇处的元素与基准数,即可保证基准数左侧小于基准数,右侧大于基准数。

  • 此时,完成了“哨兵划分”,将数组分成了左子数组、基准数、右子数组,且满足“左子数组任意元素 ≤ 基准数 ≤ 右子数组任意元素”。接下来,只需对这两个子数组进行排序。

快速排序的分治策略
哨兵划分的实质是将一个较长的数组的排序问题简化为两个较短数组的排序问题。

/*哨兵划分*/
int partition(vector<int> &nums, int left, int right){
	// 以 nums[left] 为基准数
	int i = left, j = right;
	while (i < j){
		while (i < j && nums[j] >= nums[left]){
			j--; // 从右向左找首个小于基准数的元素
		}
		while (i < j && nums[i] <= nums[left]){
			i++; // 从左向右找首个大于基准数的元素
		}
		swap(nums[i], nums[j]);// 交换这两个元素
	}
	swap(nums[left], nums[i]); // 将基准数交换至两子数组的分界线
	return i; // 返回基准数的索引
}

算法流程

  1. 首先,对原数组执行一次“哨兵划分”,得到未排序的左子数组和右子数组。
  2. 然后对左子数组和右子数组分别递归执行“哨兵划分”。
  3. 持续递归,直至数组长度为1时终止,从而完成整个数组的排序。
/*快速排序*/
void quickSort(vector<int> &nums, int left, int right){
	// 子数组长度为1时终止递归
	if (left >= right)
		return;
	// 哨兵划分
	int pivot = partition(nums, left, right);
	// 递归左、右子数组
	quickSort(nums, left, pivot - 1);
	quickSort(nums, pivot + 1, right);
}

算法特性

  • 时间复杂度O(nlogn)、自适应排序:在平均情况下,哨兵划分的层数为logn,每层中的总循环数为n,总体使用O(nlogn)时间。最差情况下,每轮哨兵划分操作都将长度为n的数组划分为长度为0和n-1的两个子数组,此时递归层数达到n,每层中的循环数为n,总体使用O(n2)时间。
  • 空间复杂度O(n)、原地排序:在输入数组完全倒序的情况下,达到最差递归深度n,使用O(n)栈帧空间。排序操作是在原数组上进行的,未借助额外数组。
  • 非稳定排序:在哨兵划分的最后一步,基准数可能会被交换至相等元素的右侧。

快速排序为什么快

从名称上就能看出,快速排序再效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与“归并排序”和“堆排序”相同,但通常快速排序的效率更高,主要有以下原因:

  • 出现最差情况的概率很低:虽然快速排序的最差时间复杂度为O(n2),没有归并排序稳定,但在绝大多数情况下,快速排序能在O(nlogn)的时间复杂度下运行。
  • 缓存使用效率高:在执行哨兵划分操作时,系统可将整个子数组加载到缓存,因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素,从而缺乏这一特性。
  • 复杂度的常数系数小:在上述三种算法中,快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。

基准数优化

快速排序再某些输入下的时间效率可能降低。举一个极端例子,假设输入数组是完全倒序的,由于我们选择最左端的元素作为基准数,那么在哨兵划分完成后,基准书被交换至数组最右端,导致左子数组长度为n-1、右子数组长度为0。如此递归下去,每轮哨兵划分后都有一个子数组长度为0,分治策略失效,快速排序退化为“冒泡排序近似形式”。

为了尽量避免这种情况发生,我们可以优化哨兵划分中的基准数的选取策略。例如,我们可以随机选取一个元素作为基准数,但有可能每次都选到不理想的基准数,效率仍然不尽人意。

为了进一步改进,我们可以在数组中选取三个候选元素(通常为数组首、尾、中点元素),并将这三个候选元素的中位数作为基准数。这样一来,基准数“既不太小也不太大”的概率将大幅提升。采用这种方法后,时间复杂度劣化至O(n2)的概率大大降低。

/*选取三个候选元素的中位数*/
int medianThree(vector<int> &nums, int left, int mid, int right){
	int l = nums[left], m = nums[mid], r = nums[right];
	if ((l <= m && m <= r) || (l >= m && m >= r))
		return mid;
	if ((m <= l && l <= r) || (m >= l && l >= r))
		return left;
	return right;
}
/*哨兵划分*/
int partition(vector<int> &nums, int left, int right){
	// 选取三个候选元素的中位数
	int med = medianThree(nums, left, (left + right) / 2, right);
	// 将中位数交换至数组最左端
	swap(nums[left], nums[med]);
	// 以 nums[left] 为基准数
	int i = left, j = right;
	while (i < j){
		while (i < j && nums[j] >= nums[left]){
			j--; // 从右向左找首个小于基准数的元素
		}
		while (i < j && nums[i] <= nums[left]){
			i++; // 从左向右找首个大于基准数的元素
		}
		swap(nums[i], nums[j]);// 交换这两个元素
	}
	swap(nums[left], nums[i]); // 将基准数交换至两子数组的分界线
	return i; // 返回基准数的索引
}

尾递归优化

在某些输入下,快速排序可能占用空间较多。以完全有序的输入数组为例,设,递归中的子数组长度为m,每轮哨兵划分操作都将产生长度为0的左子数组和长度为m-1的右子数组,这意味着每一层递归调用减少的问题规模非常小(只减少一个元素),递归树的高度会达到n-1,此时需要占用O(n)大小的栈帧空间。

为了防止栈帧空间的积累,我们可以在每轮哨兵排序完成后,比较两个子数组的长度,仅对较短的子数组进行递归。由于较短子数组的长度不会超过n/2,因此这种方法能确保递归深度不会超过logn,从而将最差空间复杂度优化至O(logn)。

/* 快速排序(尾递归优化) */
void quickSort(vector<int> &nums, int left, int right) {
	// 子数组长度为 1 时终止
	while (left < right) {
		// 哨兵划分操作
		int pivot = partition(nums, left, right);
		// 对两个子数组中较短的那个执行快速排序
		if (pivot - left < right - pivot) {
			quickSort(nums, left, pivot - 1); // 递归排序左子数组
			left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
		}
		else {
			quickSort(nums, pivot + 1, right); // 递归排序右子数组
			right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
		}
	}
}

标签:排序,nums,基准,算法,right,数组,数据结构,left
From: https://www.cnblogs.com/1873cy/p/18432979

相关文章

  • JAVA 数据结构与算法 队列的介绍与应用
    一、队列队列是一个有序列表,可以用数组或者链表来实现遵循先入先出的原则。当我们将数据存入队列时称为”addQueue”,addQueue的处理需要有两个步骤:思路分析:将尾指针往后移:rear+1,当front==rear【空】若尾指针rear小于队列的最大下标maxSize-1,则将数据存入rear所......
  • 【数据结构.总集篇】第一章 链表
    文章目录1.链表1.1线性表1.2顺序表1.3单链表链表简介单链表的介绍线性表的链式存储头节点概念为何引入头结点单链表的基本操作创建一个单链表初始化头插法尾插法删除操作打印总代码1.4单链表循环1.5双链表双链表的定义双链表上的操作初始化插入操作头插法尾插法......
  • 字符串从入门到退竞(2)——KMP 算法
    约定在文字描述中字符串下标从\(1\)开始,代码中从\(0\)开始。前缀函数对于长\(n\)的字符串\(S\),其前缀函数是一个长\(n\)的数组(数列)\(\pi\),定义如下:若\(S[1..i]\)有相等的真前缀和真后缀(称之为border),\(\pi[i]\)为其长度的最大值;若不存在,\(\pi[i]=0\)。字符串的......
  • RabbitMq 入门应用 提升性能 : 算法多阶段并行 (Python)
    大问题:我们有一个算法,它可以被分为多个阶段进行(顺序不可颠倒),每个阶段的性能和资源要求不同(且不均衡程度比较高);假设我们现在可以堆资源(较多的CPU和内存),如何将算法各个步骤拆分并进行性能均衡和实现,使得算法性能最大化以满足生产要求?多进程:由于算法有严格的顺序要求,如果是......
  • 老鼠检测、厨房老鼠检测、老鼠识别算法
    老鼠检测算法主要用于家庭、餐饮行业、仓储物流、医疗设施等领域的鼠患监控,通过图像识别技术来检测和识别视频或图像中的老鼠。这种技术可以帮助管理者实时监控老鼠活动,及时采取措施,防止鼠患带来的健康和经济损失。一、技术实现老鼠检测算法通常依赖于计算机视觉和深度学习技术,通......
  • 本科学历能找到人工智能算法岗位的工作吗?好就业吗?
    随着科技的发展,人工智能技术在各行各业的应用日益广泛,催生了大量专注于人工智能的企业,这些企业在招聘网站上发布了众多相关岗位,并且这些岗位的薪资普遍高于其他行业岗位,因此越来越多求职者渴望进入这一行业。对于同样有这一愿景的本科生来说,他们常常会问:“我本科学历能找到人工智能......
  • 【图计算算法‌】基于路径依赖的图计算算法‌
    目录一、基于路径依赖的图计算算法‌概述二、基于路径依赖的图计算算法‌主要特点三、基于路径依赖的图计算算法‌优缺点和改进2.1  基于路径依赖的图计算算法‌优点3.2  基于路径依赖的图计算算法‌缺点3.3  基于路径依赖的图计算算法‌改进四、 基于路径依赖的......
  • 要不要入行大模型算法啊?
    最近又有不少私信问我关于要不要入行大模型之类的问题,年初的时候我写过一篇相同主题的笔记,时隔8个月,今时不同往日,想法确实有些变化,再说一说这个问题。先讨论算法相关的方向,分成三部分吧pretrain、post-training和更偏应用的工作pretrain的机会应该是越来越少了,还能在......
  • [算法] A LITTLE 网络流
    简介所谓网络流,就是给了一张图,有源点和汇点,让你求从源点放水,到汇点的水最多能有多少;这实际上是一个最大流的问题;最大流我们把这张图的每个边看作一条水管,每个水管都有一个容量,那么对于一条从源点到汇点的路径,其最大通过量是这些水管中容量最小的那一个的容量;对于这个问题,我们......
  • 算法与数据结构——简单排序算法(选择、冒泡、插入)
    简单排序算法时间复杂度均为O(n2)选择排序选择排序(selectionsort)的工作原理非常简单:开启一个循环,每轮从未排序区间选择最小的元素,将其放到已排序的区间的末尾。算法流程设数组长度为n,选择排序的算法流程如下。初识状态下,所有元素未排序,即未排序(索引)区间为[1,n-1]。选取......