数据结构与算法 排序（下）

数据结构与算法 排序（上）https://developer.aliyun.com/article/1504023?spm=a2c6h.13148508.setting.15.36834f0eMJOehx

归并排序

归并排序(merge sort)：是一种基于分治策略的排序算法，包含图 11‑10 所示的“划分”和“合并”阶段。

1. 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
2. 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。
   

归并排序与二叉树后序遍历的递归顺序是一致的。

• 后序遍历：先递归左子树，再递归右子树，最后处理根节点。
• 归并排序：先递归左子数组，再递归右子数组，最后处理合并。

def merge(lst, left, mid, right):
    tmp = list(lst[left:right+1])
  
    left_start = 0
    left_end = mid - left
  
    right_start = mid - left + 1
    right_end = right - left
  
    i = left_start
    j = right_start
    for k in range(left, right + 1):
        if i > left_end:
            lst[k] = tmp[j]
            j += 1
        elif j > right_end or tmp[i] <= tmp[j]:
            lst[k] = tmp[i]
            i += 1
        else:
            lst[k] = tmp[j]
            j += 1
  
def merge_sort(lst, left, right):
    if left >= right:
        return None
    mid = int(left + (right - left)/2)
    merge_sort(lst, left, mid)
    merge_sort(lst, mid+1, right)
    merge(lst, left, mid, right)
    return lst

算法特性

• 时间复杂度 𝑂(𝑛 log 𝑛)、非自适应排序：划分产生高度为 log 𝑛 的递归树，每层合并的总操作数量为𝑛 ，因此总体时间复杂度为 𝑂(𝑛 log 𝑛) 。
• 空间复杂度 𝑂(𝑛)、非原地排序：递归深度为 log 𝑛 ，使用 𝑂(log 𝑛) 大小的栈帧空间。合并操作需要借助辅助数组实现，使用 𝑂(𝑛) 大小的额外空间。
• 稳定排序：在合并过程中，相等元素的次序保持不变。

链表排序

对于链表，归并排序相较于其他排序算法具有显著优势，可以将链表排序任务的空间复杂度优化至 𝑂(1) 。

• 划分阶段：可以通过使用“迭代”替代“递归”来实现链表划分工作，从而省去递归使用的栈帧空间。
• 合并阶段：在链表中，节点增删操作仅需改变引用（指针）即可实现，因此合并阶段（将两个短有序链表合并为一个长有序链表）无须创建额外链表。

堆排序

堆排序(heap sort):是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。

1. 输入数组并建立小顶堆，此时最小元素位于堆顶。
2. 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。

设数组的长度为 𝑛 ，堆排序的流程如图 11‑12 所示。

1. 输入数组并建立大顶堆。完成后，最大元素位于堆顶。
2. 将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减 1 ，已排序元素数量加 1 。
3. 从堆顶元素开始，从顶到底执行堆化操作（Sift Down）。完成堆化后，堆的性质得到修复。
4. 循环执行第 2. 和 3. 步。循环 𝑛 − 1 轮后，即可完成数组排序。
   

代码

def sift_down(lst, size, ix):
    while True:
        l, r, max = 2*ix + 1, 2*ix + 2, ix
        if l < size and lst[l] > lst[max]:
            max = l
        if r < size and lst[r] > lst[max]:
            max = r
        if max == ix:
            break
        lst[max], lst[ix] = lst[ix], lst[max]
        ix = max
    return lst
  
def heap_sort(lst):
    # 建堆
    for i in range(len(lst), -1, -1):
        sift_down(lst, len(lst), i)
    # 从堆中提取最大元素，循环 n-1 轮
    for i in range(len(lst)-1, 0, -1):
        lst[0], lst[i] = lst[i], lst[0]
        sift_down(lst, i, 0)

算法特性

• 时间复杂度 𝑂(𝑛 log 𝑛)、非自适应排序：建堆操作使用 𝑂(𝑛) 时间。从堆中提取最大元素的时间复杂度为 𝑂(log 𝑛) ，共循环 𝑛 − 1 轮。
• 空间复杂度 𝑂(1)、原地排序：几个指针变量使用 𝑂(1) 空间。元素交换和堆化操作都是在原数组上进行的。
• 非稳定排序：在交换堆顶元素和堆底元素时，相等元素的相对位置可能发生变化。

桶排序

桶排序(bucket sort):是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。

考虑一个长度为 𝑛 的数组

1. 初始化 𝑘 个桶，将 𝑛 个元素分配到 𝑘 个桶中。
2. 对每个桶分别执行排序（本文采用编程语言的内置排序函数）。
3. 按照桶的从小到大的顺序，合并结果。
   

代码

def bucket_sort(nums: list[float]):
    """ 桶排序"""
    # 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    k = len(nums) // 2
    buckets = [[] for _ in range(k)]
    # 1. 将数组元素分配到各个桶中
    for num in nums:
        # 输入数据范围 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
        i = int(num * k)
        # 将 num 添加进桶 i
        buckets[i].append(num)
    # 2. 对各个桶执行排序
    for bucket in buckets:
        # 使用内置排序函数，也可以替换成其他排序算法
        bucket.sort()
    # 3. 遍历桶合并结果
    i = 0
    for bucket in buckets:
        for num in bucket:
            nums[i] = num
            i += 1
    return nums

算法特性

桶排序适用于处理体量很大的数据。例如，输入数据包含 100 万个元素，由于空间限制，系统内存无法一次性加载所有数据。此时，可以将数据分成 1000 个桶，然后分别对每个桶进行排序，最后将结果合并。桶排序的重点在于均匀分配

计数排序

计数排序(counting sort)：通过统计元素数量来实现排序，通常应用于整数数组。

给定一个长度为 𝑛 的数组 nums ，其中的元素都是“非负整数”.

1. 遍历数组，找出数组中的最大数字，记为 𝑚 ，然后创建一个长度为 𝑚 + 1 的辅助数组 counter 。
2. 借助 counter 统计 nums 中各数字的出现次数，其中 counter[num] 对应数字 num 的出现次数。统计方法很简单，只需遍历 nums（设当前数字为 num），每轮将 counter[num] 增加 1 即可。
3. 由于 counter 的各个索引天然有序，因此相当于所有数字已经被排序好了。接下来，我们遍历 counter，根据各数字的出现次数，将它们按从小到大的顺序填入 nums 即可。

代码

def count_sort(lst):
    size = max(lst)
    tmp = [0] * (size + 1)
    for item in lst:
        tmp[item] += 1
    i = 0
    for num in range(size+1):
        for _ in range(tmp[num]):
            lst[i] = num
            i += 1
    return lst

前缀和

如果输入数据是对象，上述步骤 3. 就失效了。假设输入数据是商品对象，我们想要按照商品价格（类的成员变量）对商品进行排序，而上述算法只能给出价格的排序结果。利用前缀和得到原数据的排序结果

前缀和代码

def count_sort(lst):
    size = max(lst)
    tmp = [0] * (size + 1)
    for item in lst:
        tmp[item] += 1
    for i in range(size):
        tmp[i+1] += tmp[i]
  
    new_lst = [0]*len(lst)
    for item in lst[::-1]:
        new_lst[tmp[item] - 1] = item
        tmp[item] -= 1
    return new_lst

算法特性

• 时间复杂度 𝑂(𝑛 + 𝑚) ：涉及遍历 nums 和遍历 counter ，都使用线性时间。一般情况下 𝑛 ≫ 𝑚 ，时间复杂度趋于 𝑂(𝑛) 。
• 空间复杂度 𝑂(𝑛 + 𝑚)、非原地排序：借助了长度分别为 𝑛 和 𝑚 的数组 res 和 counter。
• 稳定排序：由于向 res 中填充元素的顺序是“从右向左”的，因此倒序遍历 nums 可以避免改变相等元素之间的相对位置，从而实现稳定排序。实际上，正序遍历 nums 也可以得到正确的排序结果，但结果是非稳定的。
• 计数排序只适用于非负整数。 若想要将其用于其他类型的数据，需要确保这些数据可以被转换为非负整数，并且在转换过程中不能改变各个元素之间的相对大小关系。例如，对于包含负数的整数数组，可以先给所有数字加上一个常数，将全部数字转化为正数，排序完成后再转换回去即可。计数排序适用于数据量大但数据范围较小的情况。 比如，在上述示例中 𝑚 不能太大，否则会占用过多空间。而当 𝑛 ≪ 𝑚 时，计数排序使用 𝑂(𝑚) 时间，可能比 𝑂(𝑛 log 𝑛) 的排序算法还要慢。

基数排序

基数排序(radix sort)的核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。

代码

def digit(num, exp):
    return (num // exp) % 10
  
def count_sort(lst, exp):
    counter = [0] * 10
    n = len(lst)
    for i in range(n):
        d = digit(lst[i], exp)
        counter[d] += 1
  
    for i in range(9):
        counter[i+1] += counter[i]
  
    res = [0] * n
    for i in range(n-1, -1, -1):
        d = digit(lst[i], exp)
        j = counter[d] - 1
        res[j] = lst[i]
        counter[d] -= 1
    for i in range(n):
        lst[i] = res[i]
  
def radix_sort(lst):
    m = max(lst)
    exp = 1
    while exp <= m:
        count_sort(lst, exp)
        exp *= 10
    return lst

算法特性

相较于计数排序，基数排序适用于数值范围较大的情况，但前提是数据必须可以表示为固定位数的格式，且位数不能过大。例如，浮点数不适合使用基数排序，因为其位数 𝑘 过大，可能导致时间复杂度 𝑂(𝑛𝑘) ≫ 𝑂(𝑛2 )。

重点回顾

• 冒泡排序通过交换相邻元素来实现排序。通过添加一个标志位来实现提前返回，我们可以将冒泡排序的最佳时间复杂度优化到 𝑂(𝑛) 。
• 插入排序每轮将未排序区间内的元素插入到已排序区间的正确位置，从而完成排序。虽然插入排序的时间复杂度为 𝑂(𝑛2 ) ，但由于单元操作相对较少，它在小数据量的排序任务中非常受欢迎。
• 快速排序基于哨兵划分操作实现排序。在哨兵划分中，有可能每次都选取到最差的基准数，导致时间复杂度劣化至 𝑂(𝑛2 ) 。引入中位数基准数或随机基准数可以降低这种劣化的概率。尾递归方法可以有效地减少递归深度，将空间复杂度优化到 𝑂(log 𝑛) 。
• 归并排序包括划分和合并两个阶段，典型地体现了分治策略。在归并排序中，排序数组需要创建辅助数组，空间复杂度为 𝑂(𝑛) ；然而排序链表的空间复杂度可以优化至 𝑂(1) 。
• 桶排序包含三个步骤：数据分桶、桶内排序和合并结果。它同样体现了分治策略，适用于数据体量很大的情况。桶排序的关键在于对数据进行平均分配。
• 计数排序是桶排序的一个特例，它通过统计数据出现的次数来实现排序。计数排序适用于数据量大但数据范围有限的情况，并且要求数据能够转换为正整数。
• 基数排序通过逐位排序来实现数据排序，要求数据能够表示为固定位数的数字。
• 总的来说，我们希望找到一种排序算法，具有高效率、稳定、原地以及正向自适应性等优点。然而，正如其他数据结构和算法一样，没有一种排序算法能够同时满足所有这些条件。在实际应用中，我们需要根据数据的特性来选择合适的排序算法。
• 图 11‑19 对比了主流排序算法的效率、稳定性、就地性和自适应性等。
  

Q&A

• 排序算法稳定性在什么情况下是必须的？
  在现实中，我们有可能是在对象的某个属性上进行排序。例如，学生有姓名和身高两个属性，我们希望实现一个多级排序先按照姓名进行排序，得到 (A, 180) (B, 185) (C, 170) (D, 170) ；接下来对身高进行排序。由于排序算法不稳定，我们可能得到 (D, 170) (C, 170) (A, 180) (B, 185) 。可以发现，学生 D 和 C 的位置发生了交换，姓名的有序性被破坏了，而这是我们不希望看到的。
• 哨兵划分中“从右往左查找”与“从左往右查找”的顺序可以交换吗？
  不行，当我们以最左端元素为基准数时，必须先“从右往左查找”再“从左往右查找”。这个结论有些反直觉，我们来剖析一下原因。哨兵划分 partition() 的最后一步是交换nums[left] 和 nums[i] 。完成交换后，基准数左边的元素都 <= 基准数，这就要求最后一步交换前 nums[left] >= nums[i] 必须成立。假设我们先“从左往右查找”，那么如果找不到比基准数更小的元素，则会在 i == j 时跳出循环，此时可能 nums[j] == nums[i] > nums[left]。也就是说，此时最后一步交换操作会把一个比基准数更大的元素交换至数组最左端，导致哨兵划分失败。举个例子，给定数组 [0, 0, 0, 0, 1] ，如果先“从左向右查找”，哨兵划分后数组为[1, 0, 0, 0, 0] ，这个结果是不正确的。再深入思考一下，如果我们选择 nums[right] 为基准数，那么正好反过来，必须先“从左往右查找”。
• 关于尾递归优化，为什么选短的数组能保证递归深度不超过 log 𝑛 ？
  递归深度就是当前未返回的递归方法的数量。每轮哨兵划分我们将原数组划分为两个子数组。在尾递归优化后，向下递归的子数组长度最大为原数组的一半长度。假设最差情况，一直为一半长度，那么最终的递归深度就是 log 𝑛 。回顾原始的快速排序，我们有可能会连续地递归长度较大的数组，最差情况下为 𝑛、𝑛 − 1、…、2、1 ，递归深度为 𝑛 。尾递归优化可以避免这种情况的出现。
• 当数组中所有元素都相等时，快速排序的时间复杂度是 𝑂(𝑛2 ) 吗？该如何处理这种退化情况？
  是的。这种情况可以考虑通过哨兵划分将数组划分为三个部分：小于、等于、大于基准数。仅向下递归小于和大于的两部分。在该方法下，输入元素全部相等的数组，仅一轮哨兵划分即可完成排序。
• 桶排序的最差时间复杂度为什么是 𝑂(𝑛2 ) ？
  最差情况下，所有元素被分至同一个桶中。如果我们采用一个 𝑂(𝑛2 ) 算法来排序这些元素，则时间复杂度为 𝑂(𝑛2 ) 。