数据结构之八大排序算法

### 八大经典排序算法详解 #### 插入排序 直接插入排序是一种简单直观的排序方法。其基本思想是将待排序的数据逐个取出，按照关键字大小依次插入到已排序序列中的适当位置，直到全部数据都插入完毕为止[^1]。 ```python def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr ``` --- #### 归并排序 归并排序基于分治策略，它将数组分为两部分分别递归排序后再合并成整体有序的结果。这种方法的时间复杂度为 \(O(n \log n)\)，空间复杂度较高，因为需要额外的空间来存储临时数组[^3]。 ```python def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left_half = merge_sort(arr[:mid]) right_half = merge_sort(arr[mid:]) return merge(left_half, right_half) 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)\)[^2]。 ```python 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) 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) return arr ``` --- #### 希尔排序 希尔排序是对插入排序的一种优化改进版，通过设定不同的步长（增量）对子序列进行多次插入排序，最后再以步长为 1 进行一次完整的插入排序[^4]。 ```python def shell_sort(arr): gap = len(arr) // 2 while gap > 0: for i in range(gap, len(arr)): 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 ``` --- #### 快速排序 快速排序也是一种经典的分治法应用，选取一个基准值划分数组为两个子区间，使得左侧小于等于基准值而右侧大于基准值，之后递归处理这两个子区间。 ```python 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) ``` --- #### 计数排序 计数排序属于非比较类排序算法之一，适用于范围较小且整数值的情况。它的核心思想是统计每个元素出现次数并通过累加计算出它们的位置。 ```python def counting_sort(arr): max_val = max(arr) min_val = min(arr) count_range = max_val - min_val + 1 count_arr = [0] * count_range output = [0] * len(arr) for num in arr: count_arr[num - min_val] += 1 for i in range(1, len(count_arr)): count_arr[i] += count_arr[i - 1] for num in reversed(arr): index = count_arr[num - min_val] - 1 output[index] = num count_arr[num - min_val] -= 1 return output ``` --- #### 桶排序 桶排序适合用于分布均匀的数据集。先根据输入数据的特点分配若干个桶，然后对每个桶内的数据单独执行其他排序方式（通常选插入排序）。最后按顺序收集各桶的内容即可获得全局有序列表。 ```python import math def bucket_sort(arr): buckets_num = round(math.sqrt(len(arr))) max_value = max(arr) buckets = [[] for _ in range(buckets_num)] for value in arr: idx = int(value / (max_value + 1) * buckets_num) buckets[idx].append(value) sorted_buckets = [] for bucket in buckets: sorted_buckets.extend(insertion_sort(bucket)) return sorted_buckets ``` --- #### 基数排序 基数排序针对多关键字问题设计了一种特殊的解决办法——低位优先原则。即从最低有效位开始逐一整理直至最高位结束。 ```python def radix_sort(arr): max_digits = len(str(max(arr))) for digit in range(max_digits): buckets = [[] for _ in range(10)] for number in arr: d = (number // 10 ** digit) % 10 buckets[d].append(number) arr.clear() for b in buckets: arr.extend(b) return arr ``` ---