【基础算法】（二）高效排序（快排、归并、堆排）

快速排序 (Quick Sort)

算法原理

快速排序采用分治策略，通过选择一个"基准"元素将数组分成两个子数组：一个包含小于基准的元素，另一个包含大于基准的元素，然后递归地对子数组进行排序。

代码实现

def find_index(nums, beg, end):
    index = beg
    j = index + 1

    for i in range(beg+1, end+1):
        if nums[i] < nums[index]:
            nums[j], nums[i] = nums[i], nums[j]
            j += 1
    nums[index], nums[j-1] = nums[j-1], nums[index]
    index = j - 1

    return index

def quick_sort(nums, beg, end):
    if beg >= end:
        return
  
    index = find_index(nums, beg, end)
    quick_sort(nums, beg, index - 1)
    quick_sort(nums, index + 1, end)

算法分析

• 时间复杂度：
  • 最好情况：O(n log n)
  • 最坏情况：O(n²)（当数组已排序或逆序时）
  • 平均情况：O(n log n)
• 空间复杂度：
  • 最好情况：O(log n)（递归调用栈）
  • 最坏情况：O(n)
• 稳定性：不稳定排序

归并排序 (Merge Sort)

算法原理

归并排序是典型的分治算法，它将数组分成两半，递归地对每一半进行排序，然后将两个有序的子数组合并成一个有序数组。

代码实现

def merge(nums, beg, mid, end):
    nums1 = nums[beg: mid+1]
    nums2 = nums[mid+1: end+1]
    temp_res = []
    i = 0
    j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            temp_res.append(nums1[i])
            i += 1
        else:
            temp_res.append(nums2[j])
            j += 1
    temp_res.extend(nums1[i:])
    temp_res.extend(nums2[j:])
    nums[beg:end+1] = temp_res[:]

def merge_sort(nums, beg, end):
    if beg >= end:
        return
    mid = (beg + end) // 2

    merge_sort(nums, beg, mid)
    merge_sort(nums, mid+1, end)
    merge(nums, beg, mid, end)

算法分析

• 时间复杂度：始终为O(n log n)
• 空间复杂度：O(n)（需要额外的存储空间）
• 稳定性：稳定排序

堆排序 (Heap Sort)

算法原理

堆排序利用堆这种数据结构所设计的一种排序算法。它首先将数组构建成一个大顶堆，然后反复将堆顶元素（最大值）与末尾元素交换，并重新调整堆结构。

代码实现

def max_heap(nums, index):
    n = len(nums)
    son = 2 * index + 1
    while son < n:
        if son + 1 < n and nums[son] < nums[son+1]:
            son = son + 1

        if nums[index] < nums[son]:
            nums[index], nums[son] = nums[son], nums[index]
            index = son
            son = 2 * son + 1
        else:
            break
  
def heap_sort(nums):
    n = len(nums)
    mid = n // 2
    for i in range(mid, -1, -1):
        max_heap(nums, i)
  
    for i in range(n // 2 + 1):
        nums[i], nums[n-i-1] = nums[n-i-1], nums[i]
        max_heap(nums[:n-i-1], 0)

算法分析

• 时间复杂度：始终为O(n log n)
• 空间复杂度：O(1)（原地排序）
• 稳定性：不稳定排序

三种排序算法的比较