排序算法：深度解析 & 代码实现

在计算机科学和算法领域中，排序算法是一项基础而重要的技术。无论是对数据进行升序排列、降序排列，还是按特定规则重新排列，排序算法都扮演着关键的角色。在本篇博客中，我们将深入探索排序算法，从简单的冒泡排序到高效的快速排序，逐步揭示不同排序算法的工作原理和应用场景。

算法概述

比较类排序

比较类排序通过比较元素间的大小来决定它们的相对次序。由于比较类排序的时间复杂度不能突破 $O(n \log_2 n)$ ，因此也被称为非线性时间比较类排序。常见的比较类排序算法包括：

交换排序（Exchange Sort）：通过不断比较相邻元素并交换位置，使得较大（或较小）的元素逐渐移动到正确的位置。
插入排序（Insertion Sort）：将当前元素插入已排序部分的合适位置，以构建最终有序序列。
选择排序（Selection Sort）：每次从未排序部分选择最小（或最大）元素插入已排序部分的末尾。
归并排序（Merge Sort）：通过将序列分成两个子序列，分别排序后再合并，实现递归地排序整个序列。

非比较类排序

非比较类排序不通过比较元素间的大小来决定它们的相对次序，因此能够突破 $O(n \log_2 n)$ 的时间下界，以线性时间运行。常见的非比较类排序算法包括：

计数排序（Counting Sort）：统计每个元素出现的次数，然后根据统计信息对元素进行排序，适用于非负整数的排序。
桶排序（Bucket Sort）：将元素分散到多个桶中，对每个桶中的元素进行排序，然后依次合并桶中的元素，适用于元素分布均匀的情况。
基数排序（Radix Sort）：按照低位先排序，然后收集；再按照高位排序，然后再收集，依次类推，直到最高位，通过分配和收集过程来实现排序，适用于整数的排序。

算法复杂度

排序方法	时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最好)	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
快速排序	$O(n \log_2 n)$	$O(n^2)$	$O(n \log_2 n)$	$O(n \log_2 n)$	不稳定
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(1)$	不稳定
归并排序	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(n)$	稳定

计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定
桶排序	$O(n+k)$	$O(n^2)$	$O(n)$	$O(n+k)$	稳定
基数排序	$O(n \cdot k)$	$O(n \cdot k)$	$O(n \cdot k)$	$O(n+k)$	稳定

比较类排序

一、交换排序

冒泡排序

冒泡排序是一种简单的比较排序算法，它重复地遍历要排序的列表，一次比较两个相邻的元素，并按照规定的顺序交换它们，直到没有任何一对元素需要交换为止，该列表就是有序的。

算法步骤

从列表的第一个元素开始，对相邻的两个元素进行比较。
如果前面的元素大于后面的元素，则交换它们的位置。
继续进行这样的比较和交换，直到到达列表的末尾。
重复以上步骤，每次都将最大的元素”冒泡”到列表的末尾。
不断缩小待排序列表的范围，直到整个列表都已经排序完毕。

动态图解

代码实现

def bubble_sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            # 如果前一个元素大于后一个元素，交换它们的位置
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

快速排序

快速排序是一种分治算法，通过递归地将数组分解为较小的子数组，然后按照某种规则对子数组进行排序，最终将整个数组排序完成。快速排序的核心思想是选择一个基准元素，将数组分为比基准元素小的部分和比基准元素大的部分，然后对这两部分分别进行递归排序。

算法步骤

选择一个基准元素（通常选择数组的第一个元素）。
将数组分为两部分，左边部分的元素小于等于基准元素，右边部分的元素大于基准元素。
对左右两部分分别进行递归排序。
递归的基本情况是数组的长度小于等于 1，此时数组已经有序。

动态图解

代码实现

def quick_sort(arr, left=None, right=None):
    # 如果 left 和 right 未指定，则默认为整个数组的范围
    left = 0 if not isinstance(left, (int, float)) else left
    right = len(arr) - 1 if not isinstance(right, (int, float)) else right
  
    if left < right:
        pivot = left
        index = pivot + 1
        item = index
        # 遍历数组，将小于基准值的元素放到基准值的左侧
        while item <= right:
            if arr[item] < arr[pivot]:
                arr[item], arr[index] = arr[index], arr[item]
                index += 1
            item += 1
        # 将基准值放到合适的位置
        arr[pivot], arr[index - 1] = arr[index - 1], arr[pivot]
  
        # 递归处理基准值左右侧的子数组
        quick_sort(arr, left, index - 2)
        quick_sort(arr, index, right)
  
    return arr

二、插入排序

简单插入排序

简单插入排序是一种基本的比较排序算法，它的思想是将未排序的元素逐个插入到已排序部分的合适位置，直到整个序列有序为止。

算法步骤

将列表分为两部分：已排序部分和未排序部分。开始时，已排序部分只包含第一个元素，未排序部分包含剩余的元素。
从未排序部分取出第一个元素，称为当前元素，将其插入到已排序部分的合适位置。
将当前元素与已排序部分的元素逐个比较，找到合适的插入位置。
插入当前元素后，将其余的已排序元素后移一位。
重复以上步骤，直到未排序部分为空，整个序列有序。

动态图解

代码实现

def insertion_sort(arr):
    for i in range(1, len(arr)):
        current = arr[i]
  
        # 寻找当前元素在已排序部分中的插入位置
        pre_index = i - 1
        while pre_index >= 0 and arr[pre_index] > current:
            # 向右移动已排序部分中比当前元素大的元素
            arr[pre_index + 1] = arr[pre_index]
            pre_index -= 1
  
        # 将当前元素插入到正确的位置
        arr[pre_index + 1] = current
  
    return arr

希尔排序

希尔排序是插入排序的一种改进版本，也称为缩小增量排序。它通过将数组分割成若干个子序列，对每个子序列进行插入排序，最终达到对整个数组进行排序的目的。希尔排序的关键在于选择增量序列，不同的增量序列会影响排序的效率。

算法步骤

选择一个增量序列 $\{h_1, h_2, ..., h_k\}$ ，并按照增量序列对数组进行分组。
对每个分组内的元素进行简单插入排序。
逐步缩小增量，重复以上步骤，直到增量为 1，完成排序。

动态图解

代码实现

def shell_sort(arr):
    gap = 1
  
    # 动态确定间隔序列的最大值
    while gap < len(arr) / 3:
        gap = gap * 3 + 1
  
    # 间隔序列逐渐缩小
    while gap > 0:
        # 对每个间隔内的元素进行插入排序
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > temp:
                arr[j + gap] = arr[j]
                j -= gap
            arr[j + gap] = temp
  
        # 缩小间隔序列
        gap = gap // 3
  
    return arr

三、选择排序

简单选择排序

简单选择排序是一种基本的比较排序算法，它的思想是每次从未排序的元素中选择最小（或最大）的元素，然后放到已排序部分的末尾。简单选择排序的核心是不断地选择未排序部分的最小（或最大）元素，并将其与未排序部分的第一个元素交换位置。

算法步骤

初始化一个指针，指向未排序部分的第一个元素。
从指针指向的位置开始，依次遍历未排序部分的元素，找到最小的元素。
将最小的元素与指针指向的元素交换位置。
移动指针到未排序部分的下一个位置，重复以上步骤，直到整个序列有序。

动态图解

代码实现

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_index = i
  
        # 内层循环找到未排序部分的最小值的索引
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
  
        # 如果最小值的索引发生变化，则交换当前位置元素与最小值元素的位置
        if i != min_index:
            arr[i], arr[min_index] = arr[min_index], arr[i]
  
    return arr

堆排序

堆排序是一种基于完全二叉树（堆）的排序算法。它利用了堆的特性：子结点的键值或索引总是小于（或者大于）它的父节点。堆排序的核心思想是将待排序的序列构建成一个大顶堆或小顶堆，然后依次将堆顶元素与末尾元素交换，并重新调整堆，直到整个序列有序。

算法步骤

将数组中的元素构建成一个大根堆或小根堆。
将根节点与最后一个叶子节点交换，然后重新调整堆的结构，确保堆仍然满足堆的特性。
重复步骤 2，直到堆中只剩下一个元素。

动态图解

代码实现

def heap_sort(arr):
    # 从最后一个非叶子节点开始，到根节点，依次进行堆化
    for start in range(len(arr) // 2 - 1, -1, -1):
        heapify(arr, start, len(arr))

    # 交换堆顶元素（最大值）与数组末尾元素，并重新堆化剩余的元素
    for end in range(len(arr) - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        heapify(arr, 0, end)
  
    return arr


def heapify(arr, parent_index, heap_size):
    largest = parent_index
    left_child = 2 * parent_index + 1
    right_child = 2 * parent_index + 2

    # 检查左子节点是否存在且是否大于当前最大值
    if left_child < heap_size and arr[largest] < arr[left_child]:
        largest = left_child

    # 检查右子节点是否存在且是否大于当前最大值
    if right_child < heap_size and arr[largest] < arr[right_child]:
        largest = right_child

    # 如果最大值不是当前父节点，则交换它们，并递归地对受影响的子树进行堆化
    if largest != parent_index:
        arr[parent_index], arr[largest] = arr[largest], arr[parent_index]
        heapify(arr, largest, heap_size)

四、归并排序

归并排序

归并排序是一种分治算法，它将待排序序列分成两个子序列，然后对每个子序列分别进行排序，最后将两个有序子序列合并成一个有序序列，也称为二路归并。归并排序的核心思想是递归地将序列分成更小的子序列，直到每个子序列只有一个元素，然后逐层合并子序列直到整个序列有序。

算法步骤

将待排序序列分成两个子序列，每个子序列包含原序列的一半元素。
递归地对每个子序列进行排序，直到每个子序列只有一个元素。
将排好序的子序列合并成一个有序序列。

动态图解

代码实现

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
  
    # 寻找中间分割点
    middle = len(arr) // 2
  
    # 递归地对左右两部分数组进行归并排序
    left = merge_sort(arr[:middle])
    right = merge_sort(arr[middle:])
  
    # 合并两个有序数组
    result = []
    # 比较左右两个数组的元素，将较小的元素加入结果中
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
  
    # 将剩余的元素加入结果中
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
  
    return result

非比较排序

计数排序

计数排序是一种非比较排序算法，它的核心思想是统计待排序序列中每个元素的出现次数，然后根据统计信息将元素放置到正确的位置上。计数排序的关键是要知道待排序序列中的元素取值范围，以便确定统计数组的大小。计数排序适用于待排序元素为整数且取值范围不是很大的情况。

算法步骤

统计每个元素的出现次数：遍历待排序序列，统计每个元素的出现次数，并存储在统计数组中。
计算每个元素的位置：根据统计数组，计算每个元素在排序后的序列中的起始位置。
根据每个元素的位置，将元素放置到正确的位置上。

动态图解

代码实现

def counting_sort(arr):
    if len(arr) <= 1:
        return arr

    # 确定待排序序列的最大值和最小值
    min_val, max_val = min(arr), max(arr)
    # 统计数组，用于存储每个元素的出现次数
    count = [0] * (max_val - min_val + 1)

    # 统计每个元素的出现次数
    for num in arr:
        count[num - min_val] += 1

    # 根据统计数组计算每个元素的位置
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # 进行排序
    result = [0] * len(arr)
    for num in reversed(arr):
        result[count[num - min_val] - 1] = num
        count[num - min_val] -= 1

    return result

桶排序

桶排序是一种分布排序算法，它将待排序序列分到有限数量的桶中，然后对每个桶单独进行排序，最后按照顺序合并每个桶的元素。桶排序的核心思想是利用映射函数将待排序序列的元素分布到各个桶中，然后对每个桶中的元素进行排序，最后将各个桶的元素按照顺序合并。

算法步骤

根据待排序序列中元素的分布情况，创建足够数量的桶。
遍历待排序序列，根据映射函数将每个元素分配到相应的桶中。
对每个桶中的元素进行排序，可以选择不同的排序算法。
将各个桶中的元素按照顺序合并成一个有序序列。

动态图解

代码实现

def bucket_sort(arr):
    if len(arr) <= 1:
        return arr
  
    bucket_size = 10
    buckets = [[] for _ in range(bucket_size)]
  
    max_val, min_val = max(arr), min(arr)
    bucket_range = (max_val - min_val) / bucket_size
  
    for num in arr:
        # 计算每个元素应该放到哪个桶中
        idx = min(bucket_size - 1, int((num - min_val) / bucket_range))
        buckets[idx].append(num)
  
    # 对每个桶中的元素进行排序
    for bucket in buckets:
        bucket.sort()
  
    # 合并桶中的元素
    result = [num for bucket in buckets for num in bucket]
  
    return result

基数排序

基数排序是一种非比较排序算法，它将整数按位数逐个比较，然后将整数按位数从小到大排序。基数排序适用于排序大量整数，因为它不需要比较整数的大小，只需要比较整数的位数即可。

算法步骤

确定待排序整数的最大位数。
从最低位开始，将整数按位数从小到大排序。
重复步骤 2，直到所有位数都已排序。

动态图解

代码实现

def radix_sort(arr):
    if len(arr) <= 1:
        return arr
  
    # 获取数组中最大数字的位数
    max_num = max(arr)
    k = len(str(max_num))
  
    # 根据位数进行循环
    for radix in range(k):
        bucket = [[] for _ in range(10)]
  
        # 将每个数字按照当前位上的数值放入对应的桶中
        for item in arr:
            num = (item % (10 ** (radix + 1))) // (10 ** radix)
            bucket[num].append(item)
  
        # 将桶中的数字按顺序取出，覆盖原数组
        arr = [j for i in bucket for j in i]
  
    return arr

拓展内容

珠排序

珠排序是一种自然排序算法，使用二维数组来模拟算盘，将无序的整数数组转换为二维数组，通过模拟算盘的珠子掉落过程来实现排序。

算法步骤

将输入数组转换为二维数组，其中每个元素代表算盘上的一列，每个元素的值为该列上的珠子个数。
对每一列进行遍历，将珠子从上方掉落到最底部，即将数组中的 1 向下移动，直至到达最底部。
将掉落后的二维数组转换为一维数组，每个元素的值即为该列下方珠子的个数。

5 | * * * * *            5 | *
3 | * * *                3 | * *
1 | *              ->    1 | * * *
2 | * *                  2 | * * * *
4 | * * * *              4 | * * * * *

代码实现

def bead_sort(arr):
    arr_up = [[0] * max(arr) for i in range(len(arr))]
    arr_down = [[0] * max(arr) for i in range(len(arr))]
  
    # 在上方算盘中放置珠子
    for i in range(len(arr)):
        for j in range(arr[i]):
            arr_up[i][j] = 1
  
    # 让珠子掉落到下方算盘
    for j in range(max(arr)):
        index = len(arr) - 1
        for i in range(len(arr)):
            if arr_up[i][j] == 1:
                arr_down[index][j] = 1
                index -= 1
  
    # 统计下方算盘每列的珠子数量，即排序后的结果
    for i in range(len(arr)):
        count = arr_down[i].count(1)
        arr[i] = count
  
    return arr

睡眠排序

睡眠排序是一种非常奇特的排序算法，它利用线程的睡眠来实现排序。对于待排序数组中的每个元素，都创建一个线程，并让线程睡眠一定的时间，时间长短与元素大小成正比。当线程醒来后，将对应的元素添加到排序结果中，最终得到有序的数组。

算法步骤

对于待排序数组中的每一个元素，开启一个线程，并设置睡眠时间为元素的值乘以一个固定的系数。
当这些线程陆续醒来时，睡眠时间短的线程先醒来，睡眠时间长的线程后醒来。
按照线程醒来的顺序，依次将对应的元素添加到新的数组或列表中。

代码实现

import time
import threading

def sleep_sort(arr):
    # 设置睡眠系数
    sleep_coefficient = 0.02
    thread_list, result = [], []
    for num in arr:
        # 创建线程，每个线程睡眠时间与元素大小成正比
        thread = threading.Thread(target=sleep, args=(num, result, sleep_coefficient))
        thread_list.append(thread)
  
    # 启动所有线程
    for thread in thread_list:
        thread.start()
  
    # 等待所有线程执行完毕
    for thread in thread_list:
        thread.join()
  
    return result

def sleep(num, sorted_arr, sleep_coefficient):
    # 线程睡眠时间与元素大小成正比
    time.sleep(num * sleep_coefficient)
    sorted_arr.append(num)

猴子排序

猴子排序，灵感来源于猴子与打字机的经典故事。在这个故事中，一只猴子随机地敲击打字机键盘，最终可以产生特定的文本，例如莎士比亚的全集。类似地，对于一个乱序的数组，猴子排序算法会随机打乱数组顺序，然后检查是否排好序。若数组已经排好序，则算法结束并输出结果；否则，再次随机打乱数组顺序，继续检查，直到数组被排好序。

算法步骤

随机打乱数组顺序。
检查数组是否已经排好序。若已排好序，则输出排序结果；否则，回到步骤 1。

代码实现

import random

def bogo_sort(arr):
    while True:
        flag = True
  
        # 随机打乱数组顺序
        random.shuffle(arr)
  
        # 检查数组是否已排序
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                flag = False
                break
  
        # 排序成功返回数组
        if flag:
            return arr

Kared

算法概述

比较类排序

非比较类排序

相关概念

算法复杂度

比较类排序

一、交换排序

冒泡排序

算法步骤

动态图解

代码实现

快速排序

算法步骤

动态图解

代码实现

二、插入排序

简单插入排序

算法步骤

动态图解

代码实现

希尔排序

算法步骤

动态图解

代码实现

三、选择排序

简单选择排序

算法步骤

动态图解

代码实现

堆排序

算法步骤

动态图解

代码实现

四、归并排序

归并排序

算法步骤

动态图解

代码实现

非比较排序

计数排序

算法步骤

动态图解

代码实现

桶排序

算法步骤

动态图解

代码实现

基数排序

算法步骤

动态图解

代码实现

拓展内容

珠排序

算法步骤

代码实现

睡眠排序

算法步骤

代码实现

猴子排序

算法步骤

代码实现