当前位置：首页 > article >正文

各个排序算法基础速通万字介绍

article 2024/11/30 17:16:49

大家好，我是小黄。今天给大家分享的是各个排序算法。

1. 什么是排序算法

排序算法是一种用来将一组无序数据重新排列成有序序列的算法。排序后的数据可以按照升序或降序排列。

排序算法的特点

稳定性：排序算法是否保持相等元素的相对位置。
时间复杂度：算法运行所需的时间量。
空间复杂度：算法运行所需的额外内存。

2. 排序算法的分类

根据是否需要额外的空间，排序算法可以分为两大类：

内部排序：排序过程中数据存放在内存中完成。
外部排序：数据量过大，需要借助外部存储设备。

根据实现原理，排序算法又可分为：

比较排序：通过元素之间的比较实现排序（如冒泡排序、快速排序）。
非比较排序：不直接比较元素值，依赖特定条件（如计数排序、基数排序）。

3. 各类排序算法详解

3.1 冒泡排序（Bubble Sort）

基本思想：通过重复遍历序列，相邻的元素两两比较并交换，将较大的元素逐步移动到序列末尾。

算法步骤：

从头开始，比较相邻的两个元素，如果顺序错误则交换位置。
遍历完一轮后，最大的元素已经排到末尾。
重复上述过程，直到所有元素有序。

演示

初始数据：[1, 9, 6, 8, 7, 5, 4]

冒泡排序每次比较相邻的两个元素，将较大的元素向后交换。

第 1 轮：
- 比较 1 和 9，无需交换
- 比较 9 和 6，交换 → [1, 6, 9, 8, 7, 5, 4]
- 比较 9 和 8，交换 → [1, 6, 8, 9, 7, 5, 4]
- 比较 9 和 7，交换 → [1, 6, 8, 7, 9, 5, 4]
- 比较 9 和 5，交换 → [1, 6, 8, 7, 5, 9, 4]
- 比较 9 和 4，交换 → [1, 6, 8, 7, 5, 4, 9]
第 2 轮：
- 比较 1 和 6，无需交换
- 比较 6 和 8，无需交换
- 比较 8 和 7，交换 → [1, 6, 7, 8, 5, 4, 9]
- 比较 8 和 5，交换 → [1, 6, 7, 5, 8, 4, 9]
- 比较 8 和 4，交换 → [1, 6, 7, 5, 4, 8, 9]
第 3 轮：
- 比较 1 和 6，无需交换
- 比较 6 和 7，无需交换
- 比较 7 和 5，交换 → [1, 6, 5, 7, 4, 8, 9]
- 比较 7 和 4，交换 → [1, 6, 5, 4, 7, 8, 9]
第 4 轮：
- 比较 1 和 6，无需交换
- 比较 6 和 5，交换 → [1, 5, 6, 4, 7, 8, 9]
- 比较 6 和 4，交换 → [1, 5, 4, 6, 7, 8, 9]
第 5 轮：
- 比较 1 和 5，无需交换
- 比较 5 和 4，交换 → [1, 4, 5, 6, 7, 8, 9]
第 6 轮：
- 比较 1 和 4，无需交换

结果：[1, 4, 5, 6, 7, 8, 9]

代码实现：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 提前退出的标志
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # 如果没有发生交换，说明已排序
            break
    return arr

性能分析：

时间复杂度：O(n²)（最坏/平均），O(n)（最好，已排序）
空间复杂度：O(1)
稳定性：稳定

优化：通过标记是否发生交换，可以在数组已经有序时提前退出循环。

3.2 选择排序（Selection Sort）

基本思想：每次从未排序部分找到最小（或最大）元素，并将其放到已排序部分的末尾。

算法步骤：

从未排序部分中找出最小元素的索引。
将最小元素与未排序部分的第一个元素交换。
重复上述过程，直到所有元素有序。

演示

初始数据：[1, 9, 6, 8, 7, 5, 4]

选择排序每轮从未排序部分中找到最小值，放到前面。

第 1 轮：找到最小值 1，无需交换 → [1, 9, 6, 8, 7, 5, 4]
第 2 轮：找到最小值 4，与 9 交换 → [1, 4, 6, 8, 7, 5, 9]
第 3 轮：找到最小值 5，与 6 交换 → [1, 4, 5, 8, 7, 6, 9]
第 4 轮：找到最小值 6，与 8 交换 → [1, 4, 5, 6, 7, 8, 9]
第 5 轮：找到最小值 7，无需交换 → [1, 4, 5, 6, 7, 8, 9]
第 6 轮：找到最小值 8，无需交换 → [1, 4, 5, 6, 7, 8, 9]

结果：[1, 4, 5, 6, 7, 8, 9]

代码实现：

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

性能分析：

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定（交换可能打乱相同元素顺序）

3.3 插入排序（Insertion Sort）

基本思想：通过构建有序序列，将未排序元素逐一插入到已排序部分的适当位置。

算法步骤：

假设前面部分已经排序。
将未排序部分的第一个元素插入到已排序部分的适当位置。
重复上述过程，直到所有元素有序。

演示：

初始数据：[1, 9, 6, 8, 7, 5, 4]

插入排序每轮将当前元素插入到前面有序部分的合适位置。

第 1 轮：[1, 9, 6, 8, 7, 5, 4]（无需移动）
第 2 轮：[1, 6, 9, 8, 7, 5, 4]（6 插入到 1 后）
第 3 轮：[1, 6, 8, 9, 7, 5, 4]（8 插入到 6 和 9 之间）
第 4 轮：[1, 6, 7, 8, 9, 5, 4]（7 插入到 6 和 8 之间）
第 5 轮：[1, 5, 6, 7, 8, 9, 4]（5 插入到 1 后）
第 6 轮：[1, 4, 5, 6, 7, 8, 9]（4 插入到 1 后）

结果：[1, 4, 5, 6, 7, 8, 9]

代码实现：

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

性能分析：

时间复杂度：O(n²)（最坏/平均），O(n)（最好，已排序）
空间复杂度：O(1)
稳定性：稳定
3.4 希尔排序（Shell Sort）

基本思想：通过逐步缩小的增量分组，对每组应用插入排序，最终达到全局有序。

算法步骤：
选择一个增量序列（如 n/2, n/4, ..., 1）。
按增量划分子序列，对每个子序列进行插入排序。
缩小增量，重复上述步骤，直至增量为1。

演示

初始数据：[1, 9, 6, 8, 7, 5, 4]

希尔排序通过将数组分为多个子序列分别排序，然后逐步减少间隔直至最终排序完成。

第一轮（间隔为 3）：
- 子序列：[1, 8, 5] 和 [9, 7, 4]，分别排序后为 [1, 5, 8] 和 [4, 7, 9]
- 合并为 [1, 4, 5, 7, 8, 9]
第二轮（间隔为 1）：
- 按插入排序方式对整个数组排序

结果：[1, 4, 5, 6, 7, 8, 9]

代码

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

性能分析：

时间复杂度：取决于增量序列，最优可达 O(n log n)
空间复杂度：O(1)
稳定性：不稳定。

3.5 归并排序（Merge Sort）

基本思想：采用分治策略，将序列递归拆分，再合并排序后的子序列。

算法步骤：

将序列分成两部分，递归对子序列排序。
合并两个已排序的子序列。

演示：

初始数据：[1, 9, 6, 8, 7, 5, 4]

归并排序通过递归将数组不断分割成更小的子数组，然后合并已排序的子数组。

分割阶段：
- 将数组分成两部分：[1, 9, 6] 和 [8, 7, 5, 4]
- 继续分割：
  - [1, 9, 6] → [1] 和 [9, 6] → [9] 和 [6]
  - [8, 7, 5, 4] → [8, 7] 和 [5, 4] → [8] 和 [7]，[5] 和 [4]
合并阶段：
- [9] 和 [6] 合并为 [6, 9]
- [1] 和 [6, 9] 合并为 [1, 6, 9]
- [8] 和 [7] 合并为 [7, 8]
- [5] 和 [4] 合并为 [4, 5]
- [7, 8] 和 [4, 5] 合并为 [4, 5, 7, 8]
- [1, 6, 9] 和 [4, 5, 7, 8] 合并为 [1, 4, 5, 6, 7, 8, 9]

结果：[1, 4, 5, 6, 7, 8, 9]

代码实现：

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

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

性能分析：

时间复杂度：O(n log n)
空间复杂度：O(n)
稳定性：稳定。

3.6 快速排序（Quick Sort）

基本思想：快速排序基于分治思想，通过选择一个“基准”（pivot）将序列分为两部分，小于基准的在左，大于基准的在右，递归排序两部分。

算法步骤：

选择一个基准元素。
将序列重新排列：比基准小的放左边，比基准大的放右边。
对左右子序列递归执行上述步骤。

演示：

初始数据：[1, 9, 6, 8, 7, 5, 4]

快速排序选择 1 为基准：

左：[]，右：[9, 6, 8, 7, 5, 4]

对右部分递归：选择 9 为基准：

左：[6, 8, 7, 5, 4]，右：[]

对 [6, 8, 7, 5, 4] 递归，选择 6 为基准：

左：[5, 4]，右：[8, 7]

最终结果合并：
结果：[1, 4, 5, 6, 7, 8, 9]

代码实现：

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

性能分析：

时间复杂度：O(n log n)（平均），O(n²)（最坏，分割极不均匀）
空间复杂度：O(log n)（递归栈）
稳定性：不稳定

优化：

基准选择：随机选取基准或三数取中法可避免极端情况。
原地分区：减少空间消耗。

3.7 堆排序（Heap Sort）

基本思想：将序列构造成一个堆，反复将堆顶元素（最大或最小）移到序列末尾，调整堆以保持堆性质。

算法步骤：

构建最大堆（或最小堆）。
交换堆顶与末尾元素，缩小堆的范围。
调整剩余堆使其保持最大堆性质。

演示：

初始数据：[1, 9, 6, 8, 7, 5, 4]

堆排序通过构建一个大顶堆，然后逐步将堆顶元素与最后一个元素交换，再调整堆。

建堆阶段（构建大顶堆）：
- 初始堆：[1, 9, 6, 8, 7, 5, 4]
- 调整为堆：[9, 8, 6, 1, 7, 5, 4]
排序阶段：
- 第 1 步：交换堆顶和最后一个元素 → [4, 8, 6, 1, 7, 5, 9]，重新调整为堆 → [8, 7, 6, 1, 4, 5, 9]
- 第 2 步：交换堆顶和倒数第 2 个元素 → [5, 7, 6, 1, 4, 8, 9]，调整为堆 → [7, 5, 6, 1, 4, 8, 9]
- 第 3 步：交换堆顶和倒数第 3 个元素 → [4, 5, 6, 1, 7, 8, 9]，调整为堆 → [6, 5, 4, 1, 7, 8, 9]
- 第 4 步：交换堆顶和倒数第 4 个元素 → [1, 5, 4, 6, 7, 8, 9]，调整为堆 → [5, 1, 4, 6, 7, 8, 9]
- 第 5 步：交换堆顶和倒数第 5 个元素 → [4, 1, 5, 6, 7, 8, 9]，调整为堆 → [4, 1, 5, 6, 7, 8, 9]
- 第 6 步：交换堆顶和倒数第 6 个元素 → [1, 4, 5, 6, 7, 8, 9]

结果：[1, 4, 5, 6, 7, 8, 9]

代码实现：

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[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

性能分析：

时间复杂度：O(n log n)
空间复杂度：O(1)
稳定性：不稳定。

3.8 计数排序（Counting Sort）

基本思想：计数排序适用于整数范围较小的场景，通过统计每个元素出现的次数，直接构造有序序列。

算法步骤：

找到数据范围，初始化计数数组。
统计每个元素的出现次数。
通过累加计数数组计算元素的最终位置。
根据计数数组重建有序序列。

代码实现：

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i, c in enumerate(count):
        sorted_arr.extend([i] * c)
    return sorted_arr

性能分析：

时间复杂度：O(n + k)（k 为最大值与最小值的差）
空间复杂度：O(k)
稳定性：稳定

注意：计数排序对数据范围较大的情况不适用，可能导致内存浪费。

3.9 桶排序（Bucket Sort）

基本思想：将数据划分为多个区间（桶），每个桶内部再使用其他排序算法排序。

算法步骤：

初始化若干空桶。
将元素分配到对应的桶中。
对每个桶中的元素单独排序。
按顺序合并所有桶中的元素。

代码实现：

def bucket_sort(arr):
    if not arr:
        return []
    bucket_count = 10
    max_val, min_val = max(arr), min(arr)
    bucket_size = (max_val - min_val) / bucket_count
    buckets = [[] for _ in range(bucket_count)]
    for num in arr:
        index = int((num - min_val) / bucket_size)
        if index == bucket_count:  # 边界情况
            index -= 1
        buckets[index].append(num)
    for bucket in buckets:
        bucket.sort()  # 可改为其他排序算法
    return [num for bucket in buckets for num in bucket]

性能分析：

时间复杂度：O(n)（平均），取决于桶内排序算法
空间复杂度：O(n + k)（k 为桶数）
稳定性：稳定

3.10 基数排序（Radix Sort）

基本思想：基数排序通过逐位（从最低位到最高位或反之）对数据进行多次排序，实现全局有序。

算法步骤：

找到数据的最大位数。
按每个位数排序，从最低位到最高位。
每次排序使用稳定排序算法（如计数排序）。

演示：

初始数据：[1, 9, 6, 8, 7, 5, 4]

基数排序从个位到最高位依次排序。

个位排序：
- 根据个位数字分组：[1] [9] [6] [8] [7] [5] [4]
- 按顺序合并：[1, 4, 5, 6, 7, 8, 9]
十位排序（无变化）：
- 直接合并：[1, 4, 5, 6, 7, 8, 9]

结果：[1, 4, 5, 6, 7, 8, 9]

代码实现：

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    count = [0] * 10
    output = [0] * n
    for num in arr:
        index = (num // exp) % 10
        count[index] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
    return output

性能分析：

时间复杂度：O(nk)（k 为位数）
空间复杂度：O(n + k)
稳定性：稳定

4. 排序算法的比较与应用场景

算法	时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	O(n²)	O(1)	稳定	小数据量，简单实现
插入排序	O(n²)（最坏）	O(1)	稳定	少量元素，基本有序
快速排序	O(n log n)	O(log n)	不稳定	大数据量，通用性强
归并排序	O(n log n)	O(n)	稳定	数据分布随机或链表
堆排序	O(n log n)	O(1)	不稳定	要求空间效率的场景
计数排序	O(n + k)	O(k)	稳定	整数范围小的情况
桶排序	O(n)（平均）	O(n + k)	稳定	数据分布均匀的场景
基数排序	O(nk)	O(n + k)	稳定	数据位数较少的整数