✨ 八大排序算法详解 ②

def selection_sort(arr):
    """
    简单选择排序（升序）
    :param arr: 待排序数组（列表）
    :return: 排序后的数组（不修改原数组）
    """
    arr_copy = arr.copy()
    n = len(arr_copy)
    # 外层循环：控制待排序区间的起始位置（0 ~ n-2）
    for i in range(n - 1):
        min_idx = i  # 初始化最小值索引为待排序区间第一个元素
        # 内层循环：遍历待排序区间，找到最小值索引
        for j in range(i + 1, n):
            if arr_copy[j] < arr_copy[min_idx]:
                min_idx = j
        # 交换最小值与待排序区间第一个元素
        arr_copy[i], arr_copy[min_idx] = arr_copy[min_idx], arr_copy[i]
    return arr_copy

# 优化版：二元选择排序（同时找最小/最大值，减少循环次数）
def selection_sort_optimized(arr):
    arr_copy = arr.copy()
    n = len(arr_copy)
    left = 0
    right = n - 1
    while left < right:
        min_idx = left
        max_idx = right
        # 一次遍历同时找最小、最大值索引
        for j in range(left, right + 1):
            if arr_copy[j] < arr_copy[min_idx]:
                min_idx = j
            if arr_copy[j] > arr_copy[max_idx]:
                max_idx = j
        # 交换最小值到左边界
        arr_copy[left], arr_copy[min_idx] = arr_copy[min_idx], arr_copy[left]
        # 若最大值索引是左边界（已被交换），更新最大值索引
        if max_idx == left:
            max_idx = min_idx
        # 交换最大值到右边界
        arr_copy[right], arr_copy[max_idx] = arr_copy[max_idx], arr_copy[right]
        # 缩小待排序区间
        left += 1
        right -= 1
    return arr_copy

# 测试用例
if __name__ == "__main__":
    test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
    res1 = selection_sort(test_arr)
    res2 = selection_sort_optimized(test_arr)
    print("原始数组：", test_arr)
    print("基础版排序后：", res1)  # [13, 27, 38, 49, 49, 65, 76, 97]
    print("优化版排序后：", res2)  # [13, 27, 38, 49, 49, 65, 76, 97]

def heap_sort(arr):
    """
    堆排序（升序，基于大顶堆）
    :param arr: 待排序数组（列表）
    :return: 排序后的数组（不修改原数组）
    """
    arr_copy = arr.copy()
    n = len(arr_copy)

    def sift_down(arr, start, end):
        """
        堆调整函数（下沉）：将以start为根的子树调整为大顶堆
        :param start: 子树根节点索引
        :param end: 堆的最后一个元素索引
        """
        root = start
        while True:
            # 左子节点索引
            child = 2 * root + 1
            # 子节点超出堆范围则退出
            if child > end:
                break
            # 选择左右子节点中较大的那个
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child += 1
            # 若根节点 < 子节点，交换并继续下沉
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                break

    # 1. 构建大顶堆（从最后一个非叶子节点开始调整）
    # 最后一个非叶子节点索引：n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr_copy, i, n - 1)

    # 2. 交换堆顶与末尾，调整堆结构
    for end in range(n - 1, 0, -1):
        arr_copy[0], arr_copy[end] = arr_copy[end], arr_copy[0]
        sift_down(arr_copy, 0, end - 1)

    return arr_copy

# 测试用例
if __name__ == "__main__":
    test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
    result = heap_sort(test_arr)
    print("原始数组：", test_arr)
    print("堆排序后：", result)  # [13, 27, 38, 49, 49, 65, 76, 97]

def merge_sort(arr):
    """
    归并排序（递归实现，升序）
    :param arr: 待排序数组（列表）
    :return: 排序后的数组（不修改原数组）
    """
    # 基线条件：子数组长度≤1时直接返回
    if len(arr) <= 1:
        return arr.copy()
    
    # 1. 拆分：找到中间索引，拆分为左右子数组
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # 2. 合并：双指针合并两个有序子数组
    def merge(left_arr, right_arr):
        merged = []
        i = j = 0
        # 双指针遍历，取较小值加入结果
        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i] <= right_arr[j]:
                merged.append(left_arr[i])
                i += 1
            else:
                merged.append(right_arr[j])
                j += 1
        # 追加剩余元素（左/右子数组可能有未遍历完的元素）
        merged.extend(left_arr[i:])
        merged.extend(right_arr[j:])
        return merged
    
    return merge(left, right)

# 测试用例
if __name__ == "__main__":
    test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
    result = merge_sort(test_arr)
    print("原始数组：", test_arr)
    print("归并排序后：", result)  # [13, 27, 38, 49, 49, 65, 76, 97]

def radix_sort(arr):
    """
    基数排序（LSD策略，仅处理非负整数）
    :param arr: 待排序数组（列表）
    :return: 排序后的数组（不修改原数组）
    """
    if not arr:
        return []
    arr_copy = arr.copy()
    # 找到最大数，确定需要处理的位数
    max_num = max(arr_copy)
    digit = 1  # 当前处理的位数（个位=1，十位=10，百位=100...）
    
    while max_num // digit > 0:
        # 初始化10个桶（0~9）
        buckets = [[] for _ in range(10)]
        # 1. 分配：按当前位数字放入对应桶
        for num in arr_copy:
            # 获取当前位的数字
            current_digit = (num // digit) % 10
            buckets[current_digit].append(num)
        # 2. 收集：按桶顺序合并元素
        arr_copy = []
        for bucket in buckets:
            arr_copy.extend(bucket)
        # 处理下一位
        digit *= 10
    return arr_copy

# 扩展：处理负数的基数排序
def radix_sort_with_negative(arr):
    if not arr:
        return []
    # 分离正负数，分别排序后合并
    negatives = [-x for x in arr if x < 0]
    positives = [x for x in arr if x >= 0]
    # 对负数的绝对值排序后反转，恢复负数顺序
    sorted_negatives = [-x for x in reversed(radix_sort(negatives))]
    sorted_positives = radix_sort(positives)
    return sorted_negatives + sorted_positives

# 测试用例
if __name__ == "__main__":
    test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
    result1 = radix_sort(test_arr)
    print("非负基数排序后：", result1)  # [13, 27, 38, 49, 49, 65, 76, 97]
    
    test_arr2 = [49, -38, 65, -97, 76, 13, -27, 49]
    result2 = radix_sort_with_negative(test_arr2)
    print("支持负数排序后：", result2)  # [-97, -38, -27, 13, 49, 49, 65, 76]