排序算法概述排序算法是将一组数据按照特定顺序如升序或降序重新排列的算法。根据时间复杂度、空间复杂度、稳定性等特性排序算法可分为比较排序和非比较排序两大类。常见算法包括冒泡排序、快速排序、归并排序、堆排序、计数排序等。比较排序算法冒泡排序Bubble Sort通过重复比较相邻元素并交换位置将最大或最小元素逐步“冒泡”到数组末端。时间复杂度平均和最坏情况为 (O(n^2))最好情况已排序为 (O(n))。空间复杂度(O(1))原地排序。稳定性稳定。代码示例def bubble_sort(arr): n len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] arr[j1]: arr[j], arr[j1] arr[j1], arr[j]快速排序Quick Sort基于分治思想通过选取基准值pivot将数组分为两部分递归排序子数组。时间复杂度平均为 (O(n \log n))最坏已排序为 (O(n^2))。空间复杂度(O(\log n))递归栈。稳定性不稳定。代码示例def quick_sort(arr): if len(arr) 1: return arr pivot arr[len(arr)//2] left [x for x in arr if x pivot] middle [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort(left) middle quick_sort(right)归并排序Merge Sort分治算法的典型应用将数组分为两半递归排序后合并。时间复杂度始终为 (O(n \log n))。空间复杂度(O(n))需额外空间合并。稳定性稳定。代码示例def merge_sort(arr): if len(arr) 1: mid len(arr)//2 L, R arr[:mid], arr[mid:] merge_sort(L) merge_sort(R) i j k 0 while i len(L) and j len(R): if L[i] R[j]: arr[k] L[i] i 1 else: arr[k] R[j] j 1 k 1 arr[k:] L[i:] or R[j:]非比较排序算法计数排序Counting Sort适用于整数数据通过统计元素出现次数实现排序。时间复杂度(O(n k))(k) 为数据范围。空间复杂度(O(k))。稳定性稳定。代码示例def counting_sort(arr): max_val max(arr) count [0] * (max_val 1) for num in arr: count[num] 1 sorted_arr [] for i in range(len(count)): sorted_arr.extend([i] * count[i]) return sorted_arr桶排序Bucket Sort将数据分到有限数量的桶中对每个桶单独排序后合并。时间复杂度平均 (O(n k))最坏 (O(n^2))。空间复杂度(O(n k))。适用场景数据均匀分布。高级排序算法堆排序Heap Sort利用二叉堆大顶堆或小顶堆的性质进行排序。时间复杂度始终 (O(n \log n))。空间复杂度(O(1))。稳定性不稳定。代码示例def heapify(arr, n, i): largest i l, r 2*i1, 2*i2 if l n and arr[l] arr[largest]: largest l if r n and arr[r] arr[largest]: largest r if largest ! i: arr[i], arr[largest] arr[largest], arr[i] heapify(arr, n, largest) def heap_sort(arr): n len(arr) for i in range(n//2-1, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): arr[0], arr[i] arr[i], arr[0] heapify(arr, i, 0)算法选择建议小规模数据冒泡排序或插入排序简单且稳定。大规模随机数据快速排序平均性能最优。需稳定性且数据量大归并排序。整数且范围有限计数排序或桶排序。通过理解算法原理和实际场景需求可以高效选择排序策略。https://github.com/ry-cp/eyl_w4jxhttps://github.com/ry-cp/eyl_w4jx/blob/main/README.mdhttps://raw.githubusercontent.com/ry-cp/eyl_w4jx/main/README.mdhttps://github.com/stewartsevaxy/juu_htlshttps://github.com/stewartsevaxy/juu_htls/blob/main/README.md