LeetCode 912 数组排序全解：快速排序、归并排序、堆排序、计数排序、基数排序与希尔排序的多语言实现

LeetCode 912 数组排序全解快速排序、归并排序、堆排序、计数排序、基数排序与希尔排序的多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇以 LeetCode 912「排序数组」Sort an Array为实战载体系统讲解 6 种经典排序算法——快速排序、归并排序、堆排序、计数排序、基数排序与希尔排序的直觉、算法步骤、多语言实现与复杂度分析并结合当前仓库中0912-sort-an-array系列源码进行交叉印证。读完本文你将掌握为排序任意整数数组这道题选择与实现合适算法的方法并能在实际工程中规避快排退化、负数基数排序、递归栈溢出等典型陷阱。前置知识动手解决这道题之前建议先熟悉以下四块基础它们分别对应文中的六种算法递归与分治Recursion and Divide Conquer最高效的排序算法快速排序、归并排序都是通过递归把问题拆分成子问题来求解理解递归边界与子问题合并是前提数组与原址操作Arrays and In-Place Manipulation理解如何在不开辟额外空间的情况下交换元素、就地修改数组这是快速排序与堆排序的核心要求二叉堆数据结构Binary Heap堆排序依赖堆的建堆build与堆化heapify操作需要先理解完全二叉树在数组中的下标映射哈希表Hash Maps计数排序用哈希表或定长计数数组统计每个元素的出现频次再按值域顺序回填。1. 快速排序Quick Sort直觉快速排序通过选择一个pivot基准元素将数组划分为小于基准与大于基准两部分使基准落在其最终排序位置然后递归排序左右两个子区间。本文的实现在划分前采用**三数取中median-of-three**选取基准——比较left、middle、right三个位置的元素——以避免在已排序数组上退化为最坏情况。算法步骤基准情形子数组长度为 0 或 1 时直接返回若长度为 2 且顺序颠倒简单交换即可。三数取中选基准比较left、middle、right三个位置的元素把中位数交换到left 1位置作为pivot。划分partition将小于pivot的元素移到左侧将大于pivot的元素移到右侧把pivot放到最终排序位置返回其下标j。递归排序对left与j - 1、j 1与right两个区间分别递归调用快速排序。返回排序后的数组。Python 实现class Solution: def partition(self, nums: List[int], left: int, right: int) - int: mid (left right) 1 nums[mid], nums[left 1] nums[left 1], nums[mid] if nums[left] nums[right]: nums[left], nums[right] nums[right], nums[left] if nums[left 1] nums[right]: nums[left 1], nums[right] nums[right], nums[left 1] if nums[left] nums[left 1]: nums[left], nums[left 1] nums[left 1], nums[left] pivot nums[left 1] i left 1 j right while True: while True: i 1 if not nums[i] pivot: break while True: j - 1 if not nums[j] pivot: break if i j: break nums[i], nums[j] nums[j], nums[i] nums[left 1], nums[j] nums[j], nums[left 1] return j def quickSort(self, nums: List[int], left: int, right: int) - None: if right left 1: if right left 1 and nums[right] nums[left]: nums[left], nums[right] nums[right], nums[left] return j self.partition(nums, left, right) self.quickSort(nums, left, j - 1) self.quickSort(nums, j 1, right) def sortArray(self, nums: List[int]) - List[int]: self.quickSort(nums, 0, len(nums) - 1) return nums实现细节解读mid (left right) 1用位运算右移一位求中点等价于(left right) // 2三次比较交换把left、left 1、right三处元素排成有序中位数最终落在left 1作为pivot双指针i向右扫描与j向左扫描分别跳过小于基准与大于基准的元素相遇i j即完成划分递归基right left 1保证了任何长度 ≤ 2 的子数组都被直接处理从而避免越界访问nums[left 1]。其他语言实现Java 版本使用swap辅助方法逻辑与 Python 完全一致public class Solution { private int partition(int[] nums, int left, int right) { int mid (left right) 1; swap(nums, mid, left 1); if (nums[left] nums[right]) swap(nums, left, right); if (nums[left 1] nums[right]) swap(nums, left 1, right); if (nums[left] nums[left 1]) swap(nums, left, left 1); int pivot nums[left 1]; int i left 1; int j right; while (true) { while (nums[i] pivot); while (nums[--j] pivot); if (i j) break; swap(nums, i, j); } nums[left 1] nums[j]; nums[j] pivot; return j; } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } private void quickSort(int[] nums, int left, int right) { if (right left 1) { if (right left 1 nums[right] nums[left]) swap(nums, left, right); return; } int j partition(nums, left, right); quickSort(nums, left, j - 1); quickSort(nums, j 1, right); } public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; } }C 版本class Solution { public: int partition(vectorint nums, int left, int right) { int mid (left right) 1; swap(nums[mid], nums[left 1]); if (nums[left] nums[right]) swap(nums[left], nums[right]); if (nums[left 1] nums[right]) swap(nums[left 1], nums[right]); if (nums[left] nums[left 1]) swap(nums[left], nums[left 1]); int pivot nums[left 1]; int i left 1; int j right; while (true) { while (nums[i] pivot); while (nums[--j] pivot); if (i j) break; swap(nums[i], nums[j]); } nums[left 1] nums[j]; nums[j] pivot; return j; } void quickSort(vectorint nums, int left, int right) { if (right left 1) { if (right left 1 nums[right] nums[left]) swap(nums[left], nums[right]); return; } int j partition(nums, left, right); quickSort(nums, left, j - 1); quickSort(nums, j 1, right); } vectorint sortArray(vectorint nums) { quickSort(nums, 0, nums.size() - 1); return nums; } };JavaScript、C#、Go、Kotlin、Swift、Rust 版本遵循完全相同的三数取中 双指针划分结构可分别查阅仓库中的 javascript/0912-sort-an-array.js、go/0912-sort-an-array.go、kotlin/0912-sort-an-array.kt、swift/0912-sort-an-array.swift、rust/0912-sort-an-array.rs 等文件对照学习。仓库源码佐证值得注意的另一种快排写法出现在 kotlin/0912-sort-an-array.kt——它采用随机基准(low..high).random()后与末尾交换配合 Lomuto 划分单指针i扫描、nums[j] pivot时交换。这说明避免最坏情况有两种常见策略随机化基准与三数取中二者目的一致。复杂度时间复杂度平均 $O(n \log n)$最坏 $O(n ^ 2)$例如始终选到极值作为基准时空间复杂度$O(\log n)$递归调用栈。2. 归并排序Merge Sort直觉归并排序把数组分成两半递归排序每一半再将两个有序半区合并。合并过程反复取两个有序数组的队首较小者放入结果直到一方耗尽再复制剩余元素。这种分治策略保证了无论输入顺序如何时间复杂度恒为 O(n log n)且是稳定的排序。算法步骤基准情形子数组长度为 0 或 1 时天然有序。递归分解求中点mid递归排序左半[l, mid]与右半[mid1, r]。合并merge用临时数组保存左右两部分双指针比较把较小者写回原数组将任一剩余部分的元素全部复制回原数组。返回排序后的数组。Python 实现class Solution: def sortArray(self, nums: List[int]) - List[int]: def merge(arr, L, M, R): left, right arr[L:M1], arr[M1:R1] i, j, k L, 0, 0 while j len(left) and k len(right): if left[j] right[k]: arr[i] left[j] j 1 else: arr[i] right[k] k 1 i 1 while j len(left): arr[i] left[j] j 1 i 1 while k len(right): arr[i] right[k] k 1 i 1 def mergeSort(arr, l, r): if l r: return m (l r) // 2 mergeSort(arr, l, m) mergeSort(arr, m 1, r) merge(arr, l, m, r) mergeSort(nums, 0, len(nums) - 1) return nums实现细节解读合并条件用left[j] right[k]而非相等时先取左半元素这正是归并排序稳定的来源三个while循环分别处理双指针并行合并与左右剩余元素收尾整个算法不依赖输入是否有序因此最坏情况与平均情况一致。其他语言实现Java 版本用ArrayList作临时缓冲区public class Solution { public int[] sortArray(int[] nums) { mergeSort(nums, 0, nums.length - 1); return nums; } private void mergeSort(int[] arr, int l, int r) { if (l r) return; int m (l r) / 2; mergeSort(arr, l, m); mergeSort(arr, m 1, r); merge(arr, l, m, r); } private void merge(int[] arr, int l, int m, int r) { ArrayListInteger temp new ArrayList(); int i l; int j m 1; while (i m j r) { if (arr[i] arr[j]) { temp.add(arr[i]); i; } else { temp.add(arr[j]); j; } } while (i m) { temp.add(arr[i]); i; } while (j r) { temp.add(arr[j]); j; } for (i l; i r; i) { arr[i] temp.get(i - l); } } }C 版本用vectorint temp作临时缓冲区class Solution { public: vectorint sortArray(vectorint nums) { mergeSort(nums, 0, nums.size() - 1); return nums; } private: void mergeSort(vectorint arr, int l, int r) { if (l r) return; int m (l r) / 2; mergeSort(arr, l, m); mergeSort(arr, m 1, r); merge(arr, l, m, r); } void merge(vectorint arr, int l, int m, int r) { vectorint temp; int i l, j m 1; while (i m j r) { if (arr[i] arr[j]) { temp.push_back(arr[i]); } else { temp.push_back(arr[j]); } } while (i m) temp.push_back(arr[i]); while (j r) temp.push_back(arr[j]); for (int i l; i r; i) { arr[i] temp[i - l]; } } };仓库源码佐证本仓库中多个语言的0912-sort-an-array提交恰好以归并排序作为主流解法可逐一对照python/0912-sort-an-array.py自顶向下归并mergeSort返回arr写法与本文 Python 版一致java/0912-sort-an-array.java注释明确标注 Using Merge Sort使用ArrayListInteger temp暂存有序片段cpp/0912-sort-an-array.cpp采用low (high - low) / 2防溢出的中点写法并预分配sorted(size, 0)后回写nums[k low]c/0912-sort-an-array.c用malloc动态分配左右临时数组sortArray返回新数组并设置*returnSize体现了 C 语言需要手动管理内存的差异javascript/0912-sort-an-array.jsmergeSort(left, right, nums)在left right时返回nums合并时用nums.slice(left, mid 1)复制子数组kotlin/0912-sort-an-array.ktcopyOfRange(left, mid 1)复制左右半区后三路回写rust/0912-sort-an-array.rs利用split_at递归切分sort_array对空数组与单元素数组直接返回go/0912-sort-an-array.go直接调用标准库sort.Ints(nums)是工程上优先复用语言内建排序的典型示例。复杂度时间复杂度$O(n \log n)$与输入顺序无关空间复杂度$O(n)$合并所需的临时数组。3. 堆排序Heap Sort直觉堆排序利用二叉堆组织数据先把数组建成大顶堆max-heap使最大元素位于堆顶下标 0然后反复取出堆顶最大值——交换到数组末尾——缩小堆范围——对根重新堆化从而由大到小把元素沉淀到数组尾部最终得到升序数组。算法步骤建堆从最后一个非叶节点开始自底向上对所有非叶节点调用heapify。此时最大元素位于下标0。交换把堆顶最大值与最后一个未排序元素交换。缩堆堆大小减一对根节点重新heapify恢复大顶堆性质。重复步骤 3、4直到堆大小为1。返回排序后的数组。Python 实现class Solution: def sortArray(self, nums: List[int]) - List[int]: self.heapSort(nums) return nums def heapify(self, arr, n, i): l (i 1) 1 r (i 1) 2 largestNode i if l n and arr[l] arr[largestNode]: largestNode l if r n and arr[r] arr[largestNode]: largestNode r if largestNode ! i: arr[i], arr[largestNode] arr[largestNode], arr[i] self.heapify(arr, n, largestNode) def heapSort(self, arr): n len(arr) for i in range(n // 2 - 1, -1, -1): self.heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[0], arr[i] arr[i], arr[0] self.heapify(arr, i, 0)实现细节解读下标映射左孩子l (i 1) 1右孩子r (i 1) 2即完全二叉树在数组中的层序存储建堆起点n // 2 - 1是最后一个非叶节点下标下标n//2之后全是叶子heapify比较i、l、r三处把最大值换到父节点后递归向下调整被破坏的子树排序阶段每轮把arr[0]当前堆内最大交换到末尾arr[i]再对缩小的堆大小为i从根重新堆化。其他语言实现C 版本class Solution { public: vectorint sortArray(vectorint nums) { heapSort(nums); return nums; } private: void heapify(vectorint arr, int n, int i) { int l (i 1) 1; int r (i 1) 2; int largestNode i; if (l n arr[l] arr[largestNode]) { largestNode l; } if (r n arr[r] arr[largestNode]) { largestNode r; } if (largestNode ! i) { swap(arr[i], arr[largestNode]); heapify(arr, n, largestNode); } } void heapSort(vectorint arr) { int n arr.size(); for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } for (int i n - 1; i 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } } };JavaScript 版本使用数组解构交换class Solution { sortArray(nums) { this.heapSort(nums); return nums; } heapify(arr, n, i) { let l (i 1) 1; let r (i 1) 2; let largestNode i; if (l n arr[l] arr[largestNode]) { largestNode l; } if (r n arr[r] arr[largestNode]) { largestNode r; } if (largestNode ! i) { [arr[i], arr[largestNode]] [arr[largestNode], arr[i]]; this.heapify(arr, n, largestNode); } } heapSort(arr) { let n arr.length; for (let i Math.floor(n / 2) - 1; i 0; i--) { this.heapify(arr, n, i); } for (let i n - 1; i 0; i--) { [arr[0], arr[i]] [arr[i], arr[0]]; this.heapify(arr, i, 0); } } }仓库源码佐证kotlin/0912-sort-an-array.kt 中提供了同构的堆排序实现heapSortheapify其排序循环for(i in n-1 downTo 0)与原文档逻辑一致可用于对照 Kotlin 语法下的写法。Java、C#、Go、Swift、Rust 版本结构相同见仓库对应文件。复杂度时间复杂度$O(n \log n)$建堆 $O(n)$n-1 次堆化每次 $O(\log n)$空间复杂度$O(\log n)$递归堆化的调用栈若迭代实现 heapify 则为 $O(1)$。4. 计数排序Counting Sort直觉计数排序统计每个不同值的出现频次然后按值域从小到大把每个值回填相应次数从而完全避开比较。当值域范围max - min与元素个数 n 相比不算悬殊时计数排序效率极高。算法步骤找出数组中的min与max。建立count哈希表或计数数组记录每个值的频次。遍历数组对每个值自增计数。从min到max遍历值域对计数为正的值按次数回填进数组每回填一次就递减计数。返回排序后的数组。Python 实现class Solution: def sortArray(self, nums: List[int]) - List[int]: def counting_sort(): count defaultdict(int) minVal, maxVal min(nums), max(nums) for val in nums: count[val] 1 index 0 for val in range(minVal, maxVal 1): while count[val] 0: nums[index] val index 1 count[val] - 1 counting_sort() return nums实现细节解读使用defaultdict(int)作为频次表min/max决定值域扫描范围核心循环for val in range(minVal, maxVal 1)从最小值扫到最大值天然保证升序这里用哈希表而非定长数组原因是整数数组可能包含负数且值域不连续哈希表只占用实际出现值的空间。其他语言实现Java 版本HashMapgetOrDefaultpublic class Solution { private void countingSort(int[] arr) { HashMapInteger,Integer count new HashMap(); int minVal arr[0], maxVal arr[0]; for (int i 0; i arr.length; i) { minVal Math.min(minVal, arr[i]); maxVal Math.max(maxVal, arr[i]); count.put(arr[i], count.getOrDefault(arr[i], 0) 1); } int index 0; for (int val minVal; val maxVal; val) { while (count.getOrDefault(val, 0) 0) { arr[index] val; index 1; count.put(val, count.get(val) - 1); } } } public int[] sortArray(int[] nums) { countingSort(nums); return nums; } }C 版本unordered_mapclass Solution { private: void countingSort(vectorint arr) { unordered_mapint, int count; int minVal *min_element(arr.begin(), arr.end()); int maxVal *max_element(arr.begin(), arr.end()); for (auto val : arr) { count[val]; } int index 0; for (int val minVal; val maxVal; val) { while (count[val] 0) { arr[index] val; index 1; count[val] - 1; } } } public: vectorint sortArray(vectorint nums) { countingSort(nums); return nums; } };JavaScriptMap、C#Dictionary、Gomap、KotlinHashMap、Swift[Int: Int]、RustHashMap版本的实现结构一致均遵循统计频次 → 扫描值域回填的模式可查阅仓库中对应语言文件。复杂度时间复杂度$O(n k)$空间复杂度$O(n)$其中 $n$ 为数组nums的大小$k$ 为数组中最小值与最大值之间的值域范围。当 $k$ 远大于 $n$例如[1, 10^9]两个元素时扫描值域的代价会超过 $O(n \log n)$此时应改用比较类排序。5. 基数排序Radix Sort直觉基数排序按位处理整数从最低有效位个位到最高有效位逐位排序。每一位都调用稳定的计数排序作为子过程由于计数排序是稳定的上一轮位排序建立的相对顺序得以保留。为了处理负数先把负数分离出来对其绝对值升序排序后反转再取负最后拼接。算法步骤将数组分为negatives转换为正数存储与positives两组。对每组分别执行基数排序求出组内最大值确定需要的位数轮次对每一位个位、十位、百位……基于当前位做计数排序从右向左遍历维持稳定性。反转排序后的negatives并重新取负绝对值越大、负数越小故反转。拼接negatives与positives得到最终有序数组。Python 实现class Solution: def sortArray(self, nums: List[int]) - List[int]: def countSort(arr, n, d): count [0] * 10 for num in arr: count[(num // d) % 10] 1 for i in range(1, 10): count[i] count[i - 1] res [0] * n for i in range(n - 1, -1, -1): idx (arr[i] // d) % 10 res[count[idx] - 1] arr[i] count[idx] - 1 for i in range(n): arr[i] res[i] def radixSort(arr): n len(arr) max_element max(arr) d 1 while max_element // d 0: countSort(arr, n, d) d * 10 negatives [-num for num in nums if num 0] positives [num for num in nums if num 0] if negatives: radixSort(negatives) negatives [-num for num in reversed(negatives)] if positives: radixSort(positives) return negatives positives实现细节解读位数桶固定为 10 个十进制数字 0~9(num // d) % 10提取当前位count累加为前缀和cumulative count从而确定每个元素在结果中的落点区间关键稳定性技巧从n-1到0逆序遍历原数组每个元素放入res[count[idx] - 1]并递减count[idx]保证同一位相同数字的元素保持原相对顺序负数处理-num后绝对值参与排序正序排序结果反转即得负数从大到小绝对值从小到大再取负就得到负数从小到大轮次控制d 1, 10, 100, ...直到max_element // d 0为止。其他语言实现C 版本class Solution { public: vectorint sortArray(vectorint nums) { vectorint negatives, positives; for (int num : nums) { if (num 0) { negatives.push_back(-num); } else { positives.push_back(num); } } if (!negatives.empty()) { radixSort(negatives); reverse(negatives.begin(), negatives.end()); for (int num : negatives) { num -num; } } if (!positives.empty()) { radixSort(positives); } int index 0; for (int num : negatives) { nums[index] num; } for (int num : positives) { nums[index] num; } return nums; } private: void countSort(vectorint arr, int n, int d) { vectorint count(10, 0); for (int num : arr) { count[(num / d) % 10]; } for (int i 1; i 10; i) { count[i] count[i - 1]; } vectorint res(n); for (int i n - 1; i 0; i--) { int idx (arr[i] / d) % 10; res[count[idx] - 1] arr[i]; count[idx]--; } for (int i 0; i n; i) { arr[i] res[i]; } } void radixSort(vectorint arr) { int n arr.size(); int maxElement *max_element(arr.begin(), arr.end()); int d 1; while (maxElement / d 0) { countSort(arr, n, d); d * 10; } } };Go 版本负数反转采用双指针原地交换func sortArray(nums []int) []int { var negatives, positives []int for _, num : range nums { if num 0 { negatives append(negatives, -num) } else { positives append(positives, num) } } if len(negatives) 0 { radixSort(negatives) for i, j : 0, len(negatives)-1; i j; i, j i1, j-1 { negatives[i], negatives[j] negatives[j], negatives[i] } for i : range negatives { negatives[i] -negatives[i] } } if len(positives) 0 { radixSort(positives) } return append(negatives, positives...) } func radixSort(arr []int) { maxElement : 0 for _, num : range arr { if num maxElement { maxElement num } } d : 1 for maxElement/d 0 { countSort(arr, d) d * 10 } } func countSort(arr []int, d int) { n : len(arr) count : make([]int, 10) for _, num : range arr { count[(num/d)%10] } for i : 1; i 10; i { count[i] count[i-1] } res : make([]int, n) for i : n - 1; i 0; i-- { idx : (arr[i] / d) % 10 res[count[idx]-1] arr[i] count[idx]-- } copy(arr, res) }Java、JavaScript、C#、Kotlin、Swift、Rust 版本遵循完全相同的分离负数 → 逐位稳定计数排序 → 反转取负 → 拼接流程可在仓库对应语言文件中查阅完整代码。复杂度时间复杂度$O(d \cdot n)$空间复杂度$O(n)$其中 $n$ 为数组nums的大小$d$ 为数组中最大元素的位数。对 32 位整数而言 $d$ 可视为常数因此基数排序在实践中近似线性。6. 希尔排序Shell Sort直觉希尔排序是插入排序的泛化它允许交换相距较远的元素先用较大的gap间隔对相隔 gap 的元素做间隔插入排序让元素快速逼近最终位置再逐步缩小 gap。当gap变为 1 时对已经接近有序的数组执行一次标准插入排序开销很小。算法步骤初始gap n / 2。对每个gap值执行间隔为gap的插入排序对每个元素与它前面相隔gap的元素比较若前驱更大则按gap步长向前搬移元素直到找到正确插入位置插入当前元素。gap折半重复直至gap为 0。返回排序后的数组。Python 实现class Solution: def sortArray(self, nums: List[int]) - List[int]: def shell_sort(nums, n): gap n // 2 while gap 1: for i in range(gap, n): tmp nums[i] j i - gap while j 0 and nums[j] tmp: nums[j gap] nums[j] j - gap nums[j gap] tmp gap // 2 n len(nums) if n 1: return nums shell_sort(nums, n) return nums实现细节解读外层while gap 1控制间隔序列n/2, n/4, ..., 1即希尔建议的原始序列内层对每个i ∈ [gap, n)把nums[i]与其前方相隔gap的元素做间隔插入——这等价于把数组拆成 gap 个子序列分别做插入排序当 gap 缩小到 1 时退化为普通插入排序但此时数组已接近有序比较与搬移次数很少单元素数组直接返回跳过排序。其他语言实现Java 版本public class Solution { private void shellSort(int[] nums, int n) { int gap n / 2; while (gap 1) { for (int i gap; i n; i) { int tmp nums[i]; int j i - gap; while (j 0 nums[j] tmp) { nums[j gap] nums[j]; j - gap; } nums[j gap] tmp; } gap / 2; } } public int[] sortArray(int[] nums) { int n nums.length; if (n 1) return nums; shellSort(nums, n); return nums; } }C 版本把 gap 循环写进 for 头class Solution { private: void shellSort(vectorint nums, int n) { for (int gap n / 2; gap 1; gap / 2) { for (int i gap; i n; i) { int tmp nums[i]; int j i - gap; while (j 0 nums[j] tmp) { nums[j gap] nums[j]; j - gap; } nums[j gap] tmp; } } } public: vectorint sortArray(vectorint nums) { if (nums.size() 1) return nums; shellSort(nums, nums.size()); return nums; } };JavaScript、C#、Go、Kotlin、Swift、Rust 版本的实现骨架一致gap 折半序列 间隔插入详见仓库对应语言文件。复杂度时间复杂度平均 $O(n \log n)$最坏 $O(n ^ 2)$与 gap 序列的选取有关空间复杂度$O(1)$纯原址排序不依赖额外空间。六种算法复杂度总览算法平均时间复杂度最坏时间复杂度空间复杂度稳定性是否原址快速排序$O(n \log n)$$O(n^2)$$O(\log n)$不稳定是归并排序$O(n \log n)$$O(n \log n)$$O(n)$稳定否堆排序$O(n \log n)$$O(n \log n)$$O(\log n)$不稳定是计数排序$O(n k)$$O(n k)$$O(n)$稳定否基数排序$O(d \cdot n)$$O(d \cdot n)$$O(n)$稳定否希尔排序$O(n \log n)$$O(n^2)$$O(1)$不稳定是上表基于本文各算法小节给出的复杂度结论整理。稳定性与是否原址两项可由各算法实现代码直接验证如归并排序在时先取左半即稳定堆排序的交换操作破坏稳定性。对 LeetCode 912 这道题六种方案均可在 $O(n \log n)$或对特定值域更优内通过选择依据是数据规模、值域特征以及对额外空间的容忍度。常见陷阱Common Pitfalls陷阱一快速排序使用朴素的基准选择不进行随机化或中位数选择、直接取首元素或末元素作为pivot会在已排序或接近有序的数组上退化为 $O(n^2)$。应始终使用随机化基准或三数取中median-of-three避免常见输入形态下的最坏情况。本文快速排序实现采用三数取中kotlin/0912-sort-an-array.kt 则展示了随机化基准的另一种写法。陷阱二基数排序忘记处理负数基数排序只对非负整数直接有效。若不先分离负数就对其排序结果必然错误。必须把负数单独取出转换为正数参与排序排序后反转并重新取负再与正数部分拼接。本文基数排序的negatives/positives分离流程正是为此设计。陷阱三递归实现的栈溢出归并排序与快速排序的递归深度在极端情况下可能触发栈溢出如超大数组或最坏划分下快排递归深度达到 n。生产环境建议改用迭代实现或确认语言/运行时是否支持尾调用优化部分语言对栈深度有严格限制递归排序算法可能因此越界。堆排序与希尔排序天然规避了深递归问题也是替代选择。工程实践建议结合本文六种算法与仓库源码可以提炼出以下选型思路优先复用语言内建排序如 go/0912-sort-an-array.go 直接调用sort.IntsJava 的Arrays.sort、Python 的sorted底层都是经过充分优化的混合排序如 TimSort、双轴快排工程中无需重复造轮子追求最坏情况可控选归并排序稳定、最坏 $O(n \log n)$或堆排序原址、最坏 $O(n \log n)$不选朴素的快速排序值域紧凑的小整数优先计数排序或基数排序突破比较排序的 $O(n \log n)$ 下界对空间敏感选择堆排序或希尔排序这类 $O(1)$ 额外空间的方案递归受限环境避免深递归的快排/归并改用迭代版本或堆/希尔排序。这些算法与陷阱的完整多语言代码均可从仓库中 articles/sort-an-array.md 以及python/0912-sort-an-array.py、java/0912-sort-an-array.java、cpp/0912-sort-an-array.cpp、c/0912-sort-an-array.c、javascript/0912-sort-an-array.js、go/0912-sort-an-array.go、kotlin/0912-sort-an-array.kt、rust/0912-sort-an-array.rs、swift/0912-sort-an-array.swift等文件中继续研读。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考