【数据结构】快速排序详解!

文章目录

      • 1. 快速排序的非递归版本
      • 2. 快速排序
        • 2.1 hoare 版本一
        • 2.2 挖坑法 🐧版本二
        • 2.3 前后指针 版本三
        • 2.4 调用以上的三个版本的快排
      • 3. 快速排序的优化

1. 快速排序的非递归版本

🆒🐧关键思路:
🍎① 参数中的beginend来界定,是随着函数的调用自动保存在栈帧中的,而我们需要用这种数据结构来模拟这个过程。

🍎② 如果决定先排 keyi左边的元素的话,就要先把 keyi右边的元素先入栈(因为栈是后进先出的)

🍎③ 每次取两个元素,分别表示待排序区间下标的 起点和终点。

🍎④ if (left < keyi - 1)if (keyi + 1 < right)因为要保证遍历的区间是有效的,所以需要这两个判断。

  • 先把 key 左边的区间都按照规律入栈然后排序,只有把 key左边的都排好序之后,才会开始走 key右边的逻辑
    在这里插入图片描述

在这里插入图片描述

// 快速排序的非递归法
void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(&s);STPush(&s, end);STPush(&s, begin);while (!STEmpty(&s)){int left = STTop(&s);STPop(&s);int right = STTop(&s);STPop(&s);int keyi = PartSort3(a, left, right);// [left, keyi-1] keyi [keyi+1, right]if (left < keyi - 1){STPush(&s, keyi - 1);STPush(&s, left);}if (keyi + 1 < right){STPush(&s, right);STPush(&s, keyi + 1);}}STDestroy(&s);
}

2. 快速排序

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

  • 🆒快速排序有三个版本:
2.1 hoare 版本一

在这里插入图片描述

int PartSort1(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}


2.2 挖坑法 🐧版本二

在这里插入图片描述

int PartSort2(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int key = a[begin];int hole = begin;while (begin < end){// 右边找小,填到左边的坑while (begin < end && a[end] >= key){--end;}a[hole] = a[end];hole = end;// 左边找大,填到右边的坑while (begin < end && a[begin] <= key){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = key;return hole;
}


2.3 前后指针 版本三

在这里插入图片描述

int PartSort3(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}
2.4 调用以上的三个版本的快排
// [begin, end]
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);	// 此处修改需要调用的版本QuickSort(a, begin, keyi - 1);QuickSort(a, keyi+1, end);
}


3. 快速排序的优化

  • 🍎① 三数取中法选 key
    如果不采取三数取中的方法,万一每次快排的 key都是待排序中的最大值,此时每次只能将一个数据变成有序,此时的效率极低,所以需要优化。
    在这里插入图片描述
int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;// begin midi end 三个数选中位数if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else // a[begin] > a[midi]{if (a[midi] > a[end])return midi;else if (a[begin] < a[end])return begin;elsereturn end;}
}
  • 🍎② 递归到小的子区间时,可以考虑使用插入排序.
    当小区间的时候,因为用递归的话,会消耗更多的资源,效率较低。
    在这里插入图片描述

在这里插入图片描述

void QuickSort(int* a, int begin, int end)
{if (begin >= end)		return;if (end - begin + 1 <= 10){InsertSort(a + begin, end - begin + 1);}else{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/332530.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

呆马科技----构建智能可信的踏勘云平台

近年来&#xff0c;随着信息技术的快速发展&#xff0c;各个行业都在积极探索信息化的路径&#xff0c;以提升工作效率和服务质量。智慧踏勘云平台是基于区块链和大数据技术构建的全流程智慧可信踏勘解决平台。平台集远程视频、数据显示、工作调度、过程记录为一体&#xff0c;…

嵌入式进阶——舵机控制PWM

&#x1f3ac; 秋野酱&#xff1a;《个人主页》 &#x1f525; 个人专栏:《Java专栏》《Python专栏》 ⛺️心若有所向往,何惧道阻且长 文章目录 舵机信号线代码示例初始化PWM初始化UART打印日志初始化外部中断Extimain函数 舵机最早用于船舶上实现转向功能,由于可以通过程序连…

Spring从零开始学使用系列(四)之@PostConstruct和@PreDestroy注解的使用

如果各位老爷觉得可以&#xff0c;请点赞收藏评论&#xff0c;谢谢啦&#xff01;&#xff01; 文章中涉及到的图片均由AI生成 公众号在最下方&#xff01;&#xff01;&#xff01; 目录 1. 介绍 1.1 PostConstruct概述 1.2 PreDestroy概述 2. 基本用法 2.1 注册CommonAnn…

JS根据所选ID数组在源数据中取出对象

let selectIds [1, 3] // 选中id数组let allData [{ id: 1, name: 123 },{ id: 2, name: 234 },{ id: 3, name: 345 },{ id: 4, name: 456 },] // 源数据let newList [] // 最终数据selectIds.map((i) > {allData.filter((item) > {item.id i && newList.pus…

MyBatis复习笔记

3.Mybatis复习 3.1 xml配置 properties&#xff1a;加载配置文件 settings&#xff1a;设置驼峰映射 <settings><setting name"mapUnderscoreToCamelCase" value"true"/> </settings>typeAliases&#xff1a;类型别名设置 #这样在映射…

力扣刷题---LCS 02. 完成一半题目【简单】

题目描述 有 N 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N 道题目&#xff0c;整型数组 questions 中每个数字对应了每道题目所涉及的知识点类型。 若每位扣友选择不同的一题&#xff0c;请返回被选的 N 道题目至少包含多少种知识点类型。 示例 1&…

MySQL--InnoDB体系结构

目录 一、物理存储结构 二、表空间 1.数据表空间介绍 2.数据表空间迁移 3.共享表空间 4.临时表空间 5.undo表空间 三、InnoDB内存结构 1.innodb_buffer_pool 2.innodb_log_buffer 四、InnoDB 8.0结构图例 五、InnoDB重要参数 1.redo log刷新磁盘策略 2.刷盘方式&…

自然资源-各级国土空间总体规划的审查要点及流程总结

自然资源-各级国土空间总体规划的审查要点及流程总结 国土空间规划是对一定区域国土空间开发保护在空间和时间上作出的安排&#xff0c;包括总体规划、详细规划和相关专项规划。 国土空间规划管理是国土空间规划中重要的一环。中共中央、国务院发布《关于建立国土空间规划体系…

京东应届生公司内网说了一句‘什么时候被pdd收购‘,结果惨遭辞退

京东应届生公司内网说了一句’什么时候被pdd收购’&#xff0c;结果惨遭公司开除 这个事最近在圈子讨论比较多 前二天&#xff0c;有一个上海交大毕业的应届生&#xff0c;在京东实习了9个月&#xff0c;好不容易转正12天后&#xff0c;只因在内网说了一句话&#xff0c;就被…

释放Mac潜能,选择Magic Disk Cleaner for Mac

想要让Mac运行更加流畅、性能更加出色吗&#xff1f;那就选择Magic Disk Cleaner for Mac吧&#xff01; Magic Disk Cleaner for Mac v2.7.7激活版下载 这款软件是Mac用户的得力助手&#xff0c;它拥有强大的扫描和清理功能&#xff0c;能够迅速找出并删除硬盘上的无用文件和垃…

Linux系统命令traceroute详解(语法、选项、原理和实例)

目录 一、traceroute概述 二、语法 1、基本语法 2、命令选项 三、帮助信息 四、示例 1. 使用默认模式&#xff08;ICMP Echo&#xff09;追踪到目标主机 2. 使用UDP模式&#xff08;需要root权限&#xff09;追踪到目标主机 3. 不解析IP地址为主机名&#xff0c;直接显…

前端已死? Bootstrap--CSS组件

目录 Bootstrap 下载 Bootstrap--全局CSS样式 栅格系统 栅格参数 正常显示 实例 代码演示: 排版 代码演示 表格 代码演示 表单 代码演示 等等...(文档很清晰了) Bootstrap--组件 结合演示:(页面) Bootstrap Bootstrap v3 中文文档 Bootstrap 是最受欢迎的 HT…

leetcode:计数质数

class Solution { public:// 如果 x 是质数&#xff0c;那么大于 x 的 x 的倍数 2x,3x… 一定不是质数int countPrimes(int n) {vector<int> isPrime(n, 1);int ans 0;for (int i 2; i < n; i) {if (isPrime[i]) {ans 1;if ((long long)i * i < n) {for (int j …

二十九篇:构建未来:信息系统的核心框架与应用

构建未来&#xff1a;信息系统的核心框架与应用 1. 引言 在这个充满挑战和机遇的信息时代&#xff0c;信息系统已经成为现代组织不可或缺的神经中枢。它们不仅革新了我们处理信息的方式&#xff0c;更是极大地增强了决策制定的效率和质量。在这篇文章中&#xff0c;我将分享我…

C++ 常用UI库

AWTK github gitee doc scons 类似RT-Thread element github C Cross platfrom C GUI libraries&#xff0c;QT可替代方案。调试包 SDL GUI cegui 创作不易&#xff0c; 小小的支持一下吧&#xff01;

Qt 概述

Qt 背景介绍 什么是 Qt Qt 是⼀个 跨平台的 C 图形⽤⼾界⾯应⽤程序框架 。它为应⽤程序开发者提供了建⽴艺术级图形界⾯所需的所有功能。它是完全⾯向对象的&#xff0c;很容易扩展。Qt 为开发者提供了⼀种基于组件的开发模式&#xff0c;开发者可以通过简单的拖拽和组合来实…

Kafka 安装教程和基本操作

一、简介 Kafka 是最初由 Linkedin 公司开发&#xff0c;是一个分布式、分区的、多副本的、多订阅者&#xff0c;基于 zookeeper 协调的分布式日志系统&#xff08;也可以当做 MQ 系统&#xff09;&#xff0c;常见可以用于 web/nginx 日志、访问日志&#xff0c;消息服务等等…

vue3快速入门(局部使用)

目录 前置知识JavaScript-导入导出 入门操作 变量渲染页面 局部使用vue的实现步骤 vue指令 v-for v-bind v-if v-show v-on v-model 生命周期 前置知识JavaScript-导入导出 正常情况在html导入js文件是全部导入&#xff0c;这样会导致性能上的损失 。 JS提供的…

5. C++网络编程-UDP协议的实现

UDP是无连接的。 UDP Server网络编程基本步骤 创建socket&#xff0c;指定使用UDP协议将socket与地址和端口绑定使用recv/send接收/发送数据 由于UDP是无连接的&#xff0c;直接侦听就行使用close关闭连接 这个UDP接收数据的时候用的API是recvfrom,发送数据是sendto 客户端 …

【html】网页布局模板01---简谱风

模板效果: 这是一种最简单,最干净的一种网页布局。 模板介绍: 模板概述: 这个模板是一个基础的网页布局模板,包括一个头部区域(header),其中包含网站标题(logo)和导航菜单(nav),以及一个页脚区域(copy),用于显示版权信息。整体布局简洁明了,适合作为各种类…