乐趣区

关于前端:Python-实现十大经典排序算法-artipub

jiezi
  • 参考资料：https://www.bilibili.com/video/BV1mp4y1D7UP
  • 本文动图演示起源：https://visualgo.net/

<font color=#FF0000> 排序算法分类 </font>

  • <font color=#FF0000>外部排序 </font>：指在排序期间，元素全副寄存在内存中的排序，常见的外部排序算法有： 冒泡排序、抉择排序、插入排序、希尔排序、归并排序、疾速排序、堆排序、基数排序 等。
  • <font color=#FF0000>内部排序</font>：指在排序期间，元素无奈齐全全副同时寄存在内存中，必须在排序的过程中依据要求一直地在内、外存之间挪动的排序；
  • <font color=#FF0000>比拟类排序</font>：通过比拟来决定元素间的绝对秩序，因为其工夫复杂度不能冲破 O(nlogn)，因而也称为非线性工夫比拟类排序。
  • <font color=#FF0000>非比拟类排序 </font>：不通过比拟来决定元素间的绝对秩序，它能够冲破基于比拟排序的工夫下界，以线性工夫运行，因而也称为线性工夫非比拟类排序。常见的非比拟类排序算法有： 基数排序、计数排序、桶排序 等

个别状况下，外部排序算法在执行过程中都要进行两种操作：比拟和挪动。通过比拟两个关键字的大小，确定对应元素的前后关系，而后通过挪动元素以达到有序。然而，并非所有的外部排序算法都要基于比拟操作。

每种排序算法都有各自的优缺点，适宜在不同的环境下应用，就其全面性能而言，很难提出一种被认为是最好的算法。<font color=#FF0000>通常能够将排序算法分为插入排序、替换排序、抉择排序、归并排序和基数排序五大类</font>，外部排序算法的性能取决于算法的工夫复杂度和空间复杂度，而工夫复杂度个别是由比拟和挪动的次数决定的。

排序算法 工夫复杂度（均匀） 工夫复杂度（最好） 工夫复杂度（最坏） 空间复杂度 稳定性
冒泡排序 $$ O(n^2) $$ $$ O(n) $$ $$ O(n^2) $$ $$ O(1) $$ 稳固
抉择排序 $$ O(n^2) $$ $$ O(n^2) $$ $$ O(n^2) $$ $$ O(1) $$ 不稳固
插入排序 $$ O(n^2) $$ $$ O(n) $$ $$ O(n^2) $$ $$ O(1) $$ 稳固
希尔排序 $$ O(nlogn) $$ $$ O(nlog^2n) $$ $$ O(nlog^2n) $$ $$ O(1) $$ 不稳固
归并排序 $$ O(nlogn) $$ $$ O(nlogn) $$ $$ O(nlogn) $$ $$ O(n) $$ 稳固
疾速排序 $$ O(nlogn) $$ $$ O(nlogn) $$ $$ O(n^2) $$ $$ O(logn) $$ 不稳固
堆排序 $$ O(nlogn) $$ $$ O(nlogn) $$ $$ O(nlogn) $$ $$ O(1) $$ 不稳固
计数排序 $$ O(n+k) $$ $$ O(n+k) $$ $$ O(n+k) $$ $$ O(k) $$ 稳固
桶排序 $$ O(n+k) $$ $$ O(n+k) $$ $$ O(n^2) $$ $$ O(n+k) $$ 稳固
基数排序 $$ O(n*k) $$ $$ O(n*k) $$ $$ O(n*k) $$ $$ O(n+k) $$ 稳固

稳定性：排序后 2 个相等键值的程序和排序之前它们的程序是否雷同。例：如果 a 本来在 b 后面，且 a=b，排序之后 a 依然在 b 的后面，则示意具备稳定性。

常见工夫复杂度大小比拟：

$$
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) <…< O(2^n)<O (n!)
$$

<font color=#FF0000> 一、冒泡排序（Bubble Sort）</font>

1、原理

反复地走访要排序的元素，顺次比拟两个相邻的元素，如果程序（如从大到小）谬误就把他们替换过去。走访元素的工作是反复地进行，直到没有相邻元素须要替换，也就是说该元素列曾经排序实现。冒泡的意思其实就是每一轮冒泡一个最大的元素就会通过一直比拟和替换相邻元素使它转移到最左边。

如果有 10 个小盆友从左到右站成一排，个头不等。老师想让他们依照个头从低到高站好，于是他开始喊口号。每喊一次，从第一个小盆友开始，相邻的小朋友如果身高不是正序就会两两调换，就这样第一轮个头最高的排到了最左边（冒泡到最左边），第二轮顺次这么来，从第一个小朋友开始两两替换，这样次高的小盆友又排到了倒数第二个地位。顺次类推。

2、步骤

  • ① 比拟相邻的元素。如果第一个比第二个大，就替换它们两个；
  • ② 对每一对相邻元素作同样的工作，从开始第一对到结尾的最初一对，这样在最初的元素应该会是最大的数；
  • ③ 针对所有的元素反复步骤 ① ~ ②，除了最初一个元素，直到排序实现。

3、动画演示

4、代码实现

def bubbleSort(arr):
    for i in range(len(arr)-1):         # 循环第 i 趟
        for j in range(len(arr)-i-1):   # j 为下标
            if arr[j] > arr[j+1]:       # 如果这个数大于前面的数就替换两者的地位
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

冒泡排序还有一种优化算法，就是立一个 flag，当某一趟序列遍历中元素没有产生替换，则证实该序列曾经有序，就不再进行后续的排序。动画演示里就是改良后的算法，改良后的代码如下：

def bubbleSort(arr):
    for i in range(len(arr)-1):         # 循环第 i 趟
    flag = False
        for j in range(len(arr)-i-1):   # j 为下标
            if arr[j] > arr[j+1]:       # 如果这个数大于前面的数就替换两者的地位
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = True
        if not flag:
            return
    return arr

冒泡排序最快的状况：当输出的数据是正序时；最慢的状况：当输出的数据是反序时。

5、具体示例

未改良版本：

def bubble_sort(arr):
    for i in range(len(arr)-1):         # 循环第 i 趟
        for j in range(len(arr)-i-1):   # j 为下标
            if arr[j] > arr[j+1]:       # 如果这个数大于前面的数就替换两者的地位
                arr[j], arr[j+1] = arr[j+1], arr[j]
        print(arr)                      # 每一趟比拟完了就打印一次


arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
bubble_sort(arr)
[3, 38, 5, 44, 15, 36, 26, 27, 2, 46, 4, 19, 47, 48, 50]
[3, 5, 38, 15, 36, 26, 27, 2, 44, 4, 19, 46, 47, 48, 50]
[3, 5, 15, 36, 26, 27, 2, 38, 4, 19, 44, 46, 47, 48, 50]
[3, 5, 15, 26, 27, 2, 36, 4, 19, 38, 44, 46, 47, 48, 50]
[3, 5, 15, 26, 2, 27, 4, 19, 36, 38, 44, 46, 47, 48, 50]
[3, 5, 15, 2, 26, 4, 19, 27, 36, 38, 44, 46, 47, 48, 50]
[3, 5, 2, 15, 4, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[3, 2, 5, 4, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

改良版本：

def bubble_sort(arr):
    for i in range(len(arr)-1):         # 循环第 i 趟
        flag = False
        for j in range(len(arr)-i-1):   # j 为下标
            if arr[j] > arr[j+1]:       # 如果这个数大于前面的数就替换两者的地位
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = True
        if not flag:
            return
        print(arr)                      # 每一趟比拟完了就打印一次


arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
bubble_sort(arr)
[3, 38, 5, 44, 15, 36, 26, 27, 2, 46, 4, 19, 47, 48, 50]
[3, 5, 38, 15, 36, 26, 27, 2, 44, 4, 19, 46, 47, 48, 50]
[3, 5, 15, 36, 26, 27, 2, 38, 4, 19, 44, 46, 47, 48, 50]
[3, 5, 15, 26, 27, 2, 36, 4, 19, 38, 44, 46, 47, 48, 50]
[3, 5, 15, 26, 2, 27, 4, 19, 36, 38, 44, 46, 47, 48, 50]
[3, 5, 15, 2, 26, 4, 19, 27, 36, 38, 44, 46, 47, 48, 50]
[3, 5, 2, 15, 4, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[3, 2, 5, 4, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

<font color=#FF0000> 二、抉择排序（Selection Sort）</font>

1、原理

第一次从待排序的数据元素中选出最小（或最大）的一个元素，寄存在序列的起始地位，而后再从残余的未排序元素中寻找到最小（大）元素，而后放到已排序的序列的开端。以此类推，直到全副待排序的数据元素的个数为零。能够了解为 一个 0 到 n-1 的迭代，每次向后查找抉择一个最小的元素。抉择排序是不稳固的排序办法。

如果有 10 个小盆友从左到右站成一排，个头不等。老师想让他们依照个头从低到高站好，咱们从第一个开始，从头到尾找一个个头最小的小盆友，而后把它和第一个小盆友替换。而后从第二个小盆友开始采取同样的策略，这样一圈下来小盆友就是有序的了。

2、步骤

  • ① 首先在未排序序列中找到最小（大）元素，寄存到排序序列的起始地位；
  • ② 再从残余未排序元素中持续寻找最小（大）元素，而后放到已排序序列的开端；
  • ③ 反复步骤 ②，直到所有元素均排序结束。

3、动画演示

4、代码实现

Python 代码：

def selection_sort(arr):
    for i in range(len(arr)-1):          # 循环第 i 趟
        min_index = i                    # 记录最小数的下标
        for j in range(i+1, len(arr)):   # j 为下标
            if arr[j] < arr[min_index]:  # 如果这个数小于记录的最小数，则更新最小数的下标
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]  # 将 i 地位的数（已排序序列的开端的数）和最小数进行替换
    return arr

5、具体示例

def selection_sort(arr):
    for i in range(len(arr)-1):          # 循环第 i 趟
        min_index = i                    # 记录最小数的下标
        for j in range(i+1, len(arr)):   # j 为下标
            if arr[j] < arr[min_index]:  # 如果这个数小于记录的最小数，则更新最小数的下标
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]  # 将 i 地位的数（已排序序列的开端的数）和最小数进行替换
        print(arr)                       # 每一趟比拟完了就打印一次


arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
selection_sort(arr)
[2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48]
[2, 3, 38, 5, 47, 15, 36, 26, 27, 44, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 15, 47, 36, 26, 27, 44, 46, 38, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 36, 26, 27, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 36, 27, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 46, 44, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

<font color=#FF0000> 三、插入排序（Insertion Sort）</font>

1、原理

插入排序个别也被称为间接插入排序。对于大量元素的排序，它是一个无效的算法。它的根本思维是将一个记录插入到曾经排好序的有序表中，从而造成一个新的有序表。在其实现过程应用双层循环，外层循环对除了第一个元素之外的所有元素进行遍历，内层循环对以后元素后面有序表进行待插入地位查找，并进行挪动。

插入排序的工作形式像许多人排序一手扑克牌。开始时，咱们的左手为空并且桌子上的牌面向下。而后，咱们每次从桌子上拿走一张牌并将它插入左手中正确的地位。为了找到一张牌的正确地位，咱们从右到左将它与已在手中的每张牌进行比拟。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

2、步骤

  • ① 从第一个元素开始，该元素能够认为曾经被排序；
  • ② 取出下一个元素，在曾经排序的元素序列中从后向前扫描；
  • ③ 如果该元素（已排序的）大于新元素，将该元素往右移到下一地位，反复该步骤，直到找到已排序的元素小于或者等于新元素的地位；
  • ④ 将新元素插入到步骤 ③ 找到的地位的前面；
  • ⑤ 反复步骤 ② ~ ④。

3、动画演示

4、代码实现

def insertion_sort(arr):
    for i in range(1, len(arr)):    # 将 i 看做摸到的牌的下标
        tmp = arr[i]                # 将摸到的牌贮存到 tmp
        j = i-1                     # 将 j 看做手里的牌的下标
        while j >= 0 and arr[j] > tmp:  # 如果手里的牌大于摸到的牌
            arr[j+1] = arr[j]       # 将手里的牌往右移一个地位（将手里的牌赋值给下一个地位）j -= 1                  # 将手里的牌的下标减 1，再次筹备与摸到的牌进行比拟
        arr[j+1] = tmp              # 将摸到的牌插入到 j+1 地位
    return arr

5、具体示例

def insertion_sort(arr):
    for i in range(1, len(arr)):    # 将 i 看做摸到的牌的下标
        tmp = arr[i]                # 将摸到的牌贮存到 tmp
        j = i-1                     # 将 j 看做手里的牌的下标
        while j >= 0 and arr[j] > tmp:  # 如果手里的牌大于摸到的牌
            arr[j+1] = arr[j]       # 将手里的牌往右移一个地位（将手里的牌赋值给下一个地位）j -= 1                  # 将手里的牌的下标减 1，再次筹备与摸到的牌进行比拟
        arr[j+1] = tmp              # 将摸到的牌插入到 j+1 地位
        print(arr)                  # 每一趟比拟完了就打印一次


arr = [0, 9, 8, 7, 1, 2, 3, 4, 5, 6]
insertion_sort(arr)
[0, 9, 8, 7, 1, 2, 3, 4, 5, 6]  # 手里第一张牌为 0，摸到 9，此时 i=1，j=0，0 比 9 小，将 9 插到索引 j+1=1 处。[0, 8, 9, 7, 1, 2, 3, 4, 5, 6]  # 手里的牌为 0，9，摸到 8，此时 i=2，j=1，9 比 8 大，将 9 右移一个地位，j-1=0，将 8 插到 j+1=1 处
[0, 7, 8, 9, 1, 2, 3, 4, 5, 6]
[0, 1, 7, 8, 9, 2, 3, 4, 5, 6]
[0, 1, 2, 7, 8, 9, 3, 4, 5, 6]
[0, 1, 2, 3, 7, 8, 9, 4, 5, 6]
[0, 1, 2, 3, 4, 7, 8, 9, 5, 6]
[0, 1, 2, 3, 4, 5, 7, 8, 9, 6]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

<font color=#FF0000> 四、希尔排序（Shell Sort）</font>

1、原理

希尔排序是插入排序的一种更高效的改良版本，是一种分组插入排序算法，又称放大增量排序（Diminishing Increment Sort），希尔排序是非稳固排序算法。该办法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是基于插入排序的以下两点性质而提出改良办法的：

  • 插入排序在对简直曾经排好序的数据操作时，效率高，即能够达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据挪动一位；

希尔排序的根本思维是：先将整个待排序的记录序列宰割成为若干子序列别离进行间接插入排序，待整个序列中的记录“根本有序”时，再对整体记录进行顺次间接插入排序。

2、步骤

  • ① n 为数组长度，首先取一个整数 d1=n/2，将元素分为 d1 个组，每组相邻量元素之间间隔为 d1-1，在各组内进行间接插入排序；
  • ② 取第二个整数 d2=d1/2，反复步骤 ① 分组排序过程，直到 di=1，即所有元素在同一组内进行间接插入排序。

PS：希尔排序每趟并不使某些元素有序，而是使整体数据越来越靠近有序；最初一趟排序使得所有数据有序。

3、动画演示

4、代码实现

def insertion_sort_gap(arr, gap):     # 将 gap 看做隔 gap 个间隔摸一张牌，而不是顺次依照程序摸牌
    for i in range(gap, len(arr)):    # 将 i 看做摸到的牌的下标
        tmp = arr[i]                  # 将摸到的牌贮存到 tmp
        j = i-gap                     # 将 j 看做手里的牌的下标
        while j >= 0 and arr[j] > tmp:  # 如果手里的牌大于摸到的牌
            arr[j+gap] = arr[j]         # 将手里的牌往右移一个地位（将手里的牌赋值给下一个地位）j -= gap                    # 将手里的牌的下标减 gap，再次筹备与摸到的牌进行比拟
        arr[j+gap] = tmp                # 将摸到的牌插入到 j+gap 地位


def shell_sort(arr):
    d = len(arr) // 2                   # 第一次分组
    while d >= 1:
        insertion_sort_gap(arr, d)      # 调用插入排序
        d //= 2                         # 整除 2 后再次分组
    return arr

也能够不应用两个函数，写在一起即可：

def shell_sort(arr):
    d = len(arr) // 2                   # 第一次分组
    while d >= 1:                       # 将 d 看做隔 d 个间隔摸一张牌，而不是顺次依照程序摸牌
        for i in range(d, len(arr)):    # 将 i 看做摸到的牌的下标
            tmp = arr[i]                # 将摸到的牌贮存到 tmp
            j = i - d                   # 将 j 看做手里的牌的下标
            while j >= 0 and arr[j] > tmp:   # 如果手里的牌大于摸到的牌
                arr[j + d] = arr[j]          # 将手里的牌往右移一个地位（将手里的牌赋值给下一个地位）j -= d                       # 将手里的牌的下标减 d，再次筹备与摸到的牌进行比拟
            arr[j + d] = tmp                 # 将摸到的牌插入到 j+d 地位
        d //= 2                              # 整除 2 后再次分组
    return arr

5、具体示例

def insertion_sort_gap(arr, gap):     # 将 gap 看做隔 gap 个间隔摸一张牌，而不是顺次依照程序摸牌
    for i in range(gap, len(arr)):    # 将 i 看做摸到的牌的下标
        tmp = arr[i]                  # 将摸到的牌贮存到 tmp
        j = i-gap                     # 将 j 看做手里的牌的下标
        while j >= 0 and arr[j] > tmp:  # 如果手里的牌大于摸到的牌
            arr[j+gap] = arr[j]         # 将手里的牌往右移一个地位（将手里的牌赋值给下一个地位）j -= gap                    # 将手里的牌的下标减 gap，再次筹备与摸到的牌进行比拟
        arr[j+gap] = tmp                # 将摸到的牌插入到 j+gap 地位


def shell_sort(arr):
    d = len(arr) // 2                   # 第一次分组
    while d >= 1:
        insertion_sort_gap(arr, d)      # 调用插入排序
        print(arr)                      # 每一轮排序后打印一次
        d //= 2                         # 整除 2 后再次分组


arr = [5, 7, 4, 6, 3, 1, 2, 9, 8]
shell_sort(arr)
[3, 1, 2, 6, 5, 7, 4, 9, 8]
[2, 1, 3, 6, 4, 7, 5, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
def shell_sort(arr):
    d = len(arr) // 2                   # 第一次分组
    while d >= 1:                       # 将 d 看做隔 d 个间隔摸一张牌，而不是顺次依照程序摸牌
        for i in range(d, len(arr)):    # 将 i 看做摸到的牌的下标
            tmp = arr[i]                # 将摸到的牌贮存到 tmp
            j = i - d                   # 将 j 看做手里的牌的下标
            while j >= 0 and arr[j] > tmp:   # 如果手里的牌大于摸到的牌
                arr[j + d] = arr[j]          # 将手里的牌往右移一个地位（将手里的牌赋值给下一个地位）j -= d                       # 将手里的牌的下标减 d，再次筹备与摸到的牌进行比拟
            arr[j + d] = tmp                 # 将摸到的牌插入到 j+d 地位
        print(arr)                           # 每一轮排序后打印一次
        d //= 2                              # 整除 2 后再次分组


arr = [5, 7, 4, 6, 3, 1, 2, 9, 8]
shell_sort(arr)
[3, 1, 2, 6, 5, 7, 4, 9, 8]
[2, 1, 3, 6, 4, 7, 5, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

<font color=#FF0000> 五、归并排序（Merge Sort）</font>

1、原理

归并的概念：假如一个列表分为两段，其中每一段都是有序列表，当初将该两段合并为一个有序列表，这种操作称为一次归并。

归并排序是建设在归并操作上的一种无效，稳固的排序算法，该算法是采纳分治法（Divide and Conquer）的一个十分典型的利用。将已有序的子序列合并，失去齐全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2、步骤

<font color=#ff0000>归并的根本步骤：</font>

  • ① 申请空间，使其大小为 两个曾经排序序列之和，该空间用来寄存合并后的序列；
  • ② 设定两个指针，最后地位别离为两个曾经排序序列的起始地位；
  • ③ 比拟两个指针所指向的元素，抉择绝对小的元素放入到合并空间，并挪动指针到下一地位；
  • ④ 反复步骤 ③ 直到某一指针达到序列尾；
  • ⑤ 将另一序列剩下的所有元素间接复制到合并序列尾。

<font color=#ff0000>归并排序的步骤：</font>

  • ① 合成：将列表越分越小，直至分成一个元素，终止条件：一个元素是有序的。
  • ② 合并：一直将两个有序列表进行归并，列表越来越大，直到所有序列归并结束。

3、动画演示

4、代码实现

def merge(arr, low, mid, high):
    # low 和 high 为整个数组的第一个和最初一个地位索引，mid 为两头地位索引
    # i 和 j 为指针，最后地位别离为两个有序序列的起始地位
    # ltmp 用来寄存合并后的序列
    i = low
    j = mid+1
    ltmp = []
    while i <= mid and j <= high:  # 只有左右两边都无数
        if arr[i] < arr[j]:        # 当右边的数小于左边的数
            ltmp.append(arr[i])    # 将右边的数存入 ltmp
            i += 1                 # 右边的指针往右移一位
        else:                      # 当左边的数小于右边的数
            ltmp.append(arr[j])    # 将左边的数存入 ltmp
            j += 1                 # 左边的指针往右移一位
    # 下面的 while 语句执行完后，右边或者左边没有数了
    while i <= mid:                # 当右边还有数的时候
        ltmp.append(arr[i])        # 将右边剩下的数全副存入 ltmp
        i += 1
    while j <= high:               # 当左边还有数的时候
        ltmp.append(arr[j])        # 将左边剩下的数全副存入 ltmp
        j += 1
    arr[low:high+1] = ltmp         # 将排序后的数组写回原数组


def merge_sort(arr, low, high):       # low 和 high 为整个数组的第一个和最初一个地位索引
    if low < high:                    # 至多有两个元素
        mid = (low + high) // 2
        merge_sort(arr, low, mid)     # 把右边递归合成
        merge_sort(arr, mid+1, high)  # 把左边递归合成
        merge(arr, low, mid, high)    # 做归并

5、具体示例

def merge(arr, low, mid, high):
    # low 和 high 为整个数组的第一个和最初一个地位索引，mid 为两头地位索引
    # i 和 j 为指针，最后地位别离为两个有序序列的起始地位
    # ltmp 用来寄存合并后的序列
    i = low
    j = mid+1
    ltmp = []
    while i <= mid and j <= high:  # 只有左右两边都无数
        if arr[i] < arr[j]:        # 当右边的数小于左边的数
            ltmp.append(arr[i])    # 将右边的数存入 ltmp
            i += 1                 # 右边的指针往右移一位
        else:                      # 当左边的数小于右边的数
            ltmp.append(arr[j])    # 将左边的数存入 ltmp
            j += 1                 # 左边的指针往右移一位
    # 下面的 while 语句执行完后，右边或者左边没有数了
    while i <= mid:                # 当右边还有数的时候
        ltmp.append(arr[i])        # 将右边剩下的数全副存入 ltmp
        i += 1
    while j <= high:               # 当左边还有数的时候
        ltmp.append(arr[j])        # 将左边剩下的数全副存入 ltmp
        j += 1
    arr[low:high+1] = ltmp         # 将排序后的数组写回原数组


def merge_sort(arr, low, high):       # low 和 high 为整个数组的第一个和最初一个地位索引
    if low < high:                    # 至多有两个元素
        mid = (low + high) // 2
        merge_sort(arr, low, mid)     # 把右边递归合成
        merge_sort(arr, mid+1, high)  # 把左边递归合成
        merge(arr, low, mid, high)    # 做归并
        print(arr)                    # 每一次归并打印一次


arr = [7, 1, 3, 2, 6, 9, 4]
merge_sort(arr, 0, len(arr)-1)
[1, 7, 3, 2, 6, 9, 4]
[1, 7, 2, 3, 6, 9, 4]
[1, 2, 3, 7, 6, 9, 4]
[1, 2, 3, 7, 6, 9, 4]
[1, 2, 3, 7, 4, 6, 9]
[1, 2, 3, 4, 6, 7, 9]
这里是一段防爬虫文本，请读者疏忽。本文原创首发于 CSDN，作者 TRHX•鲍勃。博客首页：https://itrhx.blog.csdn.net/
本文链接：https://itrhx.blog.csdn.net/article/details/109251836
未经受权，禁止转载！歹意转载，后果自负！尊重原创，远离抄袭！

<font color=#FF0000> 六、疾速排序（Quick Sort）</font>

1、原理

疾速排序是对冒泡排序的一种改良。顾名思义疾速排序就是快，而且效率高！它是解决大数据最快的排序算法之一了。它的根本思维是：通过一趟排序将要排序的数据宰割成独立的两局部，其中一部分的所有数据都比另外一部分的所有数据都要小，而后再按此办法对这两局部数据别离进行疾速排序，整个排序过程能够递归进行，以此达到整个数据变成有序序列。

2、步骤

  • ① 从数列中挑出一个元素，称为“基准值”;
  • ② 从新排序数列，所有元素比基准值小的放在基准值的右边，比基准值大的放在基准值的左边（雷同的数能够到任一边）。在这个分区退出之后，该基准值就处于数列的两头地位。这个称为分区（partition）操作，也能够称为一次归位操作，归位操作的过程见下动图；
  • ③ 递归地把小于基准值元素的子数列和大于基准值元素的子数列依照步骤 ① ② 排序。

3、动画演示

4、代码实现

def partition(arr, left, right):
    # 归位操作，left，right 别离为数组右边和左边的地位索引
    tmp = arr[left]
    while left < right:
        while left < right and arr[right] >= tmp:  # 从左边找比 tmp 小的数，如果比 tmp 大，则挪动指针
            right -= 1                             # 将指针左移一个地位
        arr[left] = arr[right]                     # 将左边的值写到右边的空位上
        while left < right and arr[left] <= tmp:   # 从右边找比 tmp 大的数，如果比 tmp 小，则挪动指针
            left += 1                              # 将指针右移一个地位
        arr[right] = arr[left]                     # 将右边的值写到左边的空位上
    arr[left] = tmp                                # 把 tmp 归位
    return left                   # 返回 left，right 都能够，目标是便于前面的递归操作对左右两局部进行排序


def quick_sort(arr, left, right):          # 疾速排序
    if left < right:
        mid = partition(arr, left, right)
        quick_sort(arr, left, mid-1)       # 对左半局部进行归位操作
        quick_sort(arr, mid+1, right)      # 对右半局部进行归位操作
    return arr

5、具体示例

def partition(arr, left, right):
    # 归位操作，left，right 别离为数组右边和左边的地位索引
    tmp = arr[left]
    while left < right:
        while left < right and arr[right] >= tmp:  # 从左边找比 tmp 小的数，如果比 tmp 大，则挪动指针
            right -= 1                             # 将指针左移一个地位
        arr[left] = arr[right]                     # 将左边的值写到右边的空位上
        while left < right and arr[left] <= tmp:   # 从右边找比 tmp 大的数，如果比 tmp 小，则挪动指针
            left += 1                              # 将指针右移一个地位
        arr[right] = arr[left]                     # 将右边的值写到左边的空位上
    arr[left] = tmp                                # 把 tmp 归位
    return left                   # 返回 left，right 都能够，目标是便于前面的递归操作对左右两局部进行排序


def quick_sort(arr, left, right):
    if left < right:
        mid = partition(arr, left, right)
        print(arr)                         # 每次归位后打印一次
        quick_sort(arr, left, mid-1)       # 对左半局部进行归位操作
        quick_sort(arr, mid+1, right)      # 对右半局部进行归位操作


arr = [5, 7, 4, 6, 3, 1, 2, 9, 8]
quick_sort(arr, 0, len(arr)-1)
[2, 1, 4, 3, 5, 6, 7, 9, 8]
[1, 2, 4, 3, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

<font color=#FF0000> 七、堆排序（Heap Sort）</font>

1、原理

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似齐全二叉树的构造，并同时满足沉积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

  • 堆：一种非凡的齐全二叉树构造
  • 大根堆：一棵齐全二叉树，满足任一节点都比其孩子节点大
  • 小根堆：一棵齐全二叉树，满足任一节点都比其孩子节点小

2、步骤

  • ① 构建堆：将待排序序列构建成一个堆 H[0……n-1]，从最初一个非叶子结点开始，从左至右，从下至上进行调整。依据升序或降序需要抉择大顶堆或小顶堆；
  • ② 此时的堆顶元素，为最大或者最小元素；
  • ③ 把堆顶元素和堆尾元素调换，调整堆，从新使堆有序；
  • ④ 此时堆顶元素为第二大元素；
  • ⑤ 反复以上步骤，直到堆变空。

3、动画演示

堆构建实现后再进行推排序：

4、代码实现

def sift(arr, low, high):
    """
    :param li: 列表
    :param low: 堆的根节点地位
    :param high: 堆的最初一个元素的地位
    """
    i = low                 # i 最开始指向根节点
    j = 2 * i + 1           # j 开始是左孩子
    tmp = arr[low]          # 把堆顶存起来
    while j <= high:        # 只有 j 地位无数
        if j + 1 <= high and arr[j+1] > arr[j]:   # 如果右孩子有并且比拟大
            j = j + 1       # j 指向右孩子
        if arr[j] > tmp:
            arr[i] = arr[j]
            i = j           # 往下看一层
            j = 2 * i + 1
        else:               # tmp 更大，把 tmp 放到 i 的地位上
            arr[i] = tmp    # 把 tmp 放到某一级领导地位上
            break
    else:
        arr[i] = tmp        # 把 tmp 放到叶子节点上


def heap_sort(arr):
    n = len(arr)
    for i in range((n-2)//2, -1, -1):   # i 示意建堆的时候调整的局部的根的下标
        sift(arr, i, n-1)
    # 建堆实现
    for i in range(n-1, -1, -1):        # i 指向以后堆的最初一个元素
        arr[0], arr[i] = arr[i], arr[0]
        sift(arr, 0, i - 1)             # i- 1 是新的 high
    return arr

5、具体示例

def sift(arr, low, high):
    """
    :param li: 列表
    :param low: 堆的根节点地位
    :param high: 堆的最初一个元素的地位
    """
    i = low                 # i 最开始指向根节点
    j = 2 * i + 1           # j 开始是左孩子
    tmp = arr[low]          # 把堆顶存起来
    while j <= high:        # 只有 j 地位无数
        if j + 1 <= high and arr[j+1] > arr[j]:   # 如果右孩子有并且比拟大
            j = j + 1       # j 指向右孩子
        if arr[j] > tmp:
            arr[i] = arr[j]
            i = j           # 往下看一层
            j = 2 * i + 1
        else:               # tmp 更大，把 tmp 放到 i 的地位上
            arr[i] = tmp    # 把 tmp 放到某一级领导地位上
            break
    else:
        arr[i] = tmp        # 把 tmp 放到叶子节点上


def heap_sort(arr):
    n = len(arr)
    print('建堆过程：')
    print(arr)
    for i in range((n-2)//2, -1, -1):   # i 示意建堆的时候调整的局部的根的下标
        sift(arr, i, n-1)
        print(arr)
    # 建堆实现
    print('堆排序过程：')
    print(arr)
    for i in range(n-1, -1, -1):        # i 指向以后堆的最初一个元素
        arr[0], arr[i] = arr[i], arr[0]
        sift(arr, 0, i - 1)             # i- 1 是新的 high
        print(arr)


arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
heap_sort(arr)
建堆过程：[2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
[2, 7, 26, 25, 36, 17, 1, 90, 3, 19]
[2, 7, 26, 90, 36, 17, 1, 25, 3, 19]
[2, 7, 26, 90, 36, 17, 1, 25, 3, 19]
[2, 90, 26, 25, 36, 17, 1, 7, 3, 19]
[90, 36, 26, 25, 19, 17, 1, 7, 3, 2]
堆排序过程：[90, 36, 26, 25, 19, 17, 1, 7, 3, 2]
[36, 25, 26, 7, 19, 17, 1, 2, 3, 90]
[26, 25, 17, 7, 19, 3, 1, 2, 36, 90]
[25, 19, 17, 7, 2, 3, 1, 26, 36, 90]
[19, 7, 17, 1, 2, 3, 25, 26, 36, 90]
[17, 7, 3, 1, 2, 19, 25, 26, 36, 90]
[7, 2, 3, 1, 17, 19, 25, 26, 36, 90]
[3, 2, 1, 7, 17, 19, 25, 26, 36, 90]
[2, 1, 3, 7, 17, 19, 25, 26, 36, 90]
[1, 2, 3, 7, 17, 19, 25, 26, 36, 90]
[1, 2, 3, 7, 17, 19, 25, 26, 36, 90]

<font color=#FF0000> 八、计数排序（Counting Sort）</font>

1、原理

计数排序是一个非基于比拟的排序算法，它的劣势在于在对肯定范畴内的整数排序时，它的复杂度为 Ο(n+k)，其中 k 是整数的范畴，快于任何比拟排序算法。计数排序是一种就义空间换取工夫的做法。计数排序的外围在于将输出的数据值转化为键存储在额定开拓的数组空间中。作为一种线性工夫复杂度的排序，计数排序要求输出的数据必须是有确定范畴的整数。

2、步骤

  • ① 找到待排序列表中的最大值 k，开拓一个长度为 k+1 的计数列表，计数列表中的值都为 0。
  • ② 遍历待排序列表，如果遍历到的元素值为 i，则计数列表中索引 i 的值加 1。
  • ③ 遍历残缺个待排序列表，计数列表中索引 i 的值 j 示意 i 的个数为 j，统计出待排序列表中每个值的数量。
  • ④ 创立一个新列表（也能够清空原列表，在原列表中增加），遍历计数列表，顺次在新列表中增加 j 个 i，新列表就是排好序后的列表，整个过程没有比拟待排序列表中的数据大小。

3、动画演示

4、代码实现

def count_sort(arr):
    if len(arr) < 2:                       # 如果数组长度小于 2 则间接返回
        return arr
    max_num = max(arr)
    count = [0 for _ in range(max_num+1)]  # 开拓一个计数列表
    for val in arr:
        count[val] += 1
    arr.clear()                        # 原数组清空
    for ind, val in enumerate(count):  # 遍历值和下标（值的数量）for i in range(val):
            arr.append(ind)
    return arr

5、具体示例

def count_sort(arr):
    if len(arr) < 2:                       # 如果数组长度小于 2 则间接返回
        return arr
    max_num = max(arr)
    count = [0 for _ in range(max_num+1)]  # 开拓一个计数列表
    for val in arr:
        count[val] += 1
    arr.clear()                        # 原数组清空
    for ind, val in enumerate(count):  # 遍历值和下标（值的数量）for i in range(val):
            arr.append(ind)
    return arr


arr = [2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]
sorted_arr = count_sort(arr)
print(sorted_arr)
[1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]

<font color=#FF0000> 九、桶排序（Bucket Sort）</font>

1、原理

桶排序又叫箱排序，工作的原理是将数组分到无限数量的桶子里。每个桶子再个别排序（有可能再应用别的排序算法或是以递归形式持续应用桶排序进行排序）。桶排序是鸽巢排序的一种演绎后果。

桶排序也是计数排序的升级版。它利用了函数的映射关系，高效与否的要害就在于这个映射函数的确定。为了使桶排序更加高效，咱们须要做到这两点：

  • 在额定空间短缺的状况下，尽量增大桶的数量；
  • 应用的映射函数可能将输出的 N 个数据平均的调配到 K 个桶中。

同时，对于桶中元素的排序，抉择何种比拟排序算法对于性能的影响至关重要。

  • 最快状况：当输出的数据能够平均的调配到每一个桶中；
  • 最慢状况：当输出的数据被调配到了同一个桶中。

2、步骤

  • ① 创立一个定量的数组当作空桶子；
  • ② 遍历序列，把元素一个一个放到对应的桶子去；
  • ③ 对每个不是空的桶子进行排序；
  • ④ 从不是空的桶子里把元素再放回原来的序列中。

3、动画演示

（动图来源于 @五分钟学算法，侵删）

4、代码实现

def bucket_sort(arr):
    max_num = max(arr)
    n = len(arr)
    buckets = [[] for _ in range(n)]         # 创立桶
    for var in arr:
        i = min(var // (max_num // n), n-1)  # i 示意 var 放到几号桶里
        buckets[i].append(var)               # 把 var 加到桶里边
        # 放弃桶内的程序
        for j in range(len(buckets[i])-1, 0, -1):
            if buckets[i][j] < buckets[i][j-1]:
                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
            else:
                break
    sorted_arr = []
    for buc in buckets:
        sorted_arr.extend(buc)
    return sorted_arr

5、具体示例

def bucket_sort(arr):
    max_num = max(arr)
    n = len(arr)
    buckets = [[] for _ in range(n)]         # 创立桶
    for var in arr:
        i = min(var // (max_num // n), n-1)  # i 示意 var 放到几号桶里
        buckets[i].append(var)               # 把 var 加到桶里边
        # 放弃桶内的程序
        for j in range(len(buckets[i])-1, 0, -1):
            if buckets[i][j] < buckets[i][j-1]:
                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
            else:
                break
    sorted_arr = []
    for buc in buckets:
        sorted_arr.extend(buc)
    return sorted_arr


arr = [7, 12, 56, 23, 19, 33, 35, 42, 42, 2, 8, 22, 39, 26, 17]
sorted_arr = bucket_sort(arr)
print(sorted_arr)
[2, 7, 8, 12, 17, 19, 22, 23, 26, 33, 35, 39, 42, 42, 56]

<font color=#FF0000> 十、基数排序（Radix Sort）</font>

1、原理

基数排序属于调配式排序，是一种非比拟型整数排序算法，其原理是将整数按位数切割成不同的数字，而后按每个位数别离比拟。因为整数也能够表白字符串（比方名字或日期）和特定格局的浮点数，所以基数排序也不是只能应用于整数。

基数排序、计数排序、桶排序三种排序算法都利用了桶的概念，但对桶的应用办法上是有显著差别的：

  • 基数排序：依据键值的每位数字来调配桶；
  • 计数排序：每个桶只存储繁多键值；
  • 桶排序：每个桶存储肯定范畴的数值。

2、步骤

  • ① 取数组中的最大数，并获得位数；
  • ② 从最低位开始，顺次进行一次排序；
  • ③ 从最低位排序始终到最高位排序实现当前, 数列就变成一个有序序列。

3、动画演示

4、代码实现

def radix_sort(li):
    max_num = max(li)      # 最大值 9->1 次循环, 99->2 次循环, 888->3 次循环, 10000->5 次循环
    it = 0
    while 10 ** it <= max_num:
        buckets = [[] for _ in range(10)]
        for var in li:
            # var=987, it=1, 987//10->98, 98%10->8; it=2, 987//100->9, 9%10=9
            digit = (var // 10 ** it) % 10   # 顺次取一位数
            buckets[digit].append(var)
        # 分桶实现
        li.clear()
        for buc in buckets:
            li.extend(buc)
        it += 1            # 把数从新写回 li
    return arr

5、具体示例

def radix_sort(li):
    max_num = max(li)      # 最大值 9->1 次循环, 99->2 次循环, 888->3 次循环, 10000->5 次循环
    it = 0
    while 10 ** it <= max_num:
        buckets = [[] for _ in range(10)]
        for var in li:
            # var=987, it=1, 987//10->98, 98%10->8; it=2, 987//100->9, 9%10=9
            digit = (var // 10 ** it) % 10   # 顺次取一位数
            buckets[digit].append(var)
        # 分桶实现
        li.clear()
        for buc in buckets:
            li.extend(buc)
        it += 1            # 把数从新写回 li
    return arr


arr = [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127]
sorted_arr = radix_sort(arr)
print(sorted_arr)
[1, 7, 10, 82, 577, 743, 2030, 2599, 3138, 3221, 4127, 4793, 5622, 9420, 9680]
退出移动版