教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇是《算法通关手册》数组章节的总纲性指南系统梳理数组排序的完整知识地图从时间复杂度、空间复杂度、稳定性三个维度对排序算法进行分类建立统一的评价指标体系并逐一对照仓库中十种排序算法的 Python 源码实现最后给出结合数据规模、数据特征与环境约束的工程选型策略。读完本文你将掌握 10 种经典数组排序算法的原理、复杂度特征与适用场景并能基于仓库源码独立复现与验证每种算法。1. 排序算法的分类数组排序是计算机科学中最基本的问题之一。排序算法种类繁多每种算法都有其特点和适用场景。在深入理解具体算法之前先建立分类框架有助于后续的对比与选型。1.1 按照时间复杂度分类简单排序算法时间复杂度为 $O(n^2)$如冒泡排序、选择排序、插入排序。实现简单、常数因子小适合小规模数据。高级排序算法时间复杂度为 $O(n \log n)$如快速排序、归并排序、堆排序。在大数据量下具有明显性能优势。线性排序算法时间复杂度为 $O(n)$如计数排序、桶排序、基数排序。这类算法往往对数据分布或取值范围有额外要求如数据范围有限、位数有限在满足条件时可以达到线性复杂度。1.2 按照空间复杂度分类原地排序算法空间复杂度为 $O(1)$如冒泡排序、选择排序、插入排序、快速排序、堆排序。只需常数级别的额外空间在内存受限环境下优先考虑。非原地排序算法空间复杂度为 $O(n)$ 或更高如归并排序、计数排序、桶排序、基数排序。需要借助辅助数组或桶结构以空间换取时间。1.3 按照稳定性分类稳定排序算法相等元素的相对顺序在排序后保持不变如冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序。当数据本身携带附加信息、需要保持原始次序时稳定性至关重要。不稳定排序算法相等元素的相对顺序在排序后可能改变如选择排序、快速排序、堆排序。稳定性与算法是否基于相邻元素比较/交换密切相关只对相邻元素进行交换的排序算法通常是稳定的而跨距离交换如选择排序的远距离交换、快速排序的哨兵交换则可能破坏相等元素的相对顺序。2. 排序算法的评价指标评价一个排序算法的好坏主要从以下几个方面考虑时间复杂度算法执行所需的时间包括最好情况、最坏情况和平均情况。三种情况分别刻画了算法在数据恰好有序、数据完全逆序以及一般随机分布下的性能表现选型时不能只看平均复杂度。空间复杂度算法执行所需的额外空间不包括输入数据本身。对嵌入式系统、内存受限环境空间占用往往是硬约束。稳定性相等元素的相对顺序是否保持不变。这是工程选型中最容易忽略、却在实际业务如按多个关键字排序中最常踩坑的指标。原地性是否需要在原数组之外开辟额外空间。原地排序意味着可以在原数组上完成排序避免大数组的拷贝开销。这四项指标共同构成排序算法的体检表下文每种算法的复杂度表即依据此体系展开。3. 常见排序算法与源码实现仓库在 codes/python/01_array 目录下为每种排序算法提供了可直接运行的 Python 实现统一以Solution.sortArray作为入口并附有测试用例同时在 docs/01_array 中为每种算法配有一篇独立详解章节。下面逐一介绍十种常见排序算法。3.1 冒泡排序Bubble Sort核心思想通过相邻元素比较和交换将最大元素逐步「冒泡」到数组末尾。每一趟冒泡都会让未排序区间的最大值就位。源码实现array_sort_bubble_sort.pyclass Solution: def bubbleSort(self, nums: [int]) - [int]: # 第 i 趟「冒泡」 for i in range(len(nums) - 1): flag False # 是否发生交换的标志位 # 对数组未排序区间 [0, n - i - 1] 的元素执行「冒泡」 for j in range(len(nums) - i - 1): # 相邻两个元素进行比较如果前者大于后者则交换位置 if nums[j] nums[j 1]: nums[j], nums[j 1] nums[j 1], nums[j] flag True if not flag: # 此趟遍历未交换任何元素直接跳出 break return nums def sortArray(self, nums: [int]) - [int]: return self.bubbleSort(nums)注意源码中的flag标志位一旦某一趟遍历未发生任何交换说明数组已经有序可以提前终止——这正是其最好时间复杂度能达到 $O(n)$ 的原因。详细图解与步骤见 冒泡排序详解。复杂度与特点指标复杂度说明最佳时间复杂度$O(n)$数组已有序只需一趟遍历最坏时间复杂度$O(n^2)$数组逆序需要 $n$ 趟遍历平均时间复杂度$O(n^2)$一般情况下的复杂度空间复杂度$O(1)$原地排序只使用常数空间稳定性稳定相等元素相对位置不变3.2 选择排序Selection Sort核心思想将数组分为已排序区间左侧与未排序区间右侧每趟从未排序区间中选出最小元素放到已排序区间末尾。选择排序的优势在于交换次数少每趟最多一次交换总共最多 $n-1$ 次交换。源码实现array_sort_selection_sort.pyclass Solution: def selectionSort(self, nums: [int]) - [int]: for i in range(len(nums) - 1): # 记录未排序区间中最小值的位置 min_i i for j in range(i 1, len(nums)): if nums[j] nums[min_i]: min_i j # 如果找到最小值的位置将 i 位置上元素与最小值位置上的元素进行交换 if i ! min_i: nums[i], nums[min_i] nums[min_i], nums[i] return nums def sortArray(self, nums: [int]) - [int]: return self.selectionSort(nums)时间复杂度无论数据初始状态如何都是 $O(n^2)$每趟都必须完整扫描未排序区间空间复杂度 $O(1)$属于不稳定排序——交换操作可能跨越相等的元素。3.3 插入排序Insertion Sort核心思想将数组分为有序区间左侧与无序区间右侧每趟从无序区间取出第一个元素从右向左在有序区间中找到合适位置插入。插入排序对基本有序的数据非常高效且是很多高级排序如希尔排序、桶排序桶内排序、Timsort 混合策略的基础构件。源码实现array_sort_insertion_sort.pyclass Solution: def insertionSort(self, nums: [int]) - [int]: # 遍历无序区间 for i in range(1, len(nums)): temp nums[i] j i # 从右至左遍历有序区间 while j 0 and nums[j - 1] temp: # 将有序区间中插入位置右侧的所有元素依次右移一位 nums[j] nums[j - 1] j - 1 # 将该元素插入到适当位置 nums[j] temp return nums def sortArray(self, nums: [int]) - [int]: return self.insertionSort(nums)最好情况数据已有序时间复杂度为 $O(n)$最坏与平均情况为 $O(n^2)$空间复杂度 $O(1)$稳定排序。3.4 希尔排序Shell Sort核心思想先按一定间隔 $gap$ 将数组分组对每组分别进行插入排序随后逐步缩小 $gap$最终在 $gap 1$ 时对整个数组做一次完整插入排序。它通过宏观上先让数组大致有序来减少后续插入排序的移动次数是插入排序的改进版。源码实现array_sort_shell_sort.pyclass Solution: def shellSort(self, nums: [int]) - [int]: size len(nums) gap size // 2 # 按照 gap 分组 while gap 0: # 对每组元素进行插入排序 for i in range(gap, size): # temp 为每组中无序数组第 1 个元素 temp nums[i] j i # 从右至左遍历每组中的有序数组元素 while j gap and nums[j - gap] temp: # 将每组有序数组中插入位置右侧的元素依次在组中右移一位 nums[j] nums[j - gap] j - gap # 将该元素插入到适当位置 nums[j] temp # 缩小 gap 间隔 gap gap // 2 return nums def sortArray(self, nums: [int]) - [int]: return self.shellSort(nums)源码采用 $gap size // 2$ 起、每轮 $gap gap // 2$ 的经典递减序列。仓库实战记录显示其时间复杂度介于 $O(n \log n)$ 与 $O(n^2)$ 之间空间复杂度 $O(1)$。3.5 归并排序Merge Sort核心思想采用经典分治策略——先将数组从中间一分为二递归地对左右子数组排序再通过「合并」过程将两个有序子数组合并为一个有序数组。归并排序的复杂度是稳定可预期的 $O(n \log n)$不受数据初始顺序影响且是稳定排序因此也是外部排序数据量超出内存时的基础算法。源码实现array_sort_merge_sort.pyclass Solution: # 合并过程 def merge(self, left_nums: [int], right_nums: [int]): nums [] left_i, right_i 0, 0 while left_i len(left_nums) and right_i len(right_nums): # 将两个有序子数组中较小元素依次插入到结果数组中 if left_nums[left_i] right_nums[right_i]: nums.append(left_nums[left_i]) left_i 1 else: nums.append(right_nums[right_i]) right_i 1 # 如果左子数组有剩余元素则将其插入到结果数组中 while left_i len(left_nums): nums.append(left_nums[left_i]) left_i 1 # 如果右子数组有剩余元素则将其插入到结果数组中 while right_i len(right_nums): nums.append(right_nums[right_i]) right_i 1 return nums # 分解过程 def mergeSort(self, nums: [int]) - [int]: if len(nums) 1: return nums mid len(nums) // 2 # 将数组从中间位置分为左右两个数组 left_nums self.mergeSort(nums[0: mid]) # 递归将左子数组进行分解和排序 right_nums self.mergeSort(nums[mid:]) # 递归将右子数组进行分解和排序 return self.merge(left_nums, right_nums) # 把当前数组组中有序子数组逐层向上进行两两合并 def sortArray(self, nums: [int]) - [int]: return self.mergeSort(nums)时间复杂度 $O(n \log n)$空间复杂度 $O(n)$合并过程需要额外数组稳定排序。代价是牺牲了原地性。3.6 快速排序Quick Sort核心思想选择一个基准元素pivot通过「哨兵划分」将数组分为两部分小于基准的元素放在左侧大于基准的元素放在右侧随后递归排序左右两部分。它是实际工程中使用最广泛的排序算法之一许多编程语言的内置排序都以其为内核。源码实现array_sort_quick_sort.pyimport random class Solution: # 随机哨兵划分从 nums[low: high 1] 中随机挑选一个基准数并进行移位排序 def randomPartition(self, nums: [int], low: int, high: int) - int: # 随机挑选一个基准数 i random.randint(low, high) # 将基准数与最低位互换 nums[i], nums[low] nums[low], nums[i] return self.partition(nums, low, high) # 哨兵划分以第 1 位元素 nums[low] 为基准数将比基准数小的元素移动到左侧大的移动到右侧 def partition(self, nums: [int], low: int, high: int) - int: # 以第 1 位元素为基准数 pivot nums[low] i, j low, high while i j: # 从右向左找到第 1 个小于基准数的元素 while i j and nums[j] pivot: j - 1 # 从左向右找到第 1 个大于基准数的元素 while i j and nums[i] pivot: i 1 # 交换元素 nums[i], nums[j] nums[j], nums[i] # 将基准数放到正确位置上 nums[j], nums[low] nums[low], nums[j] return j def quickSort(self, nums: [int], low: int, high: int) - [int]: if low high: pivot_i self.partition(nums, low, high) self.quickSort(nums, low, pivot_i - 1) self.quickSort(nums, pivot_i 1, high) return nums def sortArray(self, nums: [int]) - [int]: return self.quickSort(nums, 0, len(nums) - 1)复杂度与优化详见 快速排序详解指标复杂度说明最佳时间复杂度$O(n \log n)$每次都能将数组平均分成两半最坏时间复杂度$O(n^2)$每次选择的基准值都是极值如已排序数组平均时间复杂度$O(n \log n)$随机选择基准值时的期望复杂度空间复杂度$O(\log n)$递归栈空间最坏情况下为 $O(n)$稳定性不稳定交换操作可能改变相等元素的相对位置源码中的randomPartition正是针对最坏情况的经典优化——随机选择基准值避免有序数组退化到 $O(n^2)$。其他常用优化还包括三数取中法、小数组改用插入排序、处理大量重复元素时使用三路快排等。3.7 堆排序Heap Sort核心思想借助「堆」这一数据结构完成排序。升序排序时先构建大顶堆根节点为最大值反复将堆顶与堆末尾交换、缩小堆范围并下移调整最终得到升序数组降序则对应小顶堆。仓库同时提供了两种实现array_sort_maxheap_sort.py大顶堆与 array_sort_minheap_sort.py小顶堆。核心流程以大顶堆升序为例建堆先将数组元素按原顺序填入堆数组再从最后一个非叶子节点(size - 2) // 2开始向前逐个执行下移调整构建大顶堆交换与调整将堆顶最大元素与堆末尾交换堆长度减 1再从根节点下移调整保持堆性质重复直到堆大小变为 1数组即完全有序。源码要点节选自 array_sort_maxheap_sort.pyclass MaxHeap: def __init__(self): self.max_heap [] def __buildMaxHeap(self, nums: [int]): size len(nums) # 先将数组 nums 的元素按顺序添加到 max_heap 中 for i in range(size): self.max_heap.append(nums[i]) # 从最后一个非叶子节点开始进行下移调整 for i in range((size - 2) // 2, -1, -1): self.__shift_down(i, size) def maxHeapSort(self, nums: [int]) - [int]: self.__buildMaxHeap(nums) size len(self.max_heap) for i in range(size - 1, -1, -1): # 交换根节点与当前堆的最后一个节点 self.max_heap[0], self.max_heap[i] self.max_heap[i], self.max_heap[0] # 从根节点开始对当前堆进行下移调整 self.__shift_down(0, i) return self.max_heap时间复杂度 $O(n \log n)$建堆 $O(n)$、每次取堆顶调整 $O(\log n)$空间复杂度 $O(1)$不稳定排序。3.8 计数排序Counting Sort核心思想统计每个元素出现的次数再根据统计信息将元素放回正确位置。它不是基于比较的排序适用于取值范围有限值域 $k$ 不大的整数数据是典型的线性排序。源码实现array_sort_counting_sort.pyclass Solution: def countingSort(self, nums: [int]) - [int]: # 计算待排序数组中最大值元素 nums_max 和最小值元素 nums_min nums_min, nums_max min(nums), max(nums) # 定义计数数组 counts大小为 最大值元素 - 最小值元素 1 size nums_max - nums_min 1 counts [0 for _ in range(size)] # 统计值为 num 的元素出现的次数 for num in nums: counts[num - nums_min] 1 # 生成累积计数数组 for i in range(1, size): counts[i] counts[i - 1] # 反向填充目标数组 res [0 for _ in range(len(nums))] for i in range(len(nums) - 1, -1, -1): num nums[i] # 根据累积计数数组将 num 放在数组对应位置 res[counts[num - nums_min] - 1] num # 将 num 的对应放置位置减 1从而得到下个元素 num 的放置位置 counts[nums[i] - nums_min] - 1 return res def sortArray(self, nums: [int]) - [int]: return self.countingSort(nums)实现要点计数数组下标通过num - nums_min偏移可处理含负数的数据通过累积计数数组与反向填充保证稳定性。时间复杂度 $O(n k)$空间复杂度 $O(k)$$k$ 为值域大小稳定排序。3.9 桶排序Bucket Sort核心思想将元素按值域范围分散到若干个「桶」中每个桶内部再单独排序通常用插入排序最后按桶区间顺序合并。当数据分布均匀时效率接近线性。源码实现array_sort_bucket_sort.pyclass Solution: def insertionSort(self, nums: [int]) - [int]: for i in range(1, len(nums)): temp nums[i] j i while j 0 and nums[j - 1] temp: nums[j] nums[j - 1] j - 1 nums[j] temp return nums def bucketSort(self, nums: [int], bucket_size5) - [int]: # 计算待排序序列中最大值元素 nums_max、最小值元素 nums_min nums_min, nums_max min(nums), max(nums) # 定义桶的个数为 (最大值元素 - 最小值元素) // 每个桶的大小 1 bucket_count (nums_max - nums_min) // bucket_size 1 # 定义桶数组 buckets buckets [[] for _ in range(bucket_count)] # 遍历待排序数组元素将每个元素根据大小分配到对应的桶中 for num in nums: buckets[(num - nums_min) // bucket_size].append(num) # 对每个非空桶内的元素单独排序排序之后按照区间顺序依次合并到 res 数组中 res [] for bucket in buckets: self.insertionSort(bucket) res.extend(bucket) return res def sortArray(self, nums: [int]) - [int]: return self.bucketSort(nums)桶的数量由bucket_size参数控制(max - min) // bucket_size 1。桶内元素越均匀单桶规模越小整体越接近 $O(n)$空间复杂度为 $O(n m)$$m$ 为桶的个数稳定排序。3.10 基数排序Radix Sort核心思想将整数按位数切割成不同的数字从最低位个位开始逐位进行分配与收集最终整体有序。采用最低位优先LSD法时每一轮都是稳定的计数/桶式分配。源码实现array_sort_radix_sort.pyclass Solution: def radixSort(self, nums: [int]) - [int]: # 桶的大小为所有元素的最大位数 size len(str(max(nums))) # 从最低位个位开始逐位遍历每一位 for i in range(size): # 定义长度为 10 的桶数组 buckets每个桶分别代表 0 ~ 9 中的 1 个数字。 buckets [[] for _ in range(10)] # 遍历数组元素按照每个元素当前位上的数字将元素放入对应数字的桶中。 for num in nums: buckets[num // (10 ** i) % 10].append(num) # 清空原始数组 nums.clear() # 按照桶的顺序依次取出对应元素重新加入到原始数组中。 for bucket in buckets: for num in bucket: nums.append(num) # 完成排序返回结果数组 return nums def sortArray(self, nums: [int]) - [int]: return self.radixSort(nums)时间复杂度 $O(n \times k)$$k$ 为数字位数取决于进制与值域全集空间复杂度 $O(n k)$稳定排序。注意适用前提仓库实战记录明确指出普通基数排序只适合非负数——因为负数参与取模与整除运算时无法正确分配桶处理含负数的数据需要额外改造。3.11 十种排序算法复杂度速查表算法平均时间复杂度最好最坏空间复杂度稳定性原地性冒泡排序$O(n^2)$$O(n)$$O(n^2)$$O(1)$稳定原地选择排序$O(n^2)$$O(n^2)$$O(n^2)$$O(1)$不稳定原地插入排序$O(n^2)$$O(n)$$O(n^2)$$O(1)$稳定原地希尔排序$O(n \log n)$ ~ $O(n^2)$——$O(1)$—原地归并排序$O(n \log n)$$O(n \log n)$$O(n \log n)$$O(n)$稳定非原地快速排序$O(n \log n)$$O(n \log n)$$O(n^2)$$O(\log n)$最坏 $O(n)$不稳定原地堆排序$O(n \log n)$$O(n \log n)$$O(n \log n)$$O(1)$不稳定原地计数排序$O(n k)$$O(n k)$$O(n k)$$O(k)$稳定非原地桶排序$O(n)$$O(n)$$O(n^2)$$O(n m)$稳定非原地基数排序$O(n \times k)$$O(n \times k)$$O(n \times k)$$O(n k)$稳定非原地表中 $k$ 表示计数排序的值域大小或基数排序的数字位数$m$ 表示桶排序的桶个数。该表综合了 01_02_array_sort.md 的分类体系、各算法分章文档以及 0912 排序数组题解 中的复杂度结论。4. 排序算法的选择策略在实际应用中选择合适的排序算法需要综合考虑以下因素4.1 数据规模小规模数据$n 50$可以使用简单排序算法如插入排序。其常数因子小、实现简单往往快过复杂度理论上更优的算法。中等规模数据$50 \le n 1000$推荐使用快速排序或归并排序。大规模数据$n \ge 1000$优先考虑快速排序、归并排序或堆排序它们能保证接近 $O(n \log n)$ 的稳定性能。4.2 数据特征基本有序插入排序效率较高最好情况可达到 $O(n)$。数据分布均匀快速排序效率较高递归划分均匀、深度接近 $\log n$。数据范围较小计数排序或桶排序可能更高效能以 $O(n)$ 线性完成排序。数据有大量重复三路快速排序或计数排序更合适可避免快速排序在重复数据下的退化。4.3 环境约束空间限制选择原地排序算法冒泡、选择、插入、快速、堆排序避免额外数组带来的内存压力。稳定性要求选择稳定排序算法冒泡、插入、归并、计数、桶、基数排序保证相等元素的原始相对顺序。硬件环境考虑缓存友好性和并行化潜力。快速排序与归并排序天然具备分治结构便于并行化。4.4 实际应用场景系统排序通常使用快速排序或归并排序的混合算法如经典 Timsort归并 插入排序兼顾最坏情况性能与常数因子。外部排序使用归并排序。当数据无法全部载入内存时归并排序的多路归并是外部排序的标准思路。实时系统优先考虑时间复杂度稳定的算法如归并排序、堆排序避免快速排序式的偶然最坏情况抖动。内存受限环境选择空间复杂度低的算法原地排序。5. 实战验证用 LeetCode 0912「排序数组」检验十种算法仓库在 sort-an-array.md 中记录了针对 LeetCode 0912「排序数组」$nums.length \le 5 \times 10^4$$|nums[i]| \le 5 \times 10^4$逐一测试十种排序算法的真实结论与本篇的复杂度分析完全相互印证超时算法$O(n^2)$冒泡排序、选择排序、插入排序——在 5 万规模数据下无法通过通过算法$O(n \log n)$希尔排序、归并排序、快速排序、堆排序通过算法$O(n)$计数排序、桶排序——得益于题目取值范围有限$[-5\times10^4, 5\times10^4]$这一数据特征解答错误算法基数排序——普通实现只适合非负数而本题数据包含负数。这一实战记录同时印证了本章选型策略的两条关键结论大规模数据必须选择 $O(n \log n)$ 级别及以上的高效算法线性排序算法计数、桶只有在数据范围受限时才可行。排序算法相关的更多练习题目见 数组排序算法题目列表。6. 总结排序算法的核心目标是将数据按指定顺序排列。常见排序算法各有优缺点选择时需结合数据规模、数据特性和实际需求综合权衡小规模数据可用插入、冒泡等简单算法常数因子小、实现直观大规模或高性能场景优先考虑快速排序、归并排序等 $O(n \log n)$ 高效算法数据范围受限时可利用计数排序、桶排序、基数排序达到线性复杂度有稳定性或空间限制等特殊要求时应优先选择满足条件的算法。理解各种排序的原理和适用场景有助于在实际开发中做出最优选择。本文所述的十种算法均可在仓库 codes/python/01_array 中直接运行验证每种算法的详细图解、逐步推导与复杂度分析可继续阅读 01_array 章节目录 下对应的分章文档。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 数组基数排序完全指南按位分桶的线性复杂度排序算法AlgoNote 数组基数排序完全指南按位分桶的线性复杂度排序算法 基数排序Radix Sort是 AlgoNote「算法通关手册」数组排序章节中的一种教程文档知识库NitroStack性能优化指南10个技巧让你的AI应用快如闪电NitroStack性能优化指南10个技巧让你的AI应用快如闪电 NitroStack是一个高性能TypeScript框架专为构建、测试和部署生产级MCP服Typst排序算法终极指南5种高效数据排序与筛选方法Typst排序算法终极指南5种高效数据排序与筛选方法 Typst是一个强大的基于标记的排版系统它提供了丰富的数组操作功能包括多种排序算法和数据筛选方法。本编译器CLI上一篇5分钟掌握歌词管理神器本地音乐歌词缺失的终极解决方案下一篇高性能Markdown解析器深度解析marked.js的架构设计与企业级应用实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考