快速排序算法详解（原理、实现和时间复杂度）.pdf资源-CSDN文库

需积分: 1 113 浏览量 2023-12-05 22:28:21 上传评论收藏 443KB PDF 举报

资源推荐

资源详情

资源评论

快速排序算法详解（原理、实现和时间复杂度）

快速排序是对冒泡排序的一种改进，由 C.A.R.Hoare（Charles Antony Richard Hoare，东尼·霍尔）在

1962 年提出。

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另

一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，

使整个数据变成有序序列。

快速排序的原理

排序算法的思想非常简单，在待排序的数列中，我们首先要找一个数字作为基准数（这只是个专用名

词）。为了方便，我们一般选择第 1 个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要

把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序

的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法

继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。

这是典型的分治思想，即分治法。下面我们对一个实际例子进行算法描述，讲解快速排序的排序步骤。

以 47、29、71、99、78、19、24、47 的待排序的数列为例进行排序，为了方便区分两个 47，我们对后

面的 47 增加一个下画线，即待排序的数列为 47、29、71、99、78、19、24、47。

首先我们需要在数列中选择一个基准数，我们一般会选择中间的一个数或者头尾的数，这里直接选择第 1

个数 47 作为基准数，接着把比 47 小的数字移动到左边，把比 47 大的数字移动到右边，对于相等的数字

不做移动。所以实际上我们需要找到中间的某个位置 k，这样 k 左边的值全部比 k 上的值小，k 右边的值全

部比 k 上的值大。

接下来开始移动元素。怎么移动呢？其实冒泡排序也涉及对元素的移动，但是那样移动起来很累，比如把

最后一个元素移动到第 1 个，就需要比较 n-1 次，同时交换 n-1 次，效率很低。其实，只需把第 1 个元素

和最后一个元素交换就好了，这种思想是不是在排序时可以借鉴呢？之前说快速排序就是对冒泡排序的一

个改进，就是这个原因。

快速排序的操作是这样的：首先从数列的右边开始往左边找，我们设这个下标为 i，也就是进行减减操作

（i--），找到第 1 个比基准数小的值，让它与基准值交换；接着从左边开始往右边找，设这个下标为 j，然

后执行加加操作（j++），找到第 1 个比基准数大的值，让它与基准值交换；然后继续寻找，直到 i 与 j 相

遇时结束，最后基准值所在的位置即 k 的位置，也就是说 k 左边的值均比 k 上的值小，而 k 右边的值都比

k 上的值大。

所以对于上面的数列 47、29、71、99、78、19、24、47，进行第 1 趟第 1 个交换的排序情况如下，第 1

次的操作情况如图 1 所示。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余5页未读，立即下载

内容反馈

hakesashou

粉丝: 4192
资源: 1083

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip