排序算法专题|7种核心排序算法集合(Python版)

def bublesort(a):    n = len(a)    # 外层循环：控制排序轮次，共n-1轮（最后一个元素无需比较）    for i in range(n-1):        # 内层循环：每轮遍历未排序部分，相邻元素比较交换        # 每轮结束后，最大元素已沉到末尾，无需再比较        for j in range(n-i-1):            # 若前一个元素大于后一个，交换位置（冒泡核心）            if a[j] > a[j+1]:                a[j], a[j+1] = a[j+1], a[j]    return a

def insertsort(a):    n = len(a)    # 外层循环：从第2个元素开始（第1个元素默认有序），遍历无序区    for i in range(1, n):        key = a[i]  # 取出当前要插入的元素（无序区第一个元素）        j = i - 1   # 有序区的最后一个元素索引        # 内层循环：在有序区中找到插入位置，将大于key的元素后移        while j >= 0 and a[j] > key:            a[j+1] = a[j]  # 元素后移，腾出插入位置            j -= 1        a[j+1] = key  # 将key插入到正确位置    return a

def selectsort(a):    n = len(a)    # 外层循环：控制有序区范围，共n-1轮（最后一个元素无需选择）    for i in range(n-1):        index = i  # 初始化最小元素索引为无序区第一个元素        # 内层循环：遍历无序区，找到最小元素的索引        for j in range(i+1, n):            if a[j] < a[index]:                index = j  # 更新最小元素索引        # 将最小元素与无序区第一个元素交换        a[i], a[index] = a[index], a[i]    return a

def countsort(a):    n = len(a)    if n == 0:  # 处理空数组边界情况        return a    max_v = max(a)  # 找到数组中的最大值，确定计数数组长度    res = [0] * (max_v + 1)  # 计数数组，存储每个元素出现次数    for num in a:  # 修正原代码nums为a，避免变量名错误        res[num] += 1    tmp = []  # 存储最终有序数组    # 遍历计数数组，按元素大小依次加入结果    for i, r in enumerate(res):        while r > 0:            tmp.append(i)            r -= 1    return tmp

def mergesort(a):    # 辅助函数：递归拆分+合并    def merge_sort_(a, res, start, end):        if start >= end:  # 递归终止条件：子数组长度为1（已有序）            return        # 分：将数组拆分为左右两个子数组，分别递归排序        mid = (start + end) // 2        merge_sort_(a, res, start, mid)        merge_sort_(a, res, mid + 1, end)        # 合：将两个有序子数组合并为一个有序数组        i, j, k = start, mid+1, start  # i左子数组指针，j右子数组指针，k结果指针        while i <= mid and j <= end:            # 比较左右子数组元素，将较小值存入结果数组            if a[i] <= a[j]:                res[k] = a[i]                i += 1            else:                res[k] = a[j]                j += 1            k += 1        # 将左子数组剩余元素存入结果        while i <= mid:            res[k] = a[i]            i += 1            k += 1        # 将右子数组剩余元素存入结果        while j <= end:            res[k] = a[j]            j += 1            k += 1        # 将结果数组的值复制回原数组（完成当前区间排序）        for k in range(start, end + 1):              a[k] = res[k]    n = len(a)    if n == 0:        return a    res = [0] * n  # 辅助结果数组，存储合并后的有序数据    merge_sort_(a, res, 0, n-1)    return a

def quicksort(a):    # 辅助函数：分区操作，返回基准元素的最终位置    def partition(nums, left, right):        pivot = nums[left]  # 选择左边界元素作为基准        # 双指针交换，将小于基准的元素移到左边，大于等于的移到右边        while left < right:            # 从右往左找，找到第一个小于基准的元素            while left < right and nums[right] >= pivot:                right -= 1            nums[left] = nums[right]  # 移到左指针位置            # 从左往右找，找到第一个大于基准的元素            while left < right and nums[left] <= pivot:                left += 1            nums[right] = nums[left]  # 移到右指针位置        nums[left] = pivot  # 将基准元素放到最终位置        return left  # 返回基准元素索引    # 辅助函数：递归排序    def sort_(nums, left, right):        if left >= right:  # 递归终止条件：子数组长度<=1            return        mid = partition(nums, left, right)  # 分区，得到基准位置        sort_(nums, left, mid-1)  # 递归排序左半部分        sort_(nums, mid+1, right)  # 递归排序右半部分    if len(a) == 0:        return a    sort_(a, 0, len(a)-1)    return a

def heap_sort(arr):    arr_copy = arr.copy()  # 复制数组，避免修改原数组    n = len(arr_copy)    if n <= 1:        return arr_copy    # 第一步：构建大顶堆（从最后一个非叶子节点开始调整）    for i in range(n // 2 - 1, -1, -1):        adjust_heap(arr_copy, i, n)    # 第二步：逐个交换堆顶元素和末尾元素，然后调整剩余堆    for j in range(n - 1, 0, -1):        # 交换堆顶（最大值）和当前未排序部分的最后一个元素        arr_copy[0], arr_copy[j] = arr_copy[j], arr_copy[0]        # 对剩余未排序部分（0到j-1）重新调整为大顶堆        adjust_heap(arr_copy, 0, j)    return arr_copy# 辅助函数：调整堆结构，使当前父节点满足大顶堆特性（父节点>子节点）def adjust_heap(arr, parent_idx, heap_size):    # 保存父节点值（用于后续赋值，避免多次交换）    temp = arr[parent_idx]    # 左子节点索引（完全二叉树特性：左子节点=2*父节点+1，右子节点=2*父节点+2）    child_idx = 2 * parent_idx + 1    # 循环遍历子节点，找到最大的子节点，完成堆调整    while child_idx < heap_size:        # 如果右子节点存在，且右子节点值 > 左子节点值，切换到右子节点        if child_idx + 1 < heap_size and arr[child_idx] < arr[child_idx + 1]:            child_idx += 1        # 如果子节点值 > 父节点值，将子节点值赋值给父节点（无需交换，先覆盖）        if arr[child_idx] > temp:            arr[parent_idx] = arr[child_idx]            # 父节点索引更新为当前子节点索引，继续向下调整            parent_idx = child_idx            child_idx = 2 * parent_idx + 1        else:            # 父节点值 ≥ 子节点值，无需调整，退出循环            break    # 将最初保存的父节点值赋值到最终位置    arr[parent_idx] = temp

def part_sort(array):    if len(array) <= 1:  # 数组长度<=1，本身有序        return [-1, -1]    max_v = float('-inf')  # 记录左到右遍历的最大值    min_v = float('inf')   # 记录无序区间的最小值    start = -1             # 无序区间左边界    end = -1               # 无序区间右边界    # 第一步：从左到右遍历，找无序区间的右边界end，同时记录无序区间的最小值min_v    for i, value in enumerate(array):        if max_v < value:            max_v = value  # 更新当前最大值（处于有序区间）        if max_v > value:            end = i        # 出现比当前最大值小的元素，更新右边界            if min_v > value:                min_v = value  # 更新无序区间的最小值    # 第二步：从左到右遍历，找无序区间的左边界start（第一个大于min_v的元素）    for i, value in enumerate(array):        if min_v < value:            start = i            break    # 若start仍为-1，说明数组有序（min_v未更新，即无无序元素）    return [start, end] if start != -1 else [-1, -1]