排序算法(七):快速排序

快速排序是通过分治的方式,根据选定元素将待排序集合拆分为两个值域的子集合,并对子集合递归拆分,当拆分后的每个子集合中元素个数为一时,自然就是有序状态。

归并排序也是基于分治的思想,不过归并流程是将子集合合并成为有序的集合,递归执行来完成整个集合的排序。快速排序的分治流程是根据选定元素,将集合分隔为两个子集合,一个子集合中所有元素不大于选定元素值,另一个子集合中所有元素不小于选定元素值,则用于拆分集合的选定元素即为已排序元素。即每次拆分都会形成一个已排序元素,所以

个元素的序列,拆分的次数级别为

。将拆分过程类比为二叉树形式,考虑普通二叉树和斜树的情况,则二叉树高度级别为

~

算法过程

  1. 在所有集合中均选定某一个元素;
  2. 根据选定元素,将每个集合拆分为元素值不大于该元素值的子集合,和元素值不小于该元素值的子集合;
  3. 重复步骤 1,2,直到每个集合中元素个数为 1。

演示示例

假设每个集合中的选定元素

为集合中的最后一个元素。

拆分过程

拆分过程也就是将集合中元素值不大于

的元素,和元素值不小于

的元素,通过交换元素位置的方式分别移动到

元素的两侧,这里不妨称之为正确区域。由此可知,在拆分过程中,若已将集合中所有小于

值的元素移动到正确区域中,则拆分过程完成。

如下示例中

元素值不小于

元素值小于

在集合由左向右的遍历过程中,若当前元素值小于

值时,则将当前元素替换到正确区域中。所以在拆分过程中需要维持两个变量

,分别指向当前遍历的元素位置,和正确区域尾部的下一个元素位置,或者称之为带加入正确区域的元素位置。

首次访问:

,皆指向

此时正确区域为空,所以正确区域尾部的下一个元素位置也就是起始元素位置

因为

值小于

,所以替换

指向的元素值(其实不用替换,就是同一个元素),移动

各自指向下一个元素位置。

第 2 次访问:

,皆指向

此时正确区域元素为:[

],所以正确区域尾部的下一个元素就是

元素值不小于

,所以

指向下一个元素,

指向不变

第 3 次访问:

,指向

,指向

此时正确区域元素为:[

],所以正确区域尾部的下一个元素就是

元素值不小于

,所以

指向下一个元素,

指向不变

第 4 次访问:

,指向

,指向

此时正确区域元素为:[

],所以正确区域尾部的下一个元素就是

元素值小于

,所以替换

指向的元素值,移动

各自指向下一个元素位置。

第 5 次访问:

,指向

,指向

此时正确区域元素为:

,所以正确区域尾部的下一个元素就是

元素值小于

,所以替换

指向的元素值,移动

各自指向下一个元素位置。

第 6 次访问:

,指向

,指向

此时正确区域元素为:

,所以正确区域尾部的下一个元素就是

因为访问到了集合尾部的选定元素,此时替换

指向的元素值,完成拆分过程。

此时可以发现,选定元素的左右两侧皆为正确区域,即左侧元素值都不大于

值,右侧元素值都不小于

值。所以下一轮进行拆分的则为

构成的集合和

构成的集合。

拆分过程存在一种现象,例如当前情况下是取集合的最后一个元素为选定元素进行拆分,若初始序列为有序状态,则每一次拆分后的两个集合,一个集合元素个数为

,另一个集合为空,递归进行拆解时情况同样如此,也就是走势宛如斜树一般。

算法示例

def sort(arr, left, right):
    if left < right:
        divide = quickSort(arr, left, right)   # the divide operation
        sort(arr, left, divide - 1)   # recursive sorting
        sort(arr, divide + 1, right)

def quickSort(arr, left, right):
    lessIndex, partitionValue = left, arr[right]
    for i in range(left, right):  #Traversing
        if arr[i] < partitionValue:
            arr[i], arr[lessIndex] = arr[lessIndex], arr[i]
            lessIndex = lessIndex + 1
    arr[lessIndex], arr[right] = partitionValue, arr[lessIndex]
    return lessIndex

quickSort 操作中的循环用于遍历集合中元素,每一次遍历结束,可以形成两个正确区域,即不大于选定元素值的元素区域,和不小于选定元素值得元素区域。因为是直接根据位置进行替换,所以相比较于两两相邻元素比较替换效率要高许多,当然也导致了算法的不稳定性。

算法分析

快速排序是一种非稳定排序算法,形式上类似于归并排序,操作上刚好相反,一个是对集合先拆分后操作,一个是对集合先操作后拆分。对于

个元素的初始集合,因为在每个子集合的拆分过程中,都需要对集合进行遍历比较,所以若对

个元素的集合进行拆分,则比较次数级别为

,平均交换次数为

,即交换次数级别为

。因为拆分集合的过程存在普通二叉树和斜树的情况,所以树高为

~

,每一层的平均比较和交换复杂度为

,所以累加可得快速排序的比较和交换复杂度为

~

。排序过程属于原地排序,不需要额外的存储空间,所以空间复杂度为

~

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

python的函数(一):基本概念

我们之前学了一些基础的过程语句,如if else、while、for。随着我们python程序的功能越来越复杂,代码也就越来越长,因此我们就需要用“函数”来简化...

1958
来自专栏ACM算法日常

leetcode 41| 缺失的第一个正数

难点分析:是不是和笔者一样,刚看完一遍题目都不知道它在问什么~经过多次揣摩之后,笔者终于懂了这道题目到底在问什么。其实它就是给定一个数组,然后看看数组中是否包含...

1912
来自专栏CDA数据分析师

一文读懂如何用 Python 实现6种排序算法

总结了一下常见集中排序的算法 ? 归并排序 归并排序也称合并排序,是分治法的典型应用。分治思想是将每个问题分解成个个小问题,将每个小问题解决,然后合并。 具体...

2179
来自专栏Danny的专栏

【J2SE快速进阶】——数组(及其内存分析 )

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

1214
来自专栏zingpLiu

Go语言的数组

在 Go 语言里,数组是一个长度固定的数据类型,用于存储一段具有相同的类型的元素的连续块。数组存储的类型可以是内置类型,如整型或者字符串,也可以是某种结构类型。

1254
来自专栏流媒体

C++多态

当类存在虚函数时,编译器会为该类维护一个表,这个表就是虚函数表(vtbl),里面存放了该类虚函数的函数指针。在构造类的时候增加一个虚表指针(vptr)指向对应的...

1163
来自专栏塔奇克马敲代码

第 14 章 重载运算与类型转换

2486
来自专栏函数式编程语言及工具

泛函编程(9)-异常处理-Option

     Option是一种新的数据类型。形象的来描述:Option就是一种特殊的List,都是把数据放在一个管子里;然后在管子内部对数据进行各种操作。所以Op...

1936
来自专栏CDA数据分析师

一文读懂如何用 Python 实现6种排序算法

总结了一下常见集中排序的算法 ? 归并排序 归并排序也称合并排序,是分治法的典型应用。分治思想是将每个问题分解成个个小问题,将每个小问题解决,然后合并。 具体的...

22110
来自专栏用户2442861的专栏

java中的内部类总结

http://www.cnblogs.com/nerxious/archive/2013/01/24/2875649.html

913

扫码关注云+社区

领取腾讯云代金券