1. 从“排序”说起为什么算法是程序员的必修课如果你写过代码哪怕只是写过一个简单的学生成绩管理系统你大概率都遇到过“排序”这个问题。把成绩从高到低排列把商品按价格从低到高展示把日志按时间先后顺序列出……排序是计算机科学中最基础、最频繁的操作之一没有之一。它就像木匠的锯子、厨师的菜刀是每个程序员工具箱里最趁手的工具。但工具和工具之间差别可太大了。你用一把钝刀切肉费时费力还切不整齐用一把好刀手起刀落干净利落。排序算法也是如此。选择不同的排序算法程序的性能可能天差地别。处理100条数据你用哪种算法可能都感觉不到差别但处理100万条、1000万条数据时一个糟糕的排序算法能让你的程序卡死而一个高效的算法可能只需要几秒钟。这就是学习排序算法的核心价值在正确的场景下选择正确的工具用最高效的方式解决问题。这不仅仅是应付考试或者面试这是写出高性能、高可用代码的基本功。今天我们就来彻底拆解数据结构与算法课程中公认的“十大经典排序算法”不堆砌概念只讲实战中你会遇到什么、该怎么选、以及为什么。2. 排序算法的“性能护照”时间复杂度与空间复杂度在深入每个算法之前我们必须先统一语言理解如何评价一个算法的好坏。这就好比买车要看油耗、百公里加速和空间排序算法我们主要看两个核心指标时间复杂度和空间复杂度。时间复杂度通俗讲就是“算法执行需要花费的时间”随着数据量增长的变化趋势。我们通常用大O符号O来表示。它不是精确的秒数而是一个增长级别的描述。比如O(n²)意味着如果数据量n翻倍运行时间大概会变成原来的4倍O(n log n)则意味着数据量翻倍时间增加比翻倍多一点但远少于4倍。这是衡量算法效率的最关键指标。空间复杂度指的是算法运行过程中除了原始数据外需要额外占用多少内存空间。有的算法“原地”排序几乎不需要额外空间空间复杂度O(1)有的则需要开辟和原数组一样大的新数组来辅助空间复杂度O(n)。在内存受限的嵌入式环境或处理海量数据时空间复杂度就变得至关重要。此外我们还会关注算法的稳定性。如果一个排序算法在排序后能够保持相等元素的原始相对顺序我们就称它是稳定的。例如有一组学生记录先按姓名排序再按分数排序。如果第二次排序是稳定的那么同分数的学生之间依然会保持按姓名排列的顺序。这在多关键字排序时非常有用。为了方便后续对比我先给出这十大算法的核心性能概览你可以把它当作一个速查表算法名称平均时间复杂度最坏时间复杂度空间复杂度是否稳定核心思想简述冒泡排序O(n²)O(n²)O(1)稳定相邻元素两两比较大的下沉。选择排序O(n²)O(n²)O(1)不稳定每次从未排序部分选出最小大元素放到已排序末尾。插入排序O(n²)O(n²)O(1)稳定将未排序元素逐个插入到已排序序列的合适位置。希尔排序O(n log n) ~ O(n²)O(n²)O(1)不稳定改进的插入排序先进行大步长的跳跃式分组排序。归并排序O(n log n)O(n log n)O(n)稳定“分治”思想先递归拆分再合并有序子序列。快速排序O(n log n)O(n²)O(log n) ~ O(n)不稳定“分治”思想选取基准分区递归排序左右。堆排序O(n log n)O(n log n)O(1)不稳定利用“堆”这种数据结构进行选择排序。计数排序O(n k)O(n k)O(n k)稳定非比较排序统计每个值出现的次数。桶排序O(n k)O(n²)O(n k)稳定将数据分到有限数量的桶里每个桶单独排序。基数排序O(n * k)O(n * k)O(n k)稳定非比较排序按位个、十、百…进行分配收集。注表中k代表数据的范围计数排序、桶的数量桶排序或最大数字的位数基数排序。有了这张“性能护照”我们就能理解每个算法的基本定位。接下来我们把这些算法分成三大类逐一深入剖析初出茅庐的简单排序O(n²)、中流砥柱的高效排序O(n log n)和剑走偏锋的非比较排序O(n)。3. 初出茅庐理解排序本质的O(n²)算法这类算法思想直观代码简单是理解排序逻辑的绝佳起点。虽然它们处理大数据时力不从心但在特定小场景下仍有其用武之地。3.1 冒泡排序最直观的“水中气泡”模拟想象一下水底的气泡大的气泡会更快地上浮到水面。冒泡排序就是这个过程的数字化模拟。它重复地遍历要排序的数列一次比较两个相邻元素如果它们的顺序错误就把它们交换过来。遍历数列的工作重复进行直到没有再需要交换的元素也就是说该数列已经排序完成。核心操作相邻比较与交换。代码要点Python示例def bubble_sort(arr): n len(arr) for i in range(n-1): # 控制排序趟数 swapped False # 优化记录本轮是否发生交换 for j in range(0, n-1-i): # 每趟比较范围逐渐缩小 if arr[j] arr[j1]: arr[j], arr[j1] arr[j1], arr[j] swapped True if not swapped: # 如果一趟下来没交换说明已有序提前结束 break return arr为什么是O(n²)两层嵌套循环最坏情况下数组完全逆序需要比较 (n-1) (n-2) … 1 n(n-1)/2 次所以是 O(n²)。实战心得几乎用不到这是实话。除了教学和极少数对代码简洁性要求极高、且数据量极小的场景现代开发中基本不会主动使用冒泡排序。优化点上面的代码加入了swapped标志位进行优化。如果某一趟遍历没有发生任何交换说明数组已经有序可以提前终止。这对于近乎有序的输入数据有奇效。稳定性因为只有相邻元素且相等时不交换所以是稳定的。3.2 选择排序每次找到“最值”的简单策略选择排序的思路非常“人类”在未排序序列中找到最小或最大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。核心操作扫描寻找最值与目标位置交换。代码要点def selection_sort(arr): n len(arr) for i in range(n): min_idx i # 假设当前位置是最小值 for j in range(i1, n): # 在未排序部分寻找真正的最小值 if arr[j] arr[min_idx]: min_idx j arr[i], arr[min_idx] arr[min_idx], arr[i] # 交换 return arr为什么不稳定这是面试常考点。考虑数组[5, 8, 5, 2, 9]。第一轮找到最小元素2与第一个位置的5交换。数组变成[2, 8, 5, 5, 9]。注意原本在前面的那个5索引0被交换到了后面索引2它和另一个5索引2原索引3的相对顺序被破坏了。所以选择排序是不稳定的。实战心得交换次数少选择排序每轮只交换一次元素对于交换成本很高的场景比如要排序的不是数字而是大型对象交换操作涉及大量内存拷贝选择排序比冒泡排序有优势。依然很慢时间复杂度依然是 O(n²)大数据量下不可用。3.3 插入排序整理扑克牌的智慧这可能是最符合人类直觉的排序方法。想象你手里拿着一把乱序的扑克牌你会一张一张拿起把它插入到手中已整理好的牌堆中的正确位置。插入排序就是如此将数组分为“已排序”和“未排序”两部分初始时已排序部分只有一个元素。然后依次将未排序部分的元素插入到已排序部分的正确位置。核心操作寻找插入位置移动元素。代码要点def insertion_sort(arr): for i in range(1, len(arr)): # 从第二个元素开始第一个元素视为已排序 key arr[i] # 当前待插入的元素 j i - 1 # 从后向前扫描已排序部分寻找key的插入位置并后移元素 while j 0 and key arr[j]: arr[j 1] arr[j] j - 1 arr[j 1] key # 插入key return arr为什么在近乎有序的数据上表现极佳插入排序的内层循环while循环本质是“寻找插入位置并移动元素”。如果数组已经接近有序那么对于大多数元素key arr[j]的条件很快会失败因为key本来就该在当前位置附近内层循环几乎立刻结束。在最优情况完全有序下它的时间复杂度是 O(n)。而冒泡和选择排序即使面对有序数组依然要进行 O(n²) 级别的比较。实战心得小数据量的王者当数据量很小比如 n 50时插入排序的常数因子很小实际运行速度往往比那些 O(n log n) 的“高级”算法还要快。因此像Python内置的list.sort()或sorted()以及许多快速排序、归并排序的库实现在递归到小数组时会切换成插入排序来优化性能。在线排序插入排序支持“在线”处理。如果数据是逐个到来的流式数据你可以用插入排序随时维护一个有序序列而其他排序算法通常需要所有数据到位后才能开始。3.4 希尔排序插入排序的威力增强版希尔排序是插入排序的改进由Donald Shell提出。它通过一个称为“增量序列”的东西让元素进行大步长的跳跃式移动从而让数组在早期就变得“大致有序”最后再用步长为1的插入排序即标准的插入排序收尾。由于早期的长步长移动消除了大量的逆序对使得最后的插入排序工作量大大减少。核心思想定义增量序列如gap n//2, n//4, ..., 1。对于每个gap将数组看作由gap个交错子数组组成分别对这些子数组进行插入排序。随着gap减小数组越来越有序当gap1时就是一次标准的插入排序此时数组已基本有序所以效率很高。代码要点使用希尔原始序列def shell_sort(arr): n len(arr) gap n // 2 # 初始增量 while gap 0: 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 gap // 2 # 缩小增量 return arr时间复杂度为什么难以分析希尔排序的性能严重依赖于增量序列的选择。希尔原始序列n/2, n/4, ...最坏情况仍是 O(n²)但实际应用中表现优于 O(n²)。更优的序列如Hibbard序列、Sedgewick序列可以将最坏复杂度降到 O(n^(3/2)) 甚至 O(n log² n)。它是一个在实践中表现优秀但理论分析复杂的算法。实战心得中等数据量的实用选择对于数据量不大几千到几万且对稳定性无要求的情况希尔排序是简单排序算法中非常好的选择代码不复杂速度比插入排序快得多。增量序列是关键如果你决定使用希尔排序花点时间研究并选择一个好的增量序列是值得的性能提升可能非常显著。4. 中流砥柱应对海量数据的O(n log n)算法当数据量上来后O(n²) 的算法就力不从心了。这时就需要时间复杂度为 O(n log n) 的“高级”算法登场。它们都采用了“分治”或类似的思想将大问题分解为小问题来解决。4.1 归并排序稳定可靠的“分治”典范归并排序完美体现了“分治”思想分解、解决、合并。分解递归地将当前数组平均分割成两半。解决递归地对两个子数组进行归并排序直到子数组长度为1自然有序。合并将两个已经有序的子数组合并成一个大的有序数组。核心操作合并两个有序数组。这是归并排序的灵魂也是一个非常基础的编程技巧。代码要点递归版def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: # 注意这里用 保证了稳定性 result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result为什么时间复杂度是 O(n log n)可以画出一棵递归树。每一层递归都需要遍历所有元素进行合并操作每层的工作量是 O(n)。而递归树的高度是 log₂n因为每次对半分割。所以总时间复杂度是 O(n log n)。这是一个非常稳定的性能无论输入数据是正序、逆序还是乱序它都是 O(n log n)。空间复杂度 O(n) 的代价归并排序在合并过程中需要额外的空间来存储临时数组。这是它最大的缺点。在内存紧张的环境下需要谨慎使用。实战心得外部排序的基石归并排序是“外部排序”的核心算法。当数据量大到内存放不下时可以先将数据分成若干块每块在内存中排序后写回磁盘然后再用归并排序的思路多路归并这些有序块。数据库的排序、大数据框架中的排序都离不开它。稳定性优势归并排序是稳定的 O(n log n) 算法之一另一个是后面提到的基数/桶排序。这在多关键字排序或需要保持原始相对顺序的场景下是刚需。递归的深度对于极大规模数据递归调用可能导致栈溢出。可以使用自底向上的迭代版归并排序来避免这个问题。4.2 快速排序平均性能最快的“王者”快速排序同样采用“分治”但策略与归并不同它选择一个元素作为“基准”pivot然后重新排列数组使得所有比基准值小的元素摆放在基准前面所有比基准值大的元素摆在基准后面相同的数可以到任一边。在这个分区退出之后该基准就处于数组的中间位置。这个过程称为分区操作。然后递归地对基准左右两边的子数组进行快速排序。核心操作分区Partition。这是快排的灵魂有多种实现方式如Lomuto分区、Hoare分区。代码要点递归版使用Lomuto分区def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) # pi是基准的最终位置 quick_sort(arr, low, pi - 1) quick_sort(arr, pi 1, high) def partition(arr, low, high): pivot arr[high] # 选择最右元素作为基准 i low - 1 # 指向小于pivot区域的最后一个元素 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] return i 1为什么平均是 O(n log n)最坏是 O(n²)在理想情况下每次分区都能将数组均匀分成两半递归树高度为 log n每层分区操作总计 O(n)所以是 O(n log n)。最坏情况发生在每次选择的基准都是当前子数组的最大或最小值比如数组已经有序且总是选最后一个元素作基准导致分区极度不平衡递归树退化成链表高度为 n从而退化为 O(n²)。如何避免最坏情况关键在基准的选择。常用优化策略随机化随机选择基准元素。三数取中取子数组头、尾、中间三个元素的中位数作为基准。 这些策略能极大降低遇到最坏情况的概率使得快排在实践中几乎总是表现出 O(n log n) 的性能。空间复杂度 O(log n)递归调用栈的深度平均为 O(log n)。但最坏情况下已有序数组糟糕的基准选择会达到 O(n)。实战心得内置排序的常客许多编程语言的标准库排序函数如C的qsortC的std::sortJava的Arrays.sort对基本类型都基于快速排序或其变体如内省排序IntroSort因为它的平均常数因子很小速度极快。原地排序标准的快速排序是原地排序空间消耗小这对缓存友好也是它快的原因之一。不稳定排序在分区过程中相等元素的相对位置可能被打乱。小数组优化同插入排序一样当递归到小数组时比如长度10切换成插入排序可以进一步提升性能。4.3 堆排序利用“堆”数据结构的智慧堆排序巧妙地将数组抽象成一棵“完全二叉树”并利用“堆”这种数据结构的性质进行排序。堆是一种特殊的完全二叉树其中每个节点的值都大于等于或小于等于其子节点的值前者称为大顶堆后者称为小顶堆。堆排序的步骤分为两大阶段建堆将无序数组构建成一个大顶堆。排序反复将堆顶元素最大值与堆的末尾元素交换然后缩小堆的范围并对新的堆顶元素进行“下沉”操作以重新满足堆的性质。重复此过程直到堆的大小为1。核心操作“下沉”Heapify。给定一个节点如果它不满足堆的性质就将其与较大的子节点交换并递归地对交换后的子树进行“下沉”。代码要点def heapify(arr, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest ! i: arr[i], arr[largest] arr[largest], arr[i] heapify(arr, n, largest) def heap_sort(arr): n len(arr) # 1. 构建大顶堆 (从最后一个非叶子节点开始) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # 2. 逐个提取元素 for i in range(n-1, 0, -1): arr[0], arr[i] arr[i], arr[0] # 将堆顶最大值交换到末尾 heapify(arr, i, 0) # 对剩余元素重新建堆 return arr时间复杂度稳定在 O(n log n)建堆过程的时间复杂度是 O(n)这是一个很有趣的结论可以通过数学推导证明。排序阶段需要进行 n-1 次交换和堆调整每次调整是 O(log n)所以总时间是 O(n log n)。并且无论输入数据如何堆排序都能保证这个性能没有快排那样的最坏情况。空间复杂度 O(1)堆排序是原地排序只需要常数级别的额外空间。实战心得适合对最值敏感的场景堆结构本身非常适合动态获取最大值或最小值。所以堆排序的衍生价值在于如果你需要在一个动态数据流中实时获取前K个最大/最小值那么维护一个大小为K的堆是最高效的方法而不是对整个数据集进行完整的堆排序。缓存不友好堆排序的访问模式是跳跃式的沿着二叉树父子节点访问这对CPU缓存不友好因此其常数因子通常比快速排序和归并排序大实际运行速度可能稍慢。不稳定排序在建堆和交换的过程中相等元素的顺序可能被打乱。5. 剑走偏锋特定场景下的线性时间复杂度算法前面所有算法都是基于“比较”的排序它们的时间复杂度下界是 O(n log n)。但有一类算法另辟蹊径它们不比较元素的大小而是利用数据本身的特性如整数范围、位数在特定条件下可以达到 O(n) 的线性时间复杂度。但它们对输入数据有严格要求。5.1 计数排序统计频率的极致简单计数排序要求输入的数据必须是有确定范围的整数。它的核心思想是统计每个整数在数组中出现的次数然后根据计数结果直接输出排序后的数组。工作原理找出待排序数组中的最大值max和最小值min。创建一个长度为max - min 1的计数数组count初始化为0。遍历原数组统计每个元素出现的次数存入count数组count[arr[i] - min]。对count数组进行前缀和操作。此时count[i]表示小于等于i min的元素个数。从后向前遍历原数组为了保证稳定性根据count数组确定每个元素在输出数组中的位置放入结果数组并将对应计数减一。代码要点def counting_sort(arr): if not arr: return [] min_val, max_val min(arr), max(arr) size max_val - min_val 1 count [0] * size output [0] * len(arr) # 统计频率 for num in arr: count[num - min_val] 1 # 计算前缀和此时count[i]表示值imin的元素个数 for i in range(1, size): count[i] count[i-1] # 从后向前遍历原数组保证稳定性 for i in range(len(arr)-1, -1, -1): output[count[arr[i] - min_val] - 1] arr[i] count[arr[i] - min_val] - 1 return output时间复杂度 O(n k)其中 n 是数组长度k 是数据范围max - min 1。当 k 不是很大比如给年龄排序k~100时效率远高于基于比较的排序。实战心得数据范围是关键如果数据范围 k 远大于数据量 n比如对[1, 1000000]两个数排序那么计数排序的效率反而很低因为要创建巨大的计数数组。只能用于整数因为计数数组的索引必须是整数。对于浮点数或字符串需要先进行离散化处理。稳定性的实现上面代码中从后向前遍历原数组是保证稳定性的关键一步。如果不需要稳定性可以从前向后遍历并直接根据计数输出但会失去稳定性。5.2 桶排序化整为零分而治之桶排序是计数排序的推广。它假设输入数据均匀分布在一个范围内然后将该范围划分为若干个大小相同的子区间称为“桶”。遍历输入数据将每个数据放入对应的桶中。然后对每个非空的桶单独进行排序可以使用其他排序算法如插入排序。最后按顺序遍历所有桶将桶中的元素依次取出即得到有序序列。工作原理设置一个定量的数组当作空桶。遍历输入数据把每个元素映射到对应的桶中。对每个非空桶进行排序。从非空桶里把元素拼接起来。代码要点简易版def bucket_sort(arr, bucket_size5): if not arr: return [] min_val, max_val min(arr), max(arr) # 计算桶的数量 bucket_count (max_val - min_val) // bucket_size 1 buckets [[] for _ in range(bucket_count)] # 将数据分配到各个桶中 for num in arr: buckets[(num - min_val) // bucket_size].append(num) # 对每个桶排序并收集结果 sorted_arr [] for bucket in buckets: sorted_arr.extend(sorted(bucket)) # 这里用了内置排序也可用插入排序 return sorted_arr时间复杂度取决于桶内排序算法理想情况下数据均匀分布每个桶内元素数量接近如果用 O(n log n) 算法排序每个桶总时间接近 O(n n log(n/k))当 k 接近 n 时接近 O(n)。最坏情况是所有数据集中在一个桶里退化为单个桶的排序复杂度取决于桶内排序算法。实战心得适用于外部排序当数据量太大内存放不下时桶排序的思路非常有用。可以将数据分到多个文件桶中每个文件在内存中排序后再归并起来。均匀分布假设桶排序的性能依赖于数据是否均匀分布。如果数据集中会导致多数数据落入少数桶中失去优势。桶的数量和大小需要根据数据分布情况合理设置这是一个需要经验或试探的参数。5.3 基数排序按位分配的巧妙思路基数排序是一种非比较的整数排序算法它根据键值的每位数字来分配和收集元素。可以从最低位个位开始排序LSD最低位优先也可以从最高位开始MSD最高位优先。这里以LSD为例。工作原理LSD取得数组中的最大数并取得其位数max_digit。从最低位个位开始依次根据该位数字0-9将元素分配到10个桶中。按顺序0号桶到9号桶收集桶中的元素形成新的数组。针对十位、百位...重复步骤2和3直到最高位。代码要点def radix_sort(arr): if not arr: return [] max_val max(arr) exp 1 # 从个位开始 while max_val // exp 0: # 使用计数排序作为子排序稳定 counting_sort_by_digit(arr, exp) exp * 10 return arr def counting_sort_by_digit(arr, exp): n len(arr) output [0] * n count [0] * 10 # 0-9十个数字 # 统计当前位数字的出现次数 for i in range(n): index (arr[i] // exp) % 10 count[index] 1 # 计算前缀和 for i in range(1, 10): count[i] count[i-1] # 从后向前构建输出数组保证稳定性 for i in range(n-1, -1, -1): index (arr[i] // exp) % 10 output[count[index] - 1] arr[i] count[index] - 1 # 将排序好的数组拷贝回原数组 for i in range(n): arr[i] output[i]时间复杂度 O(n * k)其中 n 是数组长度k 是最大数字的位数。由于整数位数 k 通常很小所以效率可以接近 O(n)。实战心得只能用于整数或可分解为整数的元素如字符串按字符ASCII码、日期等。稳定排序基数排序的每一轮子排序通常是计数排序都必须是稳定的否则最终结果会错误。LSD vs MSDLSD从低位开始实现简单且不需要递归。MSD从高位开始更像是一种递归的分治策略有时可以提前结束某些分支但实现稍复杂。6. 实战选型指南没有最好的只有最合适的学完了所有算法面对具体问题该如何选择记住这个决策流程数据量有多大极小n 50插入排序。常数因子小代码简单且对近乎有序数据友好。很多高级排序库的底层优化就是它。中等50 n 1000希尔排序或快速排序简单版。如果对稳定性有要求考虑归并排序。巨大n 1000快速排序优化版如三数取中、归并排序或堆排序。快速排序平均最快归并排序稳定且性能恒定堆排序空间占用最小且无最坏情况。数据有什么特点基本有序插入排序或冒泡排序带优化标志有奇效。但如果是大规模基本有序归并排序和快速排序随机化基准依然表现良好。取值范围有限的整数优先考虑计数排序或基数排序。如果范围很小计数排序是线性时间碾压一切比较排序。数据均匀分布可以尝试桶排序尤其适合外部排序。需要动态获取最值考虑堆排序的思路或者直接使用堆数据结构。有什么额外约束稳定性要求如果相等元素的顺序必须保留选择插入排序、归并排序、计数排序、桶排序或基数排序。快速排序和堆排序不稳定。空间限制内存紧张时选择原地排序算法插入排序、希尔排序、堆排序、快速排序。避免归并排序需要O(n)额外空间和计数/桶/基数排序需要额外空间。链表存储对于链表归并排序是天然的最佳选择因为它主要涉及指针操作且不需要随机访问。插入排序在链表上实现也很方便。快速排序和堆排序在链表上效率很低。一个简单的决策矩阵场景推荐算法关键理由通用场景追求平均速度快速排序优化后平均O(n log n)常数因子小原地排序需要稳定排序且数据量大归并排序稳定性能恒为O(n log n)空间极度受限堆排序O(1)空间且保证O(n log n)数据量小或基本有序插入排序实现简单小数据或有序数据下效率高数据为小范围整数计数排序O(nk)线性时间简单高效数据为多位数整数基数排序O(n*k)稳定适用于整数、字符串链表结构排序归并排序适合顺序访问稳定高效最后也是最重要的心得在绝大多数日常开发中直接使用你所用编程语言内置的排序函数如Python的sorted()Java的Arrays.sort()是最佳选择。这些内置函数由顶尖专家优化了十几年针对不同数据类型、数据规模、内存布局做了大量优化如混合使用快速排序、插入排序、归并排序等其性能、稳定性和健壮性远超你自己实现的版本。学习这些算法的目的不是为了重新造轮子而是为了理解轮子为什么这么造从而在遇到内置函数无法解决的特殊排序需求时你能做出最明智的选择和定制。