排序算法学习笔记

一、经典排序算法对比

1.1 冒泡排序（Bubble Sort）

• 原理：重复比较相邻元素，若顺序错误则交换，每趟将最大（或最小）元素“冒泡”到数组末尾。
• 时间复杂度：平均和最坏情况为 $O(n^2)$，最好情况为 $O(n)$（数组已有序）。
• 空间复杂度：$O(1)$。
• 代码示例：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))

1.2 选择排序（Selection Sort）

• 原理：每趟从未排序元素中选最小（或最大）元素，与未排序部分第一个元素交换位置。
• 时间复杂度：平均、最坏和最好情况均为 $O(n^2)$。
• 空间复杂度：$O(1)$。
• 代码示例：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


arr = [64, 34, 25, 12, 22, 11, 90]
print(selection_sort(arr))

1.3 插入排序（Insertion Sort）

• 原理：将数组分为已排序和未排序两部分，每次从未排序部分取一个元素，插入到已排序部分合适位置，类似扑克牌整理。
• 时间复杂度：平均和最坏情况为 $O(n^2)$，最好情况为 $O(n)$（数组已有序）。
• 空间复杂度：$O(1)$。
• 代码示例：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr


arr = [64, 34, 25, 12, 22, 11, 90]
print(insertion_sort(arr))

1.4 快速排序（Quick Sort）

• 原理：选一个基准元素（pivot），将数组分两部分，左边元素小于等于基准，右边元素大于等于基准，对左右两部分递归排序。
• 时间复杂度：平均情况为 $O(nlogn)$，最坏情况为 $O(n^2)$（每次选的基准为数组最大或最小元素）。
• 空间复杂度：平均为 $O(logn)$，最坏为 $O(n)$。
• 代码示例：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)


arr = [64, 34, 25, 12, 22, 11, 90]
print(quick_sort(arr))

1.5 归并排序（Merge Sort）

• 原理：采用分治思想，将数组不断分成两半，直到子数组长度为1，再将子数组合并成有序数组。
• 时间复杂度：平均、最坏和最好情况均为 $O(nlogn)$。
• 空间复杂度：$O(n)$。
• 代码示例：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    return merge(left_half, right_half)


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


arr = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(arr))

1.6 堆排序（Heap Sort）

• 原理：利用堆数据结构，将数组构建成最大堆（或最小堆），每次取堆顶元素与堆最后一个元素交换位置，调整堆结构，直到堆为空。
• 时间复杂度：平均、最坏和最好情况均为 $O(nlogn)$。
• 空间复杂度：$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)
    return arr


arr = [64, 34, 25, 12, 22, 11, 90]
print(heap_sort(arr))

1.7 Timsort

• 平均情况性能：
  • 时间复杂度：平均为 $O(n \log n)$，利用归并排序思想合并有序片段，能快速识别并利用数据中的局部有序部分，在处理部分有序数组时效率高。
  • 空间复杂度：为 $O(n)$，合并过程需额外空间存储临时结果，Python内置实现有优化可减少临时空间使用。
• 最坏情况性能：
  • 时间复杂度：最坏仍为 $O(n \log n)$，即使数组完全无序，通过合理划分run并归并排序保证高效。
  • 空间复杂度：同样为 $O(n)$。
• 优点：
  • 适应性强：对各种类型数据（部分有序、完全无序等）表现良好，能自动检测并利用数据中的有序部分，适用于数据库排序等场景。
  • 稳定性：是稳定排序算法，相等元素相对顺序排序前后不变，适用于需保持元素相对顺序的场景。
• 缺点：实现复杂，结合多种排序策略，理解和维护代码难度增加。
• 代码示例：

def timsort(arr):
    min_run = 32
    n = len(arr)
    for i in range(0, n, min_run):
        insertion_sort(arr, i, min((i + min_run - 1), n - 1))
    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            midpoint = start + size - 1
            end = min((start + size * 2 - 1), (n - 1))
            merged_array = merge(arr, start, midpoint, end)
            arr[start:start + len(merged_array)] = merged_array
        size *= 2
    return arr


def insertion_sort(arr, left, right):
    for i in range(left + 1, right + 1):
        key_item = arr[i]
        j = i - 1
        while j >= left and arr[j] > key_item:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key_item


def merge(arr, start, midpoint, end):
    left = arr[start:midpoint + 1]
    right = arr[midpoint + 1:end + 1]
    l, r = 0, 0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result


arr = [64, 34, 25, 12, 22, 11, 90]
print(timsort(arr))

1.8 IntroSort

• 平均情况性能：
  • 时间复杂度：平均为 $O(n \log n)$，平均情况下主要依赖快速排序，通过随机选枢轴元素使数组大致均匀划分，递归深度保持在 $O(\log n)$ 级别。
  • 空间复杂度：平均为 $O(\log n)$，快速排序平均递归深度为 $O(\log n)$，递归调用栈占用空间。
• 最坏情况性能：
  • 时间复杂度：最坏为 $O(n \log n)$，当快速排序可能出现最坏情况时，切换到堆排序保证性能。
  • 空间复杂度：最坏为 $O(n)$，快速排序退化为链表形式递归调用时，递归调用栈深度达 $O(n)$。
• 优点：
  • 高效通用：在各种数据分布下性能良好，能快速处理完全随机和含大量重复元素的数据，如游戏玩家分数排序。
  • 避免最坏情况：通过设置递归深度限制，避免快速排序最坏情况下 $O(n^2)$ 的时间复杂度。
• 缺点：
  • 非稳定性：不是稳定排序算法，相等元素相对顺序可能改变。
  • 空间开销：最坏情况下空间复杂度达 $O(n)$，对空间要求苛刻的场景不太适用。
• 代码示例：

def intro_sort_helper(arr, begin, end, depth_limit):
    if end - begin <= 16:
        insertion_sort(arr, begin, end)
        return
    if depth_limit == 0:
        heap_sort(arr, begin, end)
        return
    pivot_index = partition(arr, begin, end)
    intro_sort_helper(arr, begin, pivot_index, depth_limit - 1)
    intro_sort_helper(arr, pivot_index + 1, end, depth_limit - 1)


def intro_sort(arr):
    depth_limit = 2 * len(arr).bit_length()
    intro_sort_helper(arr, 0, len(arr), depth_limit)
    return arr


def insertion_sort(arr, left, right):
    for i in range(left + 1, right):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key


def heap_sort(arr, begin, end):
    n = end - begin
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i + begin)
    for i in range(n - 1, 0, -1):
        arr[begin + i], arr[begin] = arr[begin], arr[begin + i]
        heapify(arr, i, begin)


def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left + arr[0]] > arr[largest + arr[0]]:
        largest = left
    if right < n and arr[right + arr[0]] > arr[largest + arr[0]]:
        largest = right
    if largest != i:
        arr[i + arr[0]], arr[largest + arr[0]] = arr[largest + arr[0]], arr[i + arr[0]]
        heapify(arr, n, largest)


def partition(arr, begin, end):
    pivot = arr[end - 1]
    i = begin - 1
    for j in range(begin, end - 1):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[end - 1] = arr[end - 1], arr[i + 1]
    return i + 1


arr = [64, 34, 25, 12, 22, 11, 90]
print(intro_sort(arr))