当前课程知识点：程序设计基础 >  第五章 分治思想与递归 >  5.2 排序 >  5.2.5 快速排序——代码解说

返回《程序设计基础》慕课在线视频课程列表

5.2.5 快速排序——代码解说在线视频

5.2.5 快速排序——代码解说

下一节:5.2.6 排序总结

返回《程序设计基础》慕课在线视频列表

5.2.5 快速排序——代码解说课程教案、知识点、字幕

那么假定有一个数组array

它的长度是len

那为了去做实现

刚才所说的这种排序的思想

那我们需要去做如下的一些步骤

首先 这样的一个递归的过程

要写出它的中止条件

就是 如果这个长度小于等于1

那么就直接return

因为你只有一个元素的时候呢

它是不用排的

然后 按照最坏的可能

为两个子数组去分配空间

因为左边是小的 右边是大的

我们得找地方去存它

所以 按照我们刚刚讲过的那个例子里头

学到的new这个运算符的写法

我们new出一个left这个数组的长度是len

right这个数组长度呢也是len

为这两个子数组的长度设定一个初值

现在里头是空的 没有元素

所以呢 left_idx=0 right_idx=0

下面进入到关键环节

把一个长数组拆成两部分

这个拆不是简单拆

要求呢 左半部分都比参照元素小

右半部分都比参照元素大

那 怎么做呢

首先 我们先把参照元素的值取出来

int key =array[0]

把0号元素做参照

当然了 有的教材上也会讲到说

我用任意的数去做参照可能会更好一点

这个方法 大家底下去自己练习一下

我们这里头

为了简单起见用array[0]作为它的参照

那在数组里头的所有的元素

0已经取出去了 做参照了

那剩下的从1到len-1所指的元素

它们要么比参照大

要么比参照的这个元素小

为了简单起见我们假定这个数组里头

这个所有的数都是各不相同的

那么 既然如此

在循环里头就可以写出两个if语句

如果 array[i]小于key 比它小

那我就放到左半部分

根据我们前面那个所学到的

可以写成left(left_idx++)

让它的下标再加

然后呢等于array[i]

因为i是通过for循环控制的

所以呢array[i]

这个i它不用再去写++了

那么当然了这个array[i]也可能是大于key的

所以我们下面又写了一个

if (array[i] > key)

这个时候呢就把它放到right这个子数组里去

right [right_idx++] = array[i]

这两个元素啊 array[i]这个数要么比key小 要么比key大

它不可能即比它大又比它小

所以 虽然我们这边写的是

两个这个样并列的if语句

但是 其实啊

它只会有一个会执行

再次强调一下

我们假定这个数组里的元素是各不相同的

所以 这个元素要么比key大 要么比key小

所以这两个if虽然这么写

但是呢 它只会有一条执行

所以我们避免了去写else

通过这样的一种反复循环

就把array里头的元素依次的每一个分到

要么是left 要么是right里去

那么可以保证

因为left里头每一个都比key小

它当然也会比right里的元素小

因为right数组里头的每一个元素都比key要大

所以你每一个比它小的

当然会小于每一个比它大的那个数组

所以这样的话呢

左右两个部分

在后续的排序过程当中就不会发生交叉

就互相不影响

可以分开来做

所以下面我们就分开来做

调用QuickSort

然后对左半部分排序

对右半部分排序

所以左半部分是什么呢

是left数组

它的个数是left_idx

刚刚是left_idx作为下标来用

但是等到循环完了

这个left_idx就是个数了

同理啊 right这个数组

它的righy_idx就是它的个数

这样的两个子数组的排序

跟我们现在此时此刻正在进行的

array这个数组排序是一样的

所以我们这里头又调用了QuickSort这个函数

自己调自己 对吧

递归程序就是这样子

它总是在一个规模更小的任务上面

去调用同样的算法来完成它

所以看上去就是函数自己在调用自己

其实呢这个

被处理的这个数据的规模已经缩小了

然后 我们就可以把两个排序好的数组

把它合并起来

由于我们已经知道左边

整体上每一个

都会比右边的每一个都要小

所以 这个里边的合并

就比我们前一个例子里讲的

归并的排序要简单

它直接通过两层循环

两次循环就能完成

第一次先对左边的数组的每一个元素循环

把它都复制到array这个数组里去

第二步呢

是把right这个数组去循环

把它复制过去

当然了中间插了一步

就是array[idx++] = key

就是里面参照的那个元素不要丢了

它是放在中间的

实际上是放在两个子数组的中间

它的位置并不见得是整个数组的正中间

因为这个是不一定的

有可能小的元素它没那么多 它就偏左

这个根据不同的被排序的数组来定

这样 所有的有序的

这个结果就送到array里边去了

这个任务就算大功告成了

所以最后一步

把你用的不在用的这两个动态数组给删除掉

delete[ ] left

delete[ ] right

这样就完成了把一个数组拆开来分别去排序

然后再合并这样的一个过程

但是它的这个拆开来

是采取了一个很巧妙的想法

把它拆成整体的比某个参照元素小

整体的比某个参照元素大

这样的规则

从而这两个子数组的排序互相不干扰

而且呢 它最后在合并的时候也变的简单

因为你整体拿过去就行了

这样的一个办法呢

我们把它称之为快速排序法

那么当然了

这个快速排序的算法的实现

也可以不去使用这个动态数组的这种定义

那么 那个时候呢

我们就需要思考出一个巧妙的办法

在这个数组里头啊

原地进行这个数组元素

的倒换来实现参照元素在它该到达的位置去存放

左边的元素都比它小

右边的元素都比它大

这样的一个数组的这种

让它达到这样的一个状态的过程

这个算法留给大家底下去思考

看看怎么能够

不分配动态数组

直接原地的

就把它倒换成这个样子

那么很多经典的

快速排序的算法的实现

是按照我们后面讲的这个思路来实现的

这个留给大家课下自己去练习

看它怎么来完成这样的一个在原地进行调换

保证最后是左边小右边大

整体的 不是有序的

然后再分别再对各自的这个部分进行递归调用去排序

程序设计基础课程列表：

第一章 编程初步

-1.1 基础知识

--1.1.1 什么是程序？什么是语言？

--1.1.2 什么是程序设计？

--1.1.3 计算机发展史

-1.2 买菜问题

--1.2.1 问题描述

--1.2.2 程序的基本结构

-1.3 数学运算

--1.3.1 数学运算符

--1.3.2 数学函数

-1.4 补充说明

--1.4.1 编程环境的下载与安装

--1.4.2 程序基本结构中的含义

--1.4.3 格式与风格

-1.5 总结

--1.5 总结

-程设论道

--程设论道

-师生问答

--师生问答一：怎样学好程序设计

--师生问答二：语言选择

--师生问答三：关于函数

-第一章 编程初步--语法自测

第二章 变量与代数思维

-2.1 关于超级计算器的几点思考

--2.1.1 关于超级计算器的几点思考

-2.2 电子秤模拟 — 背景介绍及需求分析

--2.2.1 电子秤模拟 — 背景介绍及需求分析

-2.3 电子秤模拟 — 代码实现

--2.3.1 电子秤模拟 — 代码实现

-2.4 变量定义与变量类型

--2.4.1 变量定义与变量类型

-2.5 猜数游戏与数据表示

--2.5.1 猜数游戏与数据表示

-2.6 关于变量的讨论

--2.6.1 变量的初始值

--2.6.2 变量类型

--2.6.3 变量内存单元地址

--2.6.4 存“变量地址”的变量——指针

--2.6.5 指针的 读/写 操作

--2.6.6 指针的 加/减 操作

--公告

-2.7 变量体现的计算思维

--2.7.1 变量体现的计算思维

-程设论道

--程设论道

-师生问答

--师生问答

-第二章 变量与代数思维--语法自测

第三章 逻辑推理与枚举解题

-3.1 谁做的好事——语义表示

--3.1.1 谁做的好事——语义表示

-3.2 谁做的好事——真假检查

--3.2.1 谁做的好事——真假检查

-3.3 谁做的好事——循环枚举

--3.3.1 谁做的好事——循环枚举

-3.4 谁是嫌疑犯——多重循环枚举

--3.4.1 谁是嫌疑犯——多重循环枚举

-3.5 谁是嫌疑犯——破案线索表示

--3.5.1 谁是嫌疑犯——破案线索表示

-3.6 谁是嫌疑犯——用二进制枚举

--3.6.1 谁是嫌疑犯——用二进制枚举

-程设论道

--程设论道一

--程设论道二

--程设论道三

-师生问答

--师生问答一：字符与ASCII码表

--师生问答二：其他循环语句、运算符优先级与变量作用域

-第三章 逻辑推理与枚举解题--语法自测

第四章 筛法与查找

-4.1 插花游戏

--4.1.1 问题提出（求素数）

--4.1.2 函数初探

--4.1.3 运行演示

-4.2 筛法

--4.2.1 筛法思路

--4.2.2 数组的定义

--4.2.3 代码翻译

--4.2.4 运行演示

--4.2.5 小朋友数人数

--4.2.6 运行演示

--4.2.7 韩信点兵

-4.3 线性查找

--4.3.1 扑克查找问题

--4.3.2 扑克查找问题代码翻译

--4.3.3 最小值问题

--4.3.4 最小值问题代码翻译

-4.4 折半查找

--4.4.1 提问

--4.4.2 折半查找思路

--4.4.3 折半查找代码翻译

--4.4.4 折半查找运行演示

-4.5 排序问题

--4.5.1 插入排序

--4.5.2 选择排序

--4.5.3 函数写法

--4.5.4 运行演示

-4.6 总结

--4.6.1 总结

-程设论道

--程设论道一：数组与编码思维

--程设论道二：筛法

-师生问答

--师生问答一：函数与面向过程编程

--师生问答二：数组的下标越界

-第四章 筛法与查找--语法自测

第五章 分治思想与递归

-5.1 阶乘

--5.1.1 阶乘问题

--5.1.2 递归解法

--5.1.3 递归小结

-5.2 排序

--5.2.1 归并排序——总体思路

--5.2.2 归并排序——思路分解

--5.2.3 归并排序——代码解说

--5.2.4 快速排序——总体思路

--5.2.5 快速排序——代码解说

--5.2.6 排序总结

-5.3 矩阵填充

--5.3.1 矩阵填充问题

--5.3.2 代码解说

-5.4 分书与八皇后

--5.4.1 问题描述

--5.4.2 问题分析——共性

--5.4.3 问题分析——区别

--5.4.4 解题准备——二维数组

--5.4.5 解题准备——递归设计

--5.4.6 代码解说——分书问题

--5.4.7 代码解说——八皇后问题

-5.5 青蛙过河

--5.5.1 问题描述

--5.5.2 问题分析——简单情况

--5.5.3 问题分析——复杂情况

--5.5.4 问题分析——一般情况

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答一

--师生问答二

-第五章 分治思想与递归--语法自测

第六章 递推与动态规划

-6.1 兔子数列问题

--6.1.1 问题描述

--6.1.2 按大小兔子分别递推

--6.1.3 按总数递推

--6.1.4 不用数组递推

-6.2 分鱼问题

--6.2.1 问题描述

--6.2.2 从A到E递推

--6.2.3 从E到A递推

-6.3 橱窗的插花问题

--6.3.1 问题描述

--6.3.2 题意理解与分析

--6.3.3 用枚举思想解题

--6.3.4 采用递推的优化算法

--6.3.5.1 采用动态规划算法—优化分析

--6.3.5.2 采用动态规划算法—递推代码

--6.3.5.3 采用动态规划算法—计算过程

--6.3.5.4 采用动态规划算法—输出方案

--6.3.6 动态规划总结

-6.4 最长公共子序列问题

--6.4.1 问题描述与理解

--6.4.2 问题分析

--6.4.3.1 动态规划解题(1)

--6.4.3.2 动态规划解题(2)

--6.4.3.3 动态规划代码

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第六章 递推与动态规划--语法自测

第七章 文本数据处理

-7.1 统计记录总数

--7.1.1 问题分析

--7.1.2 读文件操作

-7.2 统计活跃用户数

--7.2.1 问题分析

--7.2.2 字符串

--7.2.3 程序翻译与演示

-7.3 统计在线时长

--7.3.1 问题分析

--7.3.2 结构

--7.3.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

--7.4.1 总结

-程设论道

--程设论道

-师生问答

--师生问答

-第七章 文本数据处理--语法自测

第八章 非文本数据处理

-8.1 将数据组织成链表

--8.1.1 链表的基本概念

--8.1.2 代码讲解

--8.1.3 链表遍历与释放

-8.2 提高链表访问效率 —— 哈希链表

--8.2.1 简单的哈希算法

--8.2.2 算法实现

-8.3 以二进制文件存储链表

--8.3.1 二进制文件的操作方法

--8.3.2 代码讲解

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第八章 非文本数据处理--语法自测

第九章 可配置的程序设计

-9.1 自动售卖程序

--9.1.1 提出问题与初步设计

--9.1.2 细化实现订单处理

--9.1.3 使程序更健壮

-9.2 配制水果信息

--9.2.1 提出问题与设计文件格式

--9.2.2 实现订单处理功能

-9.3 指定界面语言

--9.3.1 提出问题与命令行参数

--9.3.2 实现程序功能

-程设论道

--程设论道

-师生问答

--师生问答

-第九章 可配置的程序设计--语法自测

5.2.5 快速排序——代码解说笔记与讨论

也许你还感兴趣的课程:


  1. 宏观经济学(2021秋)

  2. 环境工程微生物学(2021秋)

  3. 走进性科学(2021秋)

  4. 太空生存(2021秋)

  5. 山水写生(2021秋)

  6. 生活中的生物学(2021秋)

  7. 计算机通信网络(2021秋)

  8. 中医内科学(2021秋)

  9. 知识产权法案例教学(2021秋)

  10. 计算机文化基础(2021秋)

  11. 程序设计基础(2021秋)

  12. 自我认知与情绪管理(2021秋)

  13. 大唐兴衰(2021秋)

  14. 生活、艺术与时尚：中国服饰七千年(2021秋)

  15. 中国房地产发展之路(2021秋)

  16. 计算机文化基础(2021秋)

  17. 宝玉石鉴赏(2021秋)

  18. 现代礼仪(2021秋)

  19. 中国古代礼义文明——礼学经典(2021秋)

  20. 住宅精细化设计(2021秋)
© 柠檬大学-慕课导航 课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。