python算法-快速排序

介绍

快速排序( quicksort)是一种经典的排序算法,具有较高的效率和普遍的应用。快速排序的总体思路也是把一个较大的序列,不断细分为较小序列,并递归地调用快速排序对每一小段分别排序。(类似于一分二,二分四,和多线程差不多)

实现代码

def quicksort(arr):
    if len(arr) <= 1:  # 比较每次序列长度是否大于等于1
        return arr
    else:
        pivot = arr[0]  # 设置一个比较基准点
        left = []  # 比较列表_左
        right = []  # 比较列表_右
        for i in range(1, len(arr)):  # 遍历
            if arr[i] < pivot:  # 比较-比基准点小的元素放入列表 left
                left.append(arr[i])
            else:  # 比基准点大的元素放入列表 right
                right.append(arr[i])
        return quicksort(left) + [pivot] + quicksort(right)  # 将left和right两个列表分别递归调用quicksort函数进行排序,并将排序后的列表和基准点组合成一个新的列表

原理

变量 arr 表示待排序的序列,如果序列长度小于等于1,则直接返回该序列;否则,我们选取序列的第一个元素作为比较基准点 pivot,将剩余元素分别放入左右两个列表 leftright 中,左边的元素都小于等于基准点,右边的元素都大于基准点。然后,我们递归地对左右两个子序列进行排序,并将排序后的列表和基准点组合成一个新的列表返回。在递归调用过程中,左右子序列也会不断地划分成更小的子序列,直到每个子序列只包含一个元素为止,这样整个序列就变成了有序的。

important

最后,我们来解释一下上面代码中最重要的一行:

return quicksort(left) + [pivot] + quicksort(right)

该行代码表示将 leftright 两个列表分别递归调用 quicksort 函数进行排序,并将排序后的列表和基准点 pivot 组合成一个新的列表。具体来说,quicksort(left)quicksort(right) 会递归地对 leftright 两个列表进行排序,返回排序后的列表。而 + 运算符则表示将两个列表按顺序合并成一个新的列表,其中 left是基准点左侧的,pivot 表示比较基准点,right是基准点右侧的,把它仨合起来就行了。

应用

将上述代码应用到一个例子中,以更好地理解快速排序算法的具体实现。假设我们要排序的序列为 [4, 6, 1, 3, 8, 2, 9, 7, 5],则按照上面的代码进行快速排序的过程如下所示:

  1. 选取序列的第一个元素 4 作为比较基准点 pivot
  2. 遍历序列,将小于 4 的元素 [1, 3, 2] 放入左边的列表 left 中,将大于 4 的元素 [6, 8, 9, 7, 5] 放入右边的列表 right 中。
  3. 递归调用 quicksort(left)quicksort(right),对左右两个子序列进行排序。由于 left 中只有三个元素,递归调用 quicksort(left) 后直接返回 [1, 2, 3];而 right 中有五个元素,递归调用 quicksort(right) 后返回 [5, 6, 7, 8, 9]
  4. 将排序后的列表 [1, 2, 3]、比较基准点 4 和排序后的列表 [5, 6, 7, 8, 9] 按顺序合并成一个新的列表 [1, 2, 3, 4, 5, 6, 7, 8, 9],返回结果。

over

完结撒花~此篇也算承接了很久前发过的那篇选择排序的文章(一般情况选择效率低,快排效率高)(冒泡:你再喊我?)。当然,这里排序算法就基本完结了。

所以,为啥不用.sort()排序呢?

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯
 ̄﹃ ̄
(/ω\)
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
(´っω・`。)
( ,,´・ω・)ノ)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•)
(ㆆᴗㆆ)
整活by Mimosa233
Source: github.com/k4yt3x/flowerhd
galgame系列表情by Mimosa233
颜文字
小恐龙
夸夸我!
花!
可愛い!
上一篇
下一篇