LeetCode 912：排序数组 | 排序算法全面解析

LeetCode 912排序数组 | 排序算法全面解析引言排序数组Sort an Array是 LeetCode 第 912 题难度为 Medium。题目要求将给定数组排序并返回。虽然这是一个看似简单的问题但题目对时间和空间复杂度有要求需要我们实现各种排序算法并分析其性能特点。排序是计算机科学中最基础的问题之一也是面试中的高频考点。本文将全面解析各种排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序等分析它们的时间复杂度、空间复杂度和稳定性特点。排序算法分类排序算法 Overview排序算法可以分为两大类比较排序和非比较排序。比较排序通过比较元素之间的大小关系来确定顺序而非比较排序不通过比较来排序。比较排序的时间复杂度下界是 O(n log n)而非比较排序可以达到 O(n)。但非比较排序对待排序数据有特殊要求如计数排序要求数据范围已知且不太大。常见排序算法常见排序算法包括O(n²) 冒泡排序、选择排序、插入排序O(n log n) 归并排序、快速排序、堆排序O(n) 计数排序、桶排序、基数排序冒泡排序算法原理冒泡排序是最简单的排序算法之一。它重复地遍历数组比较相邻的两个元素如果顺序错误就交换。通过多次遍历最终使数组有序。def bubble_sort(nums): n len(nums) for i in range(n): swapped False for j in range(0, n - i - 1): if nums[j] nums[j 1]: nums[j], nums[j 1] nums[j 1], nums[j] swapped True if not swapped: break return nums冒泡排序的名称来源于算法执行过程中较小的元素逐渐冒泡到数组顶端的过程。复杂度分析时间复杂度最好 O(n)最坏 O(n²)平均 O(n²)空间复杂度O(1)稳定性稳定冒泡排序的最好情况是数组已经有序只需要一次遍历就能检测到没有交换从而提前终止。选择排序算法原理选择排序首先在未排序序列中找到最小或最大元素放到排序序列的起始位置然后从剩余未排序序列中继续寻找最小或最大元素放到已排序序列的末尾。def selection_sort(nums): n len(nums) for i in range(n): min_idx i for j in range(i 1, n): if nums[j] nums[min_idx]: min_idx j nums[i], nums[min_idx] nums[min_idx], nums[i] return nums复杂度分析时间复杂度O(n²)最好和最坏都是空间复杂度O(1)稳定性不稳定选择排序的不稳定性来源于它可能改变相同元素的相对位置。例如在 [2, 2, 1] 中第一次会选择 1 与第一个 2 交换导致相同元素的相对顺序改变。插入排序算法原理插入排序类似于整理扑克牌的过程。将数组分为已排序和未排序两部分每次从未排序部分取出一个元素在已排序部分找到合适的位置插入。def insertion_sort(nums): for i in range(1, len(nums)): key nums[i] j i - 1 while j 0 and nums[j] key: nums[j 1] nums[j] j - 1 nums[j 1] key return nums复杂度分析时间复杂度最好 O(n)最坏 O(n²)平均 O(n²)空间复杂度O(1)稳定性稳定插入排序在数组基本有序时效率很高因为只需要很少的移动操作。在实际排序中插入排序经常与其他排序算法结合使用如快速排序的小数组排序阶段。归并排序算法原理归并排序采用分治法思想。将数组递归地分成两半分别排序后合并。由于需要合并两个有序数组需要额外的 O(n) 空间。def merge_sort(nums): if len(nums) 1: return nums mid len(nums) // 2 left merge_sort(nums[:mid]) right merge_sort(nums[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)稳定性稳定归并排序的缺点是需要额外的 O(n) 空间但优点是稳定性好且在外部排序数据量太大无法一次性放入内存中有重要应用。快速排序算法原理快速排序同样采用分治法。首先选择一个基准元素pivot将数组分为两部分小于 pivot 的元素和大于 pivot 的元素。然后递归地对两部分进行排序。def quick_sort(nums): if len(nums) 1: return nums pivot nums[len(nums) // 2] left [x for x in nums if x pivot] middle [x for x in nums if x pivot] right [x for x in nums if x pivot] return quick_sort(left) middle quick_sort(right)原地版本的快速排序更加空间高效def quick_sort_inplace(nums, low0, highNone): if high is None: high len(nums) - 1 if low high: pivot_idx partition(nums, low, high) quick_sort_inplace(nums, low, pivot_idx - 1) quick_sort_inplace(nums, pivot_idx 1, high) def partition(nums, low, high): pivot nums[high] i low - 1 for j in range(low, high): if nums[j] pivot: i 1 nums[i], nums[j] nums[j], nums[i] nums[i 1], nums[high] nums[high], nums[i 1] return i 1复杂度分析时间复杂度最好 O(n log n)最坏 O(n²)平均 O(n log n)空间复杂度O(log n)递归栈稳定性不稳定快速排序的最坏情况发生在数组已经有序或完全逆序时。为避免最坏情况通常采用随机选择基准或三数取中法。堆排序算法原理堆排序使用二叉堆数据结构。首先将数组构建成最大堆然后反复提取最大元素并调整堆。import heapq def heap_sort(nums): heapq.heapify(nums) return [heapq.heappop(nums) for _ in range(len(nums))]原地版本的堆排序def heap_sort_inplace(nums): n len(nums) def heapify(nums, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and nums[left] nums[largest]: largest left if right n and nums[right] nums[largest]: largest right if largest ! i: nums[i], nums[largest] nums[largest], nums[i] heapify(nums, n, largest) for i in range(n // 2 - 1, -1, -1): heapify(nums, n, i) for i in range(n - 1, 0, -1): nums[0], nums[i] nums[i], nums[0] heapify(nums, i, 0) return nums复杂度分析时间复杂度O(n log n)最好、最坏、平均都是空间复杂度O(1)稳定性不稳定堆排序的优点是不论输入数据如何时间复杂度都是 O(n log n)且是原地排序。缺点是缓存命中率和实际运行常数可能不如快速排序。计数排序算法原理计数排序是一种非比较排序适用于范围不大的整数排序。统计每个元素出现的次数然后根据计数将元素放回原数组。def counting_sort(nums): if not nums: return nums min_val, max_val min(nums), max(nums) count [0] * (max_val - min_val 1) for num in nums: count[num - min_val] 1 result [] for i, c in enumerate(count): result.extend([i min_val] * c) return result复杂度分析时间复杂度O(n k)其中 k 是数据范围空间复杂度O(k)稳定性稳定需要额外处理计数排序在数据范围不大时非常高效可以达到线性时间复杂度。算法对比时间复杂度对比算法最好最坏平均冒泡排序O(n)O(n²)O(n²)选择排序O(n²)O(n²)O(n²)插入排序O(n)O(n²)O(n²)归并排序O(n log n)O(n log n)O(n log n)快速排序O(n log n)O(n²)O(n log n)堆排序O(n log n)O(n log n)O(n log n)计数排序O(n k)O(n k)O(n k)空间复杂度对比算法空间复杂度冒泡排序O(1)选择排序O(1)插入排序O(1)归并排序O(n)快速排序O(log n)堆排序O(1)计数排序O(k)稳定性对比稳定排序冒泡排序、插入排序、归并排序、计数排序不稳定排序选择排序、快速排序、堆排序总结排序算法是算法学习的基础。不同排序算法有各自的优缺点适用于不同场景数据基本有序时插入排序效率最高需要稳定排序时归并排序是首选通用场景下快速排序通常是最佳选择数据范围已知且不大时计数排序可以达到线性时间理解各种排序算法的原理、复杂度和特点对于提升算法能力和应对面试都有重要意义。