在上一篇文章中，我们探讨了“桶排序”与“基数排序”这两种进阶排序算法，了解了它们各自的工作原理及适用场景。在本篇中，我们将重点比较几种更高级的排序算法，包括“归并排序”、“堆排序”和“快速排序”。这些排序算法在实际应用中具有重要的意义，特别是在处理大规模数据时。

归并排序

概述

归并排序是一种“分治算法”，其基本思想是将一个数组分成两半，对这两半分别进行排序，然后将两个已排序的部分合并成一个有序数组。

算法步骤

1. 分解：将数组分成大约相等的两半。
2. 递归：对这两个子数组递归地进行归并排序。
3. 合并：将两个已排序的子数组合并成一个最终的排序数组。

复杂度分析

归并排序的时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$，因为在合并过程中需要额外的存储空间。排序的稳定性使得归并排序在某些情况下更受欢迎。

代码示例

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
复制

堆排序

概述

堆排序利用二叉堆的数据结构来排序数组。它分为两个阶段：首先构建最大堆，然后逐步将堆顶元素（最大值）移动到数组末尾，并重新调整堆。

算法步骤

1. 构建最大堆：将无序数组调整为一个最大堆。
2. 交换：将堆顶元素与最后一个元素交换，减少堆的大小，并重新调整堆。

复杂度分析

堆排序的时间复杂度为 $O(n \log n)$，空间复杂度为 $O(1)$，由于使用的是原地排序，因此不需要额外的存储空间。

代码示例

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
复制

快速排序

概述

快速排序同样是一种“分治算法”。它通过一个“基准”元素将数组划分为两个子数组：左侧是小于基准的元素，右侧是大于基准的元素。

算法步骤

1. 选择基准：选择数组中的一个元素作为基准。
2. 分区：重新排列数组，使得所有小于基准的元素在其左侧，所有大于基准的元素在其右侧。
3. 递归：对基准左侧和右侧的子数组进行快速排序。

复杂度分析

快速排序的平均时间复杂度为 $O(n \log n)$，在最坏情况下（例如，已经排序的数组），时间复杂度退化为 $O(n^2)$。不过，快速排序的空间复杂度为 $O(\log n)$，且其排序效率通常优于其他 $O(n \log n)$ 的算法。

代码示例

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    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 quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)
复制

总结

在本篇文章中，我们深入探讨了几种高级排序算法：归并排序、堆排序和快速排序。每种算法都有其独特的特性与应用场景，选择合适的排序算法对于提升程序的性能至关重要。在下一篇文章中，我们将转向图算法，深入解析 Dijkstra算法 和 A* 算法，了解它们在路径搜索方面的重要性与应用场景。