四大经典排序算法：选择、插入、希尔、基数排序原理与实现

选择排序原理与实现

选择排序（Selection Sort）通过不断选择剩余元素中的最小值来完成排序。其核心思想是将序列分为已排序和未排序两部分，每次从未排序部分选出最小元素放到已排序末尾。

时间复杂度分析：

• 最优/平均/最坏时间复杂度均为O(n²)
• 空间复杂度O(1)

Python实现示例：

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        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

# 测试不同情况
print(selection_sort([64, 25, 12, 22, 11]))  # 常规数组
print(selection_sort([5, 1, 2, 2, 3, 4]))    # 含重复元素
print(selection_sort([1]))                   # 单元素

工程实践要点：

1. 适用于内存空间有限场景
2. 数据交换次数固定为n-1次
3. 不稳定排序（可通过记录索引改为稳定）

插入排序深度解析

插入排序（Insertion Sort）采用类似整理扑克牌的方式，将每个新元素插入到已排序序列的合适位置。

算法步骤分解：

1. 从第二个元素开始遍历
2. 将当前元素与前面元素逐个比较
3. 找到合适位置后插入

性能优化策略：

• 二分查找插入位置（优化比较次数）
• 链表实现（优化移动次数）
• 哨兵机制减少边界判断

优化版Python实现：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        # 二分查找优化
        low, high = 0, i-1
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] < key:
                low = mid + 1
            else:
                high = mid - 1
        # 移动元素
        while j >= low:
            arr[j+1] = arr[j]
            j -= 1
        arr[low] = key
    return arr

# 测试大规模数据
import random
test_case = random.sample(range(1, 10000), 500)
assert insertion_sort(test_case) == sorted(test_case)

希尔排序进阶研究

希尔排序（Shell Sort）是插入排序的改进版，通过分组插入排序实现高效处理。

核心参数选择：

• 增量序列设计（Hibbard、Sedgewick等）
• 初始步长设置
• 分组策略优化

Sedgewick增量序列实现：

def shell_sort(arr):
    n = len(arr)
    # Sedgewick增量序列生成
    gaps = []
    k = 0
    while True:
        gap = 9*(4**k) - 9*(2**k) + 1
        if gap > n:
            break
        gaps.append(gap)
        gap = 4**(k+2) - 3*2**(k+2) + 1
        if gap > n:
            break
        gaps.append(gap)
        k += 1
    
    for gap in reversed(gaps):
        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
    return arr

# 性能对比测试
import timeit
setup = '''
from __main__ import shell_sort, insertion_sort
import random
arr = random.sample(range(1, 100000), 10000)
'''
print("希尔排序耗时:", timeit.timeit('shell_sort(arr.copy())', setup=setup, number=1))
print("插入排序耗时:", timeit.timeit('insertion_sort(arr.copy())', setup=setup, number=1))

基数排序工程实践

基数排序（Radix Sort）按位进行排序，支持稳定高效的数字排序。

关键技术细节：

1. 基数选择（10进制/256进制）
2. 负数处理（偏移量转换）
3. 内存使用优化

支持负数的优化实现：

def radix_sort(arr):
    # 处理负数
    min_val = min(arr)
    offset = -min_val if min_val < 0 else 0
    arr = [num + offset for num in arr]
    
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    
    # 还原原始数据
    return [num - offset for num in arr]

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i-1]

    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index]-1] = arr[i]
        count[index] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

# 测试含负数的用例
print(radix_sort([-5, 123, 0, 456, -789, 42, -314159]))

实际应用场景：

• 电话号码排序
• IP地址排序
• 大规模整数排序
• 需要稳定排序的场合

四维性能对比

从四个维度对算法进行综合评估：

指标	选择排序	插入排序	希尔排序	基数排序
平均时间复杂度	O(n²)	O(n²)	O(n^1.5)	O(nk)
空间复杂度	O(1)	O(1)	O(1)	O(n+k)
稳定性	不稳定	稳定	不稳定	稳定
适用数据规模	小规模	小规模	中等规模	大规模
最佳适用场景	内存敏感	基本有序	通用排序	整数排序

场景选择建议：

1. 内存严格受限时优先选择选择排序
2. 处理基本有序数据使用插入排序
3. 通用中等规模数据采用希尔排序
4. 大规模整数排序首选基数排序