排序算法是计算机科学中最基础且重要的算法之一，本文详细介绍了十种常见的排序算法，包括原理、实现代码、优缺点、适用场景以及复杂度分析。

一、冒泡排序 (Bubble Sort)

算法原理

冒泡排序通过重复遍历数组，比较相邻元素并交换位置，使较大的元素逐渐"浮"到数组末端。每一轮遍历都会将当前未排序部分的最大值移动到正确位置。

第一轮排序：分别确定两个相邻数值，进行比较后确定是否交换，最后可确定排序最后一位。
剩余轮次排序和第一轮排序一样，但是范围不包括第n - i 位及之后的数值（之前的排序轮次已经确定这些数值的位置）。

示例演示：

初始数组: [5, 3, 8, 4, 2]
第1轮: [3, 5, 4, 2, 8]  // 8沉到底部
第2轮: [3, 4, 2, 5, 8]  // 5沉到倒数第二
第3轮: [3, 2, 4, 5, 8]  // 4沉到中间
第4轮: [2, 3, 4, 5, 8]  // 排序完成初始数组: [5, 3, 8, 4, 2]
第1轮: [3, 5, 4, 2, 8]  // 8沉到底部
第2轮: [3, 4, 2, 5, 8]  // 5沉到倒数第二
第3轮: [3, 2, 4, 5, 8]  // 4沉到中间
第4轮: [2, 3, 4, 5, 8]  // 排序完成

代码实现

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):  #表示排序的轮次，最多进行n轮排序，最少进行1轮
        is_swap = False   #表示是否在该轮次有交换操作
        for j in range(1,n-i):
            if arr[j] < arr[j-1]:  
                arr[j], arr[j-1] = arr[j-1],arr[j]
                is_swap = True
        if not is_swap:  #如果没有交换，表示排序结束
            return arr

特点分析

优点：实现简单，代码易于理解；对于基本有序的数组效率较高；稳定排序（相等元素相对位置不变）；原地排序（空间复杂度O(1)）

缺点：效率较低，时间复杂度为O(n²)；不适用于大规模数据排序

时间复杂度：最优：O(n) - 数组已经有序时； 平均：O(n²)； 最差：O(n²)

空间复杂度：O(1)

适用范围：小规模数据、教学演示、基本有序的数据

二、插入排序 (Insertion Sort)

算法原理

插入排序将数组分为已排序和未排序两部分，初始时首个元素分到已排序部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置。

示例演示：

初始数组: [5, 3, 8, 4, 2]
步骤1: [5| 3, 8, 4, 2]  // 5已排序
步骤2: [3, 5| 8, 4, 2]  // 3插入到5前面
步骤3: [3, 5, 8| 4, 2]  // 8插入到末尾
步骤4: [3, 4, 5, 8| 2]  // 4插入到5前面
步骤5: [2, 3, 4, 5, 8]  // 2插入到最前面

代码实现

def insertion_sort(arr):
    n = len(arr)
    for i in range(1,n):
        tmp = arr[i]  #确定遍及到的该元素，防止后续因数组的改变而改变该元素
        j = i - 1
        while arr[j] > tmp and j >= 0:
            #从后向前遍历已排序元素，若大于tmp ，后移一位，否则将tmp插入到该元素后面
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = tmp
    return arr

特点分析

优点：实现简单，对小规模数据效率高；对基本有序的数组效率很高；稳定排序；原地排序

缺点：大规模数据效率低；每次只能移动一个位置

时间复杂度：最优：O(n) - 数组已经有序时； 平均：O(n²)； 最差：O(n²)

空间复杂度：O(1)

适用范围：小规模数据、基本有序的数据、作为其他排序算法的子过程

三、归并排序 (Merge Sort)

算法原理

归并排序采用分治策略，将数组递归地分成两半，直到每组只剩一个元素，分别排序后再合并。这是一个典型的"分而治之"算法。

示例演示：

原始数组: [38, 27, 43, 3, 9, 82, 10]
分解过程:
[38, 27, 43, 3]  [9, 82, 10]
[38, 27] [43, 3]  [9, 82] [10]
[38] [27] [43] [3] [9] [82] [10]

合并过程:
[27, 38] [3, 43]  [9, 82] [10]
[3, 27, 38, 43]  [9, 10, 82]
[3, 9, 10, 27, 38, 43, 82]

代码实现

def merge_sort(arr):
    n = len(arr)
    if n <= 1: return arr
    
    #递归地对半分，直到子数组长度小于等于1
    mid = n // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    #回溯时，两两合并有序数组
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res.extend(left[i:])  #剩余结果直接加入list
    res.extend(right[j:])

    return res

特点分析

优点：时间复杂度稳定为O(nlogn)；稳定排序；适合处理大规模数据；适合外部排序（数据在磁盘中）

缺点：需要额外空间；对于小规模数据可能不如插入排序

时间复杂度：O(nlogn)

空间复杂度：O(n)

适用范围：大规模数据、需要稳定排序的场景、链表排序

四、快速排序 (Quick Sort)

算法原理

快速排序选择一个基准元素，将数组分成两部分：小于基准的和大于基准的，然后递归地对这两部分进行排序，直到子数组只剩一个元素的位置。

示例演示：

原始数组: [5, 3, 8, 4, 2]
选择基准5:
小于5: [3, 4, 2]  大于5: [8]
递归排序[3, 4, 2]:
选择基准3: 小于3: [2]  大于3: [4]
合并: [2, 3, 4, 5, 8]

代码实现（三种方法）

#1 递归+双指针1
def quick_sort1(arr,low,high):
    ##1、递归终止条件（子数组长度小于等于1）
    if high - low <= 0: return  #该函数是原地修改，无需返回值

    ##2、选定基准值，将小/大于基准值的数值交换到基准值的前/后面
    pivot = arr[low]
    left, right = low, high
    ## 用双指针left、right分别从数组两端向中心遍历寻找大于/小于基准值的元素，
    ## 找到后交换彼此位置，然后继续遍历，直到双指针相遇，将基准值放在相遇点
    while left < right:
        while left < right and arr[right] >= pivot:
            right -= 1
        arr[left] = arr[right]
        while left < right and arr[left] < pivot:
            left += 1
        arr[right] = arr[left]
    arr[left] = pivot

    ##3、递归地对基准值两侧的子数组执行上述操作
    quick_sort1(arr,low,left-1)
    quick_sort1(arr,left+1,high)


#2 递归+双指针2
def quick_sort2(arr,low,high):
    ## 1、递归终止条件（子数组长度小于等于1）
    if high - low <= 0: return

    ##2、选定基准值，将小/大于基准值的元素挪到基准值的左/右侧
    ## 注意：为了便于后续操作，如果选择其他值作为基准值，需要将其与arr[high]交换位置，
    pivot = arr[high]
    
    ## 使用双指针i、j将小于基准值的元素挪到位置 i 及之前，大于等于基准值的元素在i之后，
    ## 遍历结束后，将基准值放在 i+1 处，原i+1处的值放在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]

    ##3、递归地对基准值两侧的子数组执行上述操作，直到递归终止
    quick_sort2(arr,low,i)
    quick_sort2(arr,i+2,high)
    

#3 栈+双指针
def quick_sort3(arr):
    satck = [(0,len(arr) - 1)]
    while satck:
        ##1、获取子数组端点索引
        low, high = satck.pop()

        ##2、子数组长度小于等于1，无需改动，跳过
        if high - low <= 0:
            continue

        ##3、选定基准值，将小/大于基准值的元素分别挪到基准值的左/右侧
        pivot = arr[high]

        ## 将小于基准值的元素挪到位置 i 及其之前，大于等于基准值的元素在i之后，
        ## 遍历结束后，将基准值放在 i+1 处，将原i+1处的值放在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]

        ##4、将基准值两侧的子数组端点索引加入栈中
        stack.append((low,i))
        satck.append((i+2,high))

特点分析

优点：平均情况下效率很高；原地排序；在实践中通常是最快的排序算法

缺点：最坏情况下性能较差；不稳定排序；递归深度可能很大

时间复杂度：最优：O(nlogn)； 平均：O(nlogn)； 最差：O(n²) - 数组已经有序且选择最值作为基准时

空间复杂度：O(logn) - 递归栈空间

适用范围：通用排序、大规模数据、对性能要求高的场景

五、选择排序 (Selection Sort)

算法原理

选择排序每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾，直到未排序数组为空。

示例演示：

初始数组: [64, 25, 12, 22, 11]
第1轮: [11, 25, 12, 22, 64]  // 11最小
第2轮: [11, 12, 25, 22, 64]  // 12最小
第3轮: [11, 12, 22, 25, 64]  // 22最小
第4轮: [11, 12, 22, 25, 64]  // 已完成

代码实现

def select_sort(arr):
    ## 遍历数组，每轮将未排序部分的最小值交换到其首位
    n = len(arr)
    for i in range(n-1):  # i指向未排序部分的首位
        min_idx = i  # 用于记录未排序部分最小值的索引
        for j in range(i+1,n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i],arr[min_idx] = arr[min_idx],arr[i]  # 将最小值移到未排序部分首位
    return arr

特点分析

优点：实现简单；不占用额外内存；交换次数少，最多n-1次交换

缺点：时间复杂度高；不稳定排序；无论输入数据如何都需要O(n²)次比较

时间复杂度：O(n²)

空间复杂度：O(1)

适用范围：小规模数据、交换成本较高的场景

六、堆排序 (Heap Sort)

算法原理

堆排序利用堆这种数据结构，首先构建大顶堆，然后反复将堆顶元素（最大值）与末尾元素交换，并重新调整堆，重复上述步骤，直到堆中只剩一个元素。

大顶堆：每个节点值大于等于其子节点值，用于堆排序中的升序：

key[i]>=key[2i+1]；key[i]>=key[2i+2]；

小顶堆：每个节点值小于等于其子节点值，用于堆排序中的降序：

key[i]<=key[2i+1]，key[i]<=key[2i+2];

示例演示：

初始数组: [4, 10, 3, 5, 1]
构建大顶堆: [10, 5, 3, 4, 1]
交换堆顶和末尾: [1, 5, 3, 4, 10]
调整堆: [5, 4, 3, 1, 10]
继续交换和调整...
最终结果: [1, 3, 4, 5, 10]

代码实现

def heapify(arr,i,end):  # 用于维护大顶堆
    ## 从第i个元素所在节点开始，向下比较，保证每个节点值大于其子节点值
    dad = i
    son = 2 * dad + 1
    while son < end:
        if son+1 < end and arr[son+1] > arr[son]:
            son += 1
        if arr[son] <= arr[dad]:  # 如果父节点本身就大于等于子节点值，无需再向下操作
            break
        arr[dad],arr[son] = arr[son],arr[dad]  # 否则交换二者的值
        dad = son  # 继续向下操作
        son = 2 * dad + 1

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

    ## 初始化大顶堆（从最后一个非叶子节点开始构建，保证每个节点值大于等于其子节点值）
    for i in range(n//2,-1,-1):
        heapify(arr,i,n)

    ## 每轮取出堆顶元素，将其与数组未排序部分的末尾元素交换位置
    ## 维护新的大顶堆
    for i in range(n-1,0,-1):
        arr[0],arr[i] = arr[i],arr[0]
        heapify(arr,0,i)  # i位置及其之后是排好序的，所以end=i

特点分析

优点：时间复杂度稳定；原地排序；适合获取前k个最大/最小元素

缺点：不稳定排序；缓存不友好；常数因子较大

时间复杂度：O(nlogn)

空间复杂度：O(1)

适用范围：需要稳定时间复杂度的场景、实时系统、获取前k个元素

七、希尔排序 (Shell Sort)

算法原理

希尔排序是插入排序的改进版，通过比较相距一定间隔的元素来进行排序，逐步缩小间隔直到为1。

示例演示：

初始数组: [8, 3, 6, 1, 7, 2, 5, 4]
间隔为4: [7, 2, 5, 1, 8, 3, 6, 4]
间隔为2: [5, 1, 6, 2, 7, 3, 8, 4]
间隔为1: [1, 2, 3, 4, 5, 6, 7, 8]

代码实现

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

特点分析

优点：比简单插入排序快很多；原地排序；是插入排序的高效改进版

缺点：不稳定排序；时间复杂度分析复杂；性能依赖于间隔序列的选择

时间复杂度：最优：O(nlogn)； 平均：O(n^1.3)； 最差：O(n²)

空间复杂度：O(1)

适用范围：中等规模数据、需要比插入排序更高效的场景

八、计数排序 (Counting Sort)

算法原理

计数排序不是基于比较的排序，它通过统计每个元素出现的次数，然后计算每个元素在输出数组中的位置。

示例演示：

输入数组: [4, 2, 2, 8, 3, 3, 1]
计数数组: [0, 1, 2, 2, 1, 0, 0, 0, 1]
累加数组: [0, 1, 3, 5, 6, 6, 6, 6, 7]
输出数组: [1, 2, 2, 3, 3, 4, 8]

代码实现

#1、非稳定
def counting_sort1(arr):
    n = len(arr)
    max_vel, min_vel = max(arr), min(arr)  # 找出数组的最大值和最小值
    counter = [0] * (max_vel - min_vel + 1)  # 定义计数器数组，长度为数组元素的范围
    for i in arr:  # 用counter数组统计每个元素出现的次数，索引为元素值-最小值
        counter[i-min_vel] += 1

    # 遍历counter数组，根据每个元素出现的次数，将其依次添加到原数组中
    k = 0
    for i in range(max_vel-min_vel+1):
        for j in range(counter[i]):
            arr[k] = i + min_vel
            k += 1
    return arr

a = [23,34,15,22,16]
print('八、1',counting_sort1(a))

#2、稳定
def counting_sort2(arr):
    # 只计算数组最大值，最小值默认为0，建立计数数组
    m = max(arr)
    counter = [0] * (m+1)
    for a in arr:
        counter[a] += 1
    # 计算累加和，此时counter[i-1]代表的是i元素在排序后的数组存放的最后一个位置（同一元素可能存在多个）
    for i in range(1, m+1):
        counter[i] += counter[i-1]
    # 建立一个与原数组同size的数组res，倒序遍历原数组，将每个元素根据上述所说放入适当的位置
    n = len(arr)
    res = [0] * n
    for i in range(n-1, -1, -1):
        a = arr[i]
        res[counter[a]-1] = a
        # counter[i-1]代表的是i元素在排序后的数组存放的最后一个位置（同一元素可能存在多个）
        counter[a] -= 1
        # 当放了一个元素后，该元素对应的counter值要减一，对应该元素下次出现时的位置
    # 将排序后的数组放回原数组
    for i in range(n):
        arr[i] = res[i]
    return arr

特点分析

优点：线性时间复杂度;当k较小时效率很高

缺点：需要额外空间;只适用于整数排序;当数据范围很大时效率低

时间复杂度：O(n+k) - k是数据范围

空间复杂度：O(k)

适用范围：数据范围较小的整数排序、作为基数排序的子过程

九、桶排序 (Bucket Sort)

算法原理

桶排序将数据分到有限数量的桶中，每个桶再分别排序，最后合并所有桶。

示例演示：

输入数组: [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
分桶:
桶1[0.3-0.4]: [0.32, 0.33, 0.37]
桶2[0.4-0.5]: [0.42, 0.47]
桶3[0.5-0.6]: [0.52, 0.51]
各桶排序后合并: [0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52]

代码实现

def bucket_sort(arr):
    n = len(arr)
    min_val,max_val = min(arr), max(arr)  # 找出最大值、最小值
    bucketsize = 2  #定义桶的大小
    bucketnum = (max_val - min_val) // bucketsize + 1  #计算桶的数量
    buckets = [[] for _ in range(bucketnum)]  #定义桶的数组

    for i in arr:   #将元素放入对应桶中
        b_idx = (i - min_val) // bucketsize  #计算元素
        buckets[b_idx].append(i)

    for i in range(bucketnum):
        buckets[i].sort()

    k = 0
    for tmp in buckets:
        for j in tmp:
            arr[k] = j
            k += 1
    return arr

特点分析

优点：在数据分布均匀时效率很高;稳定排序（如果桶内排序使用稳定算法）;适合外部排序

缺点：需要额外空间;性能依赖于数据分布;需要知道数据范围

时间复杂度：最优：O(n+k); 平均：O(n+k); 最差：O(n²) - 所有数据在一个桶中

空间复杂度：O(n+k)

适用范围：数据分布均匀的场景、外部排序、浮点数排序

十、基数排序 (Radix Sort)

算法原理

基数排序按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

示例演示：

输入数组: [170, 45, 75, 90, 2, 802, 24, 66]
按个位排序: [170, 90, 2, 802, 24, 45, 75, 66]
按十位排序: [2, 802, 24, 45, 66, 170, 75, 90]
按百位排序: [2, 24, 45, 66, 75, 90, 170, 802]

代码实现

def counting_sort_digit(arr,exp,n):
    counter = [0] * 10   #定义计数器数组，长度为10
    output = [0] * 10   #定义输出数组，长度为n
    for i in arr:   #用counter数组统计每个元素的第exp位数出现的次数
        idx = (i // exp) % 10  #计算元素的第exp位数
        counter[idx] += 1
    for i in range(1,10):
        #计算累加和，此时counter[i-1]代表的是i元素在排序后的数组存放的最后一个位置
        counter[i] += counter[i-1]
    i = n - 1
    while i >=0:   #倒序遍历原数组，将每个元素根据上述所说放入适当的位置
        idx = (arr[i] // exp) % 10
        output[counter[idx] - 1] = arr[i]
        counter[idx] -= 1
        i -= 1
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    n = len(arr)
    max_val = max(arr)
    exp = 1  #定义基数
    while max_val // exp > 0:  #基数排序的次数
        counting_sort_digit(arr,exp,n)
        exp *= 10   #基数翻倍
    return arr

特点分析

优点：线性时间复杂度;稳定排序;适合整数和字符串排序

缺点：需要额外空间;只适用于有限长度的数据;对于浮点数需要特殊处理

时间复杂度：O(d×(n+k)) - d是最大位数，k是基数

空间复杂度：O(n+k)

适用范围：整数排序、字符串排序、数据位数较少的场景

总结

选择建议：

• 小规模数据：插入排序、冒泡排序

• 通用排序：快速排序

• 需要稳定排序：归并排序

• 大规模数据：归并排序、快速排序

• 整数排序：计数排序、基数排序

• 内存受限：堆排序、希尔排序

每种排序算法都有其特定的适用场景，在实际应用中应根据数据特点、性能要求和资源限制来选择合适的算法。

本文代码均实现升序排序，降序排序请自行根据原理进行修改。