算法通过手册：05 数组十大经典排序算法

2021-12-20 本文已影响0人 ITCharge

05 数组十大经典排序算法.png

本文首发于：「算法通关手册」

文中代码地址（欢迎 「Star ★ 」 和 「Fork」）：https://github.com/itcharge/LeetCode-Py

1. 冒泡排序算法

1.1 算法思想

冒泡排序（Bubble Sort） 基本思想：

第 i (i = 1, 2, …) 趟排序时从序列中前 n - i + 1 个元素的第 1 个元素开始，相邻两个元素进行比较，若前者大于后者，两者交换位置，否则不交换。

1.2 算法步骤

先将序列中第 1 个元素与第 2 个元素进行比较，若前者大于后者，则两者交换位置，否则不交换；
然后将第 2 个元素与第 3 个元素比较，若前者大于后者，则两者交换位置，否则不交换；
依次类推，直到第 n - 1 个元素与第 n 个元素比较（或交换）为止。经过如此一趟排序，使得 n 个元素中值最大元素被安置在序列的第 n 个位置上。
此后，再对前 n - 1 个元素进行同样过程，使得该 n - 1 个元素中值最大元素被安置在第 n - 1 个位置上。
然后再对前 n - 2 个元素重复上述过程，直到某一趟排序过程中不出现元素交换位置的动作，排序结束。

1.3 动画演示

img

1.4 算法分析

最好的情况下，初始时序列已经是从小到大有序（升序），则只需经过一趟 n - 1 次元素之间的比较，并且不移动元素，算法就可结束排序。此时，算法的时间复杂度为 $O(n)$ 。
最差的情况是当参加排序的初始序列为逆序，或者最小值元素处在序列的最后时，则需要进行 n - 1 趟排序，总共进行 $∑^n_{i=2}(i−1) = \frac{n(n−1)}{2}$ 次元素之间的比较，因此，冒泡排序算法的平均时间复杂度为 $O(n^2)$ 。
冒泡排序方法在排序过程中需要移动较多次数的元素。因此，冒泡排序方法比较适合于参加排序序列的数据量较小的情况，尤其是当序列的初始状态为基本有序的情况；而对于一般情况，这种方法是排序时间效率最低的一种方法。
由于元素交换是在相邻元素之间进行的，不会改变值相同元素的相对位置，因此，冒泡排序法是一种 稳定排序法。

1.5 代码实现

class Solution:
    def bubbleSort(self, arr):
        for i in range(len(arr)):
            for j in range(len(arr) - i - 1):
                # 如果前者大于后者，则两者交换位置
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]

        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.bubbleSort(nums)

2. 选择排序算法

2.1 算法思想

选择排序（Selection Sort） 基本思想：

第 i 趟排序从序列的后 n − i + 1 (i = 1, 2, …, n − 1) 个元素中选择一个值最小的元素与该 n - i + 1 个元素的最前面那个元素交换位置，即与整个序列的第 i 个位置上的元素交换位置。如此下去，直到 i == n − 1，排序结束。

可以简述为：每一趟排序中，从剩余未排序元素中选择一个最小的元素，与未排好序的元素最前面的那个元素交换位置。

2.2 算法步骤

在算法中设置整型变量 i，既可以作为排序趟数的计算，同时也作为执行第 i 趟排序时，参加排序的后 n − i + 1 个元素的第 1 个元素的位置。
整型变量 min_i 记录这 n − i + 1 个元素中值最小元素的位置。
每一趟排序开始，先另 min_i = i （即暂时假设序列的第 i 个元素为值最小者，以后经过比较后视实际情况再正式确定最小值元素的位置）。
第 i 趟排序比较结束时，这 n − i + 1 个元素中真正的值最小元素为下标 min_i 对应的元素。此时，若有 min_i == i，说明值最小元素就是这 n − i + 1 个元素的第 1 个元素，意味着此趟排序不必进行元素交换。

2.3 动画演示

image

2.4 算法分析

对于具有 n 个元素的序列采用选择排序方法要经过 n - 1 趟排序。

当原始序列是一个按值递增序列（升序）时，元素的移动次数最少，为 0 次。当序列初始时是一个按值递减序列（逆序）时，元素的移动次数最多，为 $3(n − 1)$ 次（3 是交换 arr[i] 与 arr[min_i] 的执行次数）。
但是，无论序列中元素的初始排列状态如何，第 i 趟排序要找出值最小元素都需要进行 n − i 次元素之间的比较。因此，整个排序过程需要进行的元素之间的比较次数都相同，为 $∑^n_{i=2}(i - 1) = \frac{n(n−1)}{2}$ 次。
这说明选择排序法所进行的元素之间的比较次数与序列的原始状态无关，同时可以确定算法的时间复杂度为 $O(n^2)$ 。
由于值最小元素与未排好序的元素中第 1 个元素的交换动作是在不相邻的元素之间进行的，因此很有可能会改变值相同元素的前后位置，因此，选择排序法是一种不稳定的排序方法。

2.5 代码实现

class Solution:
    def selectionSort(self, arr):
        for i in range(len(arr) - 1):
            # 记录未排序序列中最小数的索引
            min_i = i
            for j in range(i + 1, len(arr)):
                if arr[j] < arr[min_i]:
                    min_i = j
            # 如果找到最小数，将 i 位置上元素与最小数位置上元素进行交换
            if i != min_i:
                arr[i], arr[min_i] = arr[min_i], arr[i]
        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.selectionSort(nums)

3. 插入排序算法

3.1 算法思想

插入排序（Insertion Sort） 基本思想：

将整个序列切分为两部分：前 i - 1 个元素是有序序列，后 n - i + 1 个元素是无序序列。每一次排序，将无序序列的首元素，在有序序列中找到相应的位置并插入。

可以简述为：每一趟排序中，将剩余无序序列的第一个元素，插入到有序序列的适当位置上。

3.2 算法步骤

将第 1 个元素作为一个有序序列，将第 2 ~ n - 1 个元素作为无序序列。
从无序序列中取出第一个元素，在已经排好序的有序序列中从后向前扫描。
如果扫描到的元素大于取出元素，则将扫描到的元素向右移动 1 位，然后继续向前移动，直到找到有序序列中小于或者等于取出元素的适当位置。
将取出元素插入到适当位置上。
重复 2 ~ 4 步，直到元素全部变为有序序列。

3.3 动画演示

img

3.4 算法分析

对于具有 n 个元素的序列，插入排序方法一共要进行 n - 1 趟排序。
对于插入排序算法，整个排序过程只需要一个辅助空间 temp。
当原始序列是一个按值递增序列（升序）时，对应的每个 i 值只进行一次元素之间的比较，因而总的比较次数最少，为 $∑^n_{i = 2}1 = n − 1$ ，并不需要移动元素（记录），这是最好的情况。
最坏的情况是，序列初始时是一个按值递减序列（逆序），则对应的每个 i 值都要进行 i - 1 次元素之间的比较，总的元素之间的比较次数达到最大值，为 $∑^n_{i=2}(i − 1) = \frac{n(n−1)}{2}$ 。
如果序列的初始情况是随机的，即参加排序的序列中元素可能出现的各种排列的概率相同，则可取上述最小值和最大值的平均值作为插入排序时所进行的元素之间的比较次数，约为 $n^2/4$ 。由此得知，插入排序算法的时间复杂度 $O(n^2)$ 。
插入排序方法属于稳定性排序方法。

3.5 代码实现

class Solution:
    def insertionSort(self, arr):
        for i in range(1, len(arr)):
            # temp 为无序序列中取出的第 1 个元素
            temp = arr[i]
            j = i
            # 将扫描到的元素向右移动，并找到合适的插入位置
            while j > 0 and arr[j - 1] > temp:
                arr[j] = arr[j - 1]
                j -= 1
            # 将取出元素插入到合适位置
            arr[j] = temp

        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.insertionSort(nums)

4. 希尔排序算法

4.1 算法思想

希尔排序（Shell Sort） 基本思想：

将整个序列切按照一定的间隔取值划分为若干个子序列，每个子序列分别进行插入排序。然后逐渐缩小间隔进行下一轮划分子序列和插入排序。直至最后一轮排序间隔为 1，对整个序列进行插入排序。

4.2 算法步骤

首先确定一个元素间隔数 gap，然后将参加排序的序列按此间隔数从第 1 个元素开始一次分成若干个子序列，即分别将所有位置相隔为 gap 的元素视为一个子序列，在各个子序列中采用某种排序方法进行插入排序。
然后减少间隔数，并重新将整个序列按新的间隔数分成若干个子序列，再分别对各个子序列进行排序，如此下去，直到间隔数 gap = 1。

4.3 图解演示

image

4.4 算法分析

希尔排序方法的速度是一系列间隔数 $gap_i$ 的函数，不太容易弄清楚比较次数与 gap 之间的依赖关系，并给出完整的数学分析。
上面算法中，由于采用 $gap_i = \lfloor gap_{i-1}/2 \rfloor$ 的方法缩小间隔数，对于具有 n 个元素的序列，若 $gap_1 = \lfloor n/2 \rfloor$ ，则经过 $p = \lfloor log_2 n \rfloor$ 趟排序后就有 $gap_p = 1$ ，因此，希尔排序方法的排序总躺数为 $\lfloor log_2 n \rfloor$ 。
从算法中也可以看到，最外层的 while 循环为 $log_2 n$ 数量级，中间层 do-while 循环为 n 数量级。当子序列分得越多时，子序列内的元素就越少，最内层的 for 循环的次数也就越少；反之，当所分的子序列个数减少时，子序列内的元素也随之增多，但整个序列也逐步接近有序，而循环次数却不会随之增加。因此，希尔排序算法的时间复杂度在 $O(n log_2 n)$ 与 $O(n^2)$ 之间。
希尔排序方法是一种 不稳定排序算法。

4.5 代码实现

class Solution:
    def shellSort(self, arr):
        size = len(arr)
        gap = size // 2

        while gap > 0:
            # 分别对各个子序列进行排序
            for i in range(gap, size):
                temp = arr[i]
                j = i
                while j >= gap and arr[j - gap] > temp:
                    arr[j] = arr[j - gap]
                    j -= gap
                arr[j] = temp
            # 减少间隔数
            gap = gap // 2
        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.shellSort(nums)

5. 归并排序算法

5.1 算法思想

归并排序（Merge Sort） 基本思想：

采用经典的分治策略，先递归地将当前序列平均分成两半。然后将有序序列两两合并，最终合并成一个有序序列。

5.2 算法步骤

初始时，将待排序序列中的 n 个记录看成 n 个有序子序列（每个子序列总是有序的），每个子序列的长度均为 1。
把当前序列组中有序子序列两两归并，完成一遍之后序列组里的排序序列个数减半，每个子序列的长度加倍。
对长度加倍的有序子序列重复上面的操作，最终得到一个长度为 n 的有序序列。

5.3 动画演示

image

5.4 算法分析

归并排序算法的时间复杂度等于归并趟数与每一趟归并的时间复杂度成绩。子算法 merge(left_arr, right_arr): 的时间复杂度是 $O(n)$ ，因此，归并排序算法总的时间复杂度为 $O(nlog_2n)$ 。
归并排序方法需要用到与参加排序的序列同样大小的辅助空间。因此算法的空间复杂度为 $O(n)$ 。
因为在两个有序子序列的归并过程中，如果两个有序序列中出现相同元素，merge(left_arr, right_arr): 算法能够使前一个序列中那个相同元素先被复制，从而确保这两个元素的相对次序不发生改变。所以归并排序算法是 稳定排序算法。

5.5 代码实现

class Solution:
    # 合并排序
    def merge(self, left_arr, right_arr):
        arr = []
        while left_arr and right_arr:
            if left_arr[0] <= right_arr[0]:
                arr.append(left_arr.pop(0))
            else:
                arr.append(right_arr.pop(0))
        while left_arr:
            arr.append(left_arr.pop(0))
        while right_arr:
            arr.append(right_arr.pop(0))
        return arr
       
    def mergeSort(self, arr):
        # 切分
        size = len(arr)
        if size < 2:
            return arr
        mid = len(arr) // 2
        left_arr, right_arr = arr[0: mid], arr[mid:]
        # 递归切分并合并
        return self.merge(self.mergeSort(left_arr), self.mergeSort(right_arr))

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.mergeSort(nums)

6. 快速排序算法

6.1 算法思想

快速排序（Quick Sort） 基本思想：

通过一趟排序将无序序列分为独立的两个序列，第一个序列的值均比第二个序列的值小。然后递归地排列两个子序列，以达到整个序列有序。

6.2 算法步骤

从数组中找到一个基准数。
然后将数组中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧，从而把数组拆分为左右两个部分。
再对左右两个部分分别重复第二步，直到各个部分只有一个数，则排序结束。

6.3 动画演示

image

6.4 算法分析

在参加排序的元素初始时已经有序的情况下，快速排序方法花费的时间最长。此时，第 1 趟排序经过 n - 1 次比较以后，将第 1 个元素仍然确定在原来的位置上，并得到 1 个长度为 n - 1 的子序列；第 2 趟排序进过 n - 2 次比较以后，将第 2 个元素确定在它原来的位置上，又得到 1 个长度为 n - 2 的子序列；依次类推，最终总的比较次数为 $(n − 1) + (n − 2) + … + 1 = \frac{n(n − 1)}{2}$ 。因此时间复杂度为 $O(n^2)$ 。
还有一种情况，若每趟排序后，分界元素正好定位在序列的中间，从而把当前参加排序的序列分成大小相等的前后两个子序列，则对长度为 n 的序列进行快速排序所需要的时间为：
$\begin{aligned} T(n) \le & \ n + 2T(n/2) \\ \le & \ 2n + 4T(n/2) \\ \le & \ 3n + 8T(n/8) \\ & …… \\ \le & \ (log_2 n)n + nT(1) = O(nlog_2 n) \end{aligned}$

因此，快速排序方法的时间复杂度为 $O(nlog_2 n)$ ，时间性能显然优于前面讨论的几种排序算法。
无论快速排序算法递归与否，排序过程中都需要用到堆栈或其他结构的辅助空间来存放当前待排序序列的首、尾位置。最坏的情况下，空间复杂度为 $O(n)$ 。
若对算法进行一些改写，在一趟排序之后比较被划分所得到的两个子序列的长度，并且首先对长度较短的子序列进行快速排序，这时候需要的空间复杂度可以达到 $O(log_2 n)$ 。
快速排序时一种 不稳定排序算法，也是一种不适合在链表结构上实现的排序算法。

6.5 代码实现

import random


class Solution:
    # 随机选定基准数，并根据基准数将元素移动到正确位置上
    def randomPartition(self, arr: [int], low: int, high: int):
        i = random.randint(low, high)
        arr[i], arr[high] = arr[high], arr[i]
        return self.partition(arr, low, high)

    # 取高位为基准数，并根据基准数将元素移动到正确位置上
    def partition(self, arr: [int], low: int, high: int):
        i = low - 1
        pivot = arr[high]

        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1
    
    # 递归进行快速排序
    def quickSort(self, arr, low, high):
        if low < high:
            pi = self.randomPartition(arr, low, high)
            self.quickSort(arr, low, pi - 1)
            self.quickSort(arr, pi + 1, high)

        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.quickSort(nums, 0, len(nums) - 1)

7. 堆排序算法

7.1 算法思想

堆排序（Heap sort） 基本思想：

借用「堆结构」所设计的排序算法。将数组转化为大顶堆，重复从大顶堆中取出数值最大的节点，并让剩余的堆维持大顶堆性质。

7.2 堆的定义

堆：符合以下两个条件之一的完全二叉树：

大顶堆：根节点值 ≥ 子节点值。
小顶堆：根节点值 ≤ 子节点值。

7.3 算法步骤

首先将无序序列构造成第 1 个大顶堆（初始堆），使得 n 个元素的最大值处于序列的第 1 个位置。
然后交换序列的第 1 个元素（最大值元素）与最后一个元素的位置。
此后，再把序列的前 n - 1 个元素组成的子序列调整成一个新的大顶堆，这样又得到第 2 个最大值元素，把子序列的第 1 个元素（最大值元素）与第 n - 1 个元素交换位置。
此后再把序列的前 n - 2 个元素调整成一个新的大顶堆，……，如此下去，直到整个序列变换成一个有序序列。

可见堆排序算法主要涉及「初始堆建立方法」和「堆调整方法」。

7.3.1 堆调整方法

堆调整方法就是：把移走了最大值元素以后的剩余元素组成的序列再构造为一个新的堆积。具体步骤如下：

从根节点开始，自上而下地调整节点的位置，使其成为堆积。即把序号为 i 的节点与其左子树节点（序号为 2 * i）、右子树节点（序号为 2 * i + 1）中值最大的节点交换位置。
因为交换了位置，使得当前节点的左右子树原有的堆积特性被破坏。于是，从当前节点的左右子树节点开始，自上而下继续进行类似的调整。
如此下去直到整棵完全二叉树成为一个大顶堆。

7.3.2 初始堆建立方法

如果原始序列对应的完全二叉树（不一定是堆）的深度为 d，则从 d - 1 层最右侧分支节点（序号为 $\lfloor n/2 \rfloor$ ）开始，初始时令 $i = \lfloor n/2 \rfloor$ ，调用堆调整算法。
每调用一次堆调整算法，执行一次 i = i - 1，直到 i == 1 时，再调用一次，就把原始序列调整为了一个初始堆。

7.4 动画演示

7.4.1 堆调整方法演示

image

7.4.2 初始堆建立方法演示

image

7.4.3 堆排序方法演示

image

7.5 算法分析

堆积排序的时间主要花费在两个方面：
- 将原始序列构造为一个初始堆积。
- 排序过程中不断将移走最大值元素，然后将剩下元素重新调整为一个新堆积。
设原始序列所对应的完全二叉树深度为 d，算法由两个独立的循环组成：
- 在第 1 个循环构造初始堆积时，从 i = d - 1 层开始，到 i = 1 层为止，对每个分支节点都要调用一次 adjust 算法，每一次 adjust 算法，对于第 i 层一个节点到第 d 层上建立的子堆积，所有节点可能移动的最大距离为该子堆积根节点移动到最后一层（第 d 层）的距离即 d - i。
- 而第 i 层上节点最多有 $2^{i-1}$ 个，所以每一次 adjust 算法最大移动距离为 $2^{i-1} * (d-i)$ 。因此，堆积排序算法的第 1 个循环所需时间应该是各层上的节点数与该层上节点可移动的最大距离之积的总和，即： $\sum_{i = d - 1}^1 2^{i-1} (d-i) = \sum_{j = 1}^{d-1} 2^{d-j-1} \times j = \sum_{j = 1}^{d-1} 2^{d-1} \times {j \over 2^j} \le n \sum_{j = 1}^{d-1} {j \over 2^j} < 2n$ 。这一部分时间花费为 $O(n)$ 。
- 在算法的第 2 个循环中每次调用 adjust 算法一次，节点移动的最大距离为这棵完全二叉树的深度 $d = \lfloor log_2(n) \rfloor + 1$ ，一共调用了 n - 1 次 adjust 算法，所以，第 2 个循环的时间花费为 $(n-1)(\lfloor log_2 (n)\rfloor + 1) = O(n log_2 n)$ 。
因此，堆积排序的时间复杂度为 $O(nlog_2 n)$ 。
由于在堆积排序中只需要一个记录大小的辅助空间，因此，堆积排序的空间复杂度为： $O(1)$ 。
堆排序属于 不稳定排序算法。堆排序也是一种不适合在链表上实现的排序。

7.6 代码实现

class Solution:
    # 调整为大顶堆
    def heapify(self, arr: [int], index: int, end: int):
        left = index * 2 + 1
        right = left + 1
        while left <= end:
            # 当前节点为非叶子结点
            max_index = index
            if arr[left] > arr[max_index]:
                max_index = left
            if right <= end and arr[right] > arr[max_index]:
                max_index = right
            if index == max_index:
                # 如果不用交换，则说明已经交换结束
                break
            arr[index], arr[max_index] = arr[max_index], arr[index]
            # 继续调整子树
            index = max_index
            left = index * 2 + 1
            right = left + 1

    # 初始化大顶堆
    def buildMaxHeap(self, arr: [int]):
        size = len(arr)
        # (size-2) // 2 是最后一个非叶节点，叶节点不用调整
        for i in range((size - 2) // 2, -1, -1):
            self.heapify(arr, i, size - 1)
        return arr

    # 升序堆排序，思路如下：
    # 1. 先建立大顶堆
    # 2. 让堆顶最大元素与最后一个交换，然后调整第一个元素到倒数第二个元素，这一步获取最大值
    # 3. 再交换堆顶元素与倒数第二个元素，然后调整第一个元素到倒数第三个元素，这一步获取第二大值
    # 4. 以此类推，直到最后一个元素交换之后完毕。
    def maxHeapSort(self, arr: [int]):
        self.buildMaxHeap(arr)
        size = len(arr)
        for i in range(size):
            arr[0], arr[size - i - 1] = arr[size - i - 1], arr[0]
            self.heapify(arr, 0, size - i - 2)
        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.maxHeapSort(nums)

8. 计数排序算法

8.1 算法思想

计数排序（Counting Sort） 基本思想：

使用一个额外的数组 counts，其中第 i 个元素 counts[i] 是待排序数组 arr 中值等于 i 的元素个数。然后根据数组 counts 来将 arr 中的元素排到正确的位置。

8.2 算法步骤

找出待排序数组中最大值元素和最小值元素。
统计数组中每个值为 i 的元素出现的次数，存入数组的第 i 项。
对所有的计数累加（从 counts 中的第一个元素开始，每一项和前一项累加）。
反向填充目标数组：将每个元素 i 放在新数组的第 counts[i] 项，每放一个元素就要将 counts[i] -= 1。

8.3 动画演示

image

8.4 算法分析

当输入元素是 n 个 0 ~ k 之间的整数时，计数排序的时间复杂度为 $O(n + k)$ 。
由于用于计数的数组 counts 的长度取决于待排序数组中数据的范围（等于待排序数组最大值减去最小值再加 1）。所以计数排序对于数据范围很大的数组，需要大量的时间和内存。
计数排序一般用于排序整数，不适用于按字母顺序排序人名。
计数排序是 稳定排序算法。

8.5 代码实现

class Solution:
    def countingSort(self, arr):
        # 待排序数组中最大值元素和最小值元素
        arr_min, arr_max = min(arr), max(arr)

        size = arr_max - arr_min + 1
        counts = [0 for _ in range(size)]
        # 统计数组中每个值为 `num` 的元素出现的次数，存入数组的第 `num - arr_min` 项
        for num in arr:
            counts[num - arr_min] += 1
        # 所有的计数累加
        for j in range(1, size):
            counts[j] += counts[j - 1]
        
        # 反向填充目标数组
        res = [0 for _ in range(len(arr))]
        for i in range(len(arr) - 1, -1, -1):
            res[counts[arr[i] - arr_min] - 1] = arr[i]
            counts[arr[i] - arr_min] -= 1

        return res

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.countingSort(nums)

9. 桶排序算法

9.1 算法思想

桶排序（Bucket Sort） 基本思想：

将未排序的数组分到若干个「桶」中，每个桶的元素再进行单独排序。

9.2 算法步骤

将区间划分为 n 个相同大小的子区间，每个区间称为一个桶。
遍历数组，将每个元素装入对应的桶中。
对每个桶内的元素单独排序（使用插入、归并、快排等算法）。
最后按照顺序将桶内的元素合并起来。

9.3 图解演示

9.3.1 划分子区间

image

9.3.2 将数组元素装入桶中，并对桶内元素单独排序

image

9.3.3 将桶内元素合并起来，完成排序

image

9.4 算法分析

桶排序可以在线性时间内完成排序，当输入元素个数为 n，桶的个数是 m 时，桶排序时间复杂度为 $O(n + m)$ 。
由于桶排序使用了辅助空间，所以桶排序的空间复杂度是 o(n + m)。
如果桶内使用插入排序算法等稳定排序算法，则桶排序也是 稳定排序算法。

9.5 代码实现

class Solution:
    # 插入排序
    def insertionSort(self, arr):
        for i in range(1, len(arr)):
            temp = arr[i]
            j = i
            while j > 0 and arr[j - 1] > temp:
                arr[j] = arr[j - 1]
                j -= 1
            arr[j] = temp

        return arr

    def bucketSort(self, arr, bucket_size=5):
        # 划分子区间，并创建桶
        arr_min, arr_max = min(arr), max(arr)
        bucket_count = (arr_max - arr_min) // bucket_size + 1
        buckets = [[] for _ in range(bucket_count)]
        
        # 将每个元素装入对应的桶中
        for num in arr:
            buckets[(num - arr_min) // bucket_size].append(num)
        
        res = []
        # 对桶内元素使用插入排序算法，并将排序后结果存入目标数组
        for bucket in buckets:
            self.insertionSort(bucket)
            res.extend(bucket)

        return res

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.bucketSort(nums)

10. 基数排序算法

10.1 算法思想

基数排序（Radix Sort） 基本思想：

将整数按位数切割成不同的数字，然后按每个位数分别比较进行排序。

10.2 算法步骤

基数排序算法可以采用「最低位优先法（Least Significant Digit First）」或者「最高位优先法（Most Significant Digit first）」。最常用的是「最低位优先法」。

下面我们以最低位优先法为例，讲解一下算法步骤。

遍历数组元素，获取数组最大值元素，并取得位数。
以个位元素为索引，对数组元素排序。
合并数组。
之后依次以十位，百位，…，直到最大值元素的最高位处值为索引，进行排序，并合并数组，最终完成排序。

10.3 动画演示

image

10.4 算法分析

基数排序的时间复杂度是 $O(k * n)$ 。其中 n 是待排序元素的个数，k 是数字位数。k 的大小取决于数字位的选择（十进制位、二进制位）和待排序元素所属数据类型全集的大小。
基数排序只适合正数元素排序。
基数排序的空间复杂度是 $O(n + k)$ 。
基数排序是 稳定排序算法。

10.5 代码实现

class Solution:
    def radixSort(self, arr):
        # 计算位数最长的位数
        size = len(str(max(arr)))
        
        # 从个位到高位遍历位数
        for i in range(size):
            buckets = [[] for _ in range(10)]
            for num in arr:
                buckets[num // (10 ** i) % 10].append(num)
            arr.clear()
            # 生成新的数组
            for bucket in buckets:
                for num in bucket:
                    arr.append(num)

        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.radixSort(nums)

算法通过手册：05 数组十大经典排序算法

1. 冒泡排序算法

1.1 算法思想

1.2 算法步骤

1.3 动画演示

1.4 算法分析

1.5 代码实现

2. 选择排序算法

2.1 算法思想

2.2 算法步骤

2.3 动画演示

2.4 算法分析

2.5 代码实现

3. 插入排序算法

3.1 算法思想

3.2 算法步骤

3.3 动画演示

3.4 算法分析

3.5 代码实现

4. 希尔排序算法

4.1 算法思想

4.2 算法步骤

4.3 图解演示

4.4 算法分析

4.5 代码实现

5. 归并排序算法

5.1 算法思想

5.2 算法步骤

5.3 动画演示

5.4 算法分析

5.5 代码实现

6. 快速排序算法

6.1 算法思想

6.2 算法步骤

6.3 动画演示

6.4 算法分析

6.5 代码实现

7. 堆排序算法

7.1 算法思想

7.2 堆的定义

7.3 算法步骤

7.3.1 堆调整方法

7.3.2 初始堆建立方法

7.4 动画演示

7.4.1 堆调整方法演示

7.4.2 初始堆建立方法演示

7.4.3 堆排序方法演示

7.5 算法分析

7.6 代码实现

8. 计数排序算法

8.1 算法思想

8.2 算法步骤

8.3 动画演示

8.4 算法分析

8.5 代码实现

9. 桶排序算法

9.1 算法思想

9.2 算法步骤

9.3 图解演示

9.3.1 划分子区间

9.3.2 将数组元素装入桶中，并对桶内元素单独排序

9.3.3 将桶内元素合并起来，完成排序

9.4 算法分析

9.5 代码实现

10. 基数排序算法

10.1 算法思想

10.2 算法步骤

10.3 动画演示

10.4 算法分析

10.5 代码实现

猜你喜欢

热点阅读