当前位置：首页 > news >正文

经典排序算法合集（下）

news 2025/5/30 1:16:37

六. 堆排序（Heap Sort）

1、原理

堆排序（Heap Sort）是一种基于二叉堆数据结构的原地比较排序算法，核心思想是将数组视为完全二叉树，构建最大堆（或最小堆），逐步提取堆顶元素实现排序。具体步骤如下：

建堆（Heapify）：将无序数组调整为最大堆，使每个父节点 ≥ 子节点。
交换与调整：将堆顶元素（最大值）与末尾元素交换，堆长度减 1，重新调整剩余元素为最大堆。
重复：重复交换与调整，直到堆长度为 1。

关键操作示意图：

原始数组： [3, 6, 1, 5, 9]

建堆 → [9, 6, 3, 1, 5]

交换堆顶与末尾 → [5, 6, 3, 1｜9]

重新调整 → [6，5，3，1 | 9]

重复直至有序 → [1, 3, 5, 6, 9]

图解：

2. 性能分析

时间复杂度：
- 建堆：O(n)（非逐次插入，而是从中间节点向上调整）。
- 排序阶段：每次调整堆 O(log n)，共 n-1 次 → 整体 O(n log n)。
空间复杂度：O(1)（原地排序，无需额外空间）。
稳定性：不稳定（交换堆顶与末尾元素可能破坏相同元素顺序）。

3、适用场景

大规模数据排序：时间复杂度 O(n log n)，适合数据量大的场景。
内存限制严格：原地排序，无需额外空间（优于归并排序）。
实时系统需求：时间复杂度稳定，最坏时间复杂度仍为 O(n log n)（优于快速排序的最坏 O(n²)）。
动态数据流：堆结构适合处理实时更新的 Top-K 问题（如求前 10% 最大值）。

不适用场景：

需要稳定排序时。
数据量较小时（插入排序更高效）。

4、代码实现

Python:

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[i], arr[0] = arr[0], arr[i]  # 交换堆顶与末尾  heapify(arr, i, 0)               # 调整剩余堆  return arr  def heapify(arr, n, root):  largest = root  left = 2 * root + 1  right = 2 * root + 2  if left < n and arr[left] > arr[largest]:  largest = left  if right < n and arr[right] > arr[largest]:  largest = right  if largest != root:  arr[root], arr[largest] = arr[largest], arr[root]  heapify(arr, n, largest)  # 递归调整子树  ## 调用
arr = [12, 11, 13, 5, 6, 7]  
sorted_arr = heap_sort(arr)  
print("排序结果:", sorted_arr)  # 输出: [5, 6, 7, 11, 12, 13]

golang:

func heapSort(arr []int) {  n := len(arr)  // 建堆  for i := n/2 - 1; i >= 0; i-- {  heapify(arr, n, i)  }  // 逐个提取最大值  for i := n - 1; i > 0; i-- {  arr[0], arr[i] = arr[i], arr[0]  // 交换堆顶与末尾  heapify(arr, i, 0)               // 调整剩余堆  }  
}  func heapify(arr []int, n, root int) {  largest := root  left := 2*root + 1  right := 2*root + 2  if left < n && arr[left] > arr[largest] {  largest = left  }  if right < n && arr[right] > arr[largest] {  largest = right  }  if largest != root {  arr[root], arr[largest] = arr[largest], arr[root]  heapify(arr, n, largest)  }  
}  // 调用示例  
func main() {  arr := []int{12, 11, 13, 5, 6, 7}  heapSort(arr)  fmt.Println("排序结果:", arr)  // 输出: [5 6 7 11 12 13]  
}

php:

function heapSort(&$arr) {  $n = count($arr);  // 建堆  for ($i = intdiv($n, 2) - 1; $i >= 0; $i--) {  heapify($arr, $n, $i);  }  // 逐个提取最大值  for ($i = $n - 1; $i > 0; $i--) {  list($arr[0], $arr[$i]) = array($arr[$i], $arr[0]);  heapify($arr, $i, 0);  }  
}  function heapify(&$arr, $n, $root) {  $largest = $root;  $left = 2 * $root + 1;  $right = 2 * $root + 2;  if ($left < $n && $arr[$left] > $arr[$largest]) {  $largest = $left;  }  if ($right < $n && $arr[$right] > $arr[$largest]) {  $largest = $right;  }  if ($largest != $root) {  list($arr[$root], $arr[$largest]) = array($arr[$largest], $arr[$root]);  heapify($arr, $n, $largest);  }  
}  // 调用示例  
$arr = [12, 11, 13, 5, 6, 7];  
heapSort($arr);  
echo "排序结果: " . implode(", ", $arr);  // 输出: 5, 6, 7, 11, 12, 13

java:

public static void heapSort(int[] arr) {  int n = arr.length;  // 建堆  for (int i = n / 2 - 1; i >= 0; i--) {  heapify(arr, n, i);  }  // 逐个提取最大值  for (int i = n - 1; i > 0; i--) {  int temp = arr[0];  arr[0] = arr[i];  arr[i] = temp;  heapify(arr, i, 0);  }  
}  private static void heapify(int[] arr, int n, int root) {  int largest = root;  int left = 2 * root + 1;  int right = 2 * root + 2;  if (left < n && arr[left] > arr[largest]) {  largest = left;  }  if (right < n && arr[right] > arr[largest]) {  largest = right;  }  if (largest != root) {  int temp = arr[root];  arr[root] = arr[largest];  arr[largest] = temp;  heapify(arr, n, largest);  }  
}  // 调用示例  
public static void main(String[] args) {  int[] arr = {12, 11, 13, 5, 6, 7};  heapSort(arr);  System.out.println("排序结果: " + Arrays.toString(arr));  // 输出: [5, 6, 7, 11, 12, 13]  
}

七、计数排序（Counting Sort）

1、原理

计数排序（Counting Sort）是一种非比较的稳定排序算法，适用于整数数据且范围较小的场景。核心思想是通过统计元素出现次数直接确定元素的位置。具体步骤如下：

确定范围：找到数组中的最大值 max 和最小值 min，计算范围 k = max - min + 1。
计数数组：创建长度为 k 的计数数组，统计每个元素出现的次数。
累加计数：将计数数组转换为前缀和数组，表示每个元素的最终位置。
反向填充：从原数组末尾向前遍历，根据计数数组确定元素位置，确保稳定性。

示例：

输入数组：[4, 2, 2, 8, 3, 3, 1]（最小值 1，最大值 8，范围 k = 8）
计数数组统计次数：[1:1, 2:2, 3:2, 4:1, 8:1]
累加计数,每个元素的最终位置：[1:1, 2:3, 3:5, 4:6, 8:7]
反向填充结果：[1, 2, 2, 3, 3, 4, 8]

2、性能分析

时间复杂度：O(n + k)
- n 是元素个数，k 是数据范围（max - min + 1）。
- 当 k 接近 n 时，性能接近线性。
空间复杂度：O(n + k)（需要计数数组和结果数组）。
稳定性：稳定（反向填充保证相同元素顺序不变）。

3、适用场景

整数排序：仅适用于整数（或可映射为整数的数据）。
范围较小：k 远小于 n（如年龄、成绩、IP地址等）。
稳定性需求：需保持相同元素的原始顺序。
线性时间需求：数据量大但范围可控时优于 O(n log n) 算法。

不适用场景：

数据范围过大（如 k > 10^6）。
非整数数据（需额外处理映射关系）。

4、代码实现

核心逻辑

统计频率：将元素映射到计数数组的索引，统计出现次数。
累加计数：将频率转换为元素在结果数组中的最后一个位置。
反向填充：从原数组末尾开始遍历，确保相同元素的稳定性。

python:

def counting_sort(arr):  if not arr:  return []  min_val, max_val = min(arr), max(arr)  k = max_val - min_val + 1  count = [0] * k  for num in arr:  count[num - min_val] += 1  # 累加计数数组  for i in range(1, k):  count[i] += count[i - 1]  # 反向填充结果数组  result = [0] * len(arr)  for num in reversed(arr):  idx = count[num - min_val] - 1  result[idx] = num  count[num - min_val] -= 1  return result

go：

func countingSort(arr []int) []int {  if len(arr) == 0 {  return arr  }  minVal, maxVal := arr[0], arr[0]  for _, num := range arr {  if num < minVal {  minVal = num  }  if num > maxVal {  maxVal = num  }  }  k := maxVal - minVal + 1  count := make([]int, k)  for _, num := range arr {  count[num - minVal]++  }  // 累加计数数组  for i := 1; i < k; i++ {  count[i] += count[i - 1]  }  // 反向填充  result := make([]int, len(arr))  for i := len(arr) - 1; i >= 0; i-- {  num := arr[i]  idx := count[num - minVal] - 1  result[idx] = num  count[num - minVal]--  }  return result  
}

php: [4, 2, 2, 8, 3, 3, 1]

function countingSort($arr) {  if (empty($arr)) {  return [];  }  $minVal = min($arr);  $maxVal = max($arr);  $k = $maxVal - $minVal + 1;  $count = array_fill(0, $k, 0);  foreach ($arr as $num) {  $count[$num - $minVal]++;  }  // 累加计数数组  for ($i = 1; $i < $k; $i++) {  $count[$i] += $count[$i - 1];  }  // 反向填充  $result = array_fill(0, count($arr), 0);  for ($i = count($arr) - 1; $i >= 0; $i--) {  $num = $arr[$i];  $idx = $count[$num - $minVal] - 1;  $result[$idx] = $num;  $count[$num - $minVal]--;  }  return $result;  
}

java:

public static int[] countingSort(int[] arr) {  if (arr.length == 0) return arr;  int minVal = arr[0], maxVal = arr[0];  for (int num : arr) {  if (num < minVal) minVal = num;  if (num > maxVal) maxVal = num;  }  int k = maxVal - minVal + 1;  int[] count = new int[k];  for (int num : arr) {  count[num - minVal]++;  }  // 累加计数数组  for (int i = 1; i < k; i++) {  count[i] += count[i - 1];  }  // 反向填充  int[] result = new int[arr.length];  for (int i = arr.length - 1; i >= 0; i--) {  int num = arr[i];  int idx = count[num - minVal] - 1;  result[idx] = num;  count[num - minVal]--;  }  return result;  
}

八、桶排序（Bucket Sort）

1、原理

桶排序是一种非比较型排序算法，通过将数据分配到多个“桶”中，每个桶单独排序后再合并。其核心步骤包括：

分桶：根据元素的范围或分布，将数据分配到有限数量的桶中。
桶内排序：对每个非空桶内的数据进行排序（通常使用插入排序等简单算法）。
合并结果：按桶的顺序将数据合并回原数组。

关键特点：

适用于数据分布均匀且范围已知的场景。
时间复杂度依赖数据分布，理想情况下接近线性。
属于**“空间换时间”**的排序策略。

实现关键点：

桶的数量通常取 √n 或根据数据分布调整。
桶的范围需覆盖数据的最小值和最大值。

示例：

输入数组：[0.42, 0.32, 0.87, 0.15, 0.63]（范围 [0,1)，分 5 个桶）
分桶结果：

Bucket 0: [0.15]
Bucket 1: [0.32, 0.42]
Bucket 4: [0.63, 0.87]
合并后：[0.15, 0.32, 0.42, 0.63, 0.87]

2、性能分析

时间复杂度：
- 平均：O(n + k)（k 为桶数，假设数据均匀分布）。
- 最坏：O(n²)（所有元素集中到一个桶中）。
空间复杂度：O(n + k)（需额外空间存储桶）。
稳定性：稳定（取决于桶内排序算法的稳定性）。

3、适用场景

数据分布均匀：元素能均匀分散到各个桶中（如大量 [0,1) 的浮点数）。
范围已知：数据的最小值和最大值可明确确定。
外部排序：适用于数据量大且内存受限的场景（分桶后分批处理），比如像素排序。

不适用场景：

数据分布不均匀（如大部分元素集中在少数桶中）。
数据范围过大且未知（难以合理分桶）。

4、代码实现

python:

def bucket_sort(arr, bucket_size=5):  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:  idx = int((num - min_val) // bucket_size)  buckets[idx].append(num)  # 桶内排序（假设使用插入排序）  sorted_arr = []  for bucket in buckets:  if not bucket:  continue  # 可替换为其他排序算法  bucket = sorted(bucket)  # Python内置的Timsort  sorted_arr.extend(bucket)  return sorted_arr  # 调用示例  
arr = [0.42, 0.32, 0.87, 0.15, 0.63]  
sorted_arr = bucket_sort(arr)  
print("排序结果:", sorted_arr)  # 输出: [0.15, 0.32, 0.42, 0.63, 0.87]

golang:

package main  
import (  "fmt"  "sort"  
)  func bucketSort(arr []float64, bucketSize int) []float64 {  if len(arr) == 0 {  return arr  }  // 确定数据范围  minVal, maxVal := arr[0], arr[0]  for _, num := range arr {  if num < minVal {  minVal = num  }  if num > maxVal {  maxVal = num  }  }  bucketCount := int((maxVal - minVal)/float64(bucketSize)) + 1  buckets := make([][]float64, bucketCount)  // 分桶  for _, num := range arr {  idx := int((num - minVal) / float64(bucketSize))  buckets[idx] = append(buckets[idx], num)  }  // 桶内排序并合并  sortedArr := make([]float64, 0)  for _, bucket := range buckets {  if len(bucket) == 0 {  continue  }  sort.Float64s(bucket)  // Go内置的快速排序  sortedArr = append(sortedArr, bucket...)  }  return sortedArr  
}  // 调用示例  
func main() {  arr := []float64{0.42, 0.32, 0.87, 0.15, 0.63}  sortedArr := bucketSort(arr, 1)  // 使用1作为桶大小  fmt.Println("排序结果:", sortedArr)  // 输出: [0.15 0.32 0.42 0.63 0.87]  
}

php:

function bucketSort($arr, $bucketSize = 5) {  if (empty($arr)) {  return [];  }  $minVal = min($arr);  $maxVal = max($arr);  $bucketCount = floor(($maxVal - $minVal) / $bucketSize) + 1;  $buckets = array_fill(0, $bucketCount, []);  // 分桶  foreach ($arr as $num) {  $idx = floor(($num - $minVal) / $bucketSize);  array_push($buckets[$idx], $num);  }  // 桶内排序并合并  $sortedArr = [];  foreach ($buckets as $bucket) {  if (empty($bucket)) {  continue;  }  sort($bucket);  // PHP内置的快速排序  $sortedArr = array_merge($sortedArr, $bucket);  }  return $sortedArr;  
}  // 调用示例  
$arr = [0.42, 0.32, 0.87, 0.15, 0.63];  
$sortedArr = bucketSort($arr, 1);  
echo "排序结果: " . implode(", ", $sortedArr);  // 输出: 0.15, 0.32, 0.42, 0.63, 0.87

java:

import java.util.ArrayList;  
import java.util.Collections;  
import java.util.List;  public class BucketSort {  public static List<Double> bucketSort(List<Double> arr, int bucketSize) {  if (arr.isEmpty()) return arr;  // 确定数据范围  double minVal = Collections.min(arr);  double maxVal = Collections.max(arr);  int bucketCount = (int) Math.floor((maxVal - minVal) / bucketSize) + 1;  List<List<Double>> buckets = new ArrayList<>(bucketCount);  for (int i = 0; i < bucketCount; i++) {  buckets.add(new ArrayList<>());  }  // 分桶  for (Double num : arr) {  int idx = (int) Math.floor((num - minVal) / bucketSize);  buckets.get(idx).add(num);  }  // 桶内排序并合并  List<Double> sortedArr = new ArrayList<>();  for (List<Double> bucket : buckets) {  if (bucket.isEmpty()) continue;  Collections.sort(bucket);  // Java内置的归并排序  sortedArr.addAll(bucket);  }  return sortedArr;  }  // 调用示例  public static void main(String[] args) {  List<Double> arr = List.of(0.42, 0.32, 0.87, 0.15, 0.63);  List<Double> sortedArr = bucketSort(arr, 1);  System.out.println("排序结果: " + sortedArr);  // 输出: [0.15, 0.32, 0.42, 0.63, 0.87]  }  
}

九、基数排序（Radix Sort）

1、原理

基数排序（Radix Sort）是一种非比较型整数排序算法，按位将元素分配到不同的“桶”中，逐步从最低位到最高位（LSD）或最高位到最低位（MSD）完成排序。每次分桶操作必须使用稳定排序（如计数排序），以确保高位排序时低位的相对顺序不变。

基数排序是一种基于数字每一位进行排序的算法。它从最低位开始，依次对每一位进行排序，直到最高位。对于整数，从个位开始，将所有数字按照个位数字放入相应的“桶”中，然后按桶的顺序重新收集数据；接着对十位进行同样的操作，以此类推，直到处理完最高位。例如，对于数组[123, 456, 789, 111, 222]，先按个位数字排序，再按十位数字排序，最后按百位数字排序，从而得到有序数组。

步骤：

确定最大位数：找到数组中最大数的位数（d），决定需要多少轮排序。
按位排序：从最低位（LSD）开始，对每一位进行稳定排序（如计数排序）。
合并结果：每轮排序后，重新合并桶中的元素到原数组。
重复直到最高位：完成所有位的排序后，数组整体有序。

2、性能分析

时间复杂度：
- 平均/最坏/最好情况均为 O(d(n + k))*，其中：
  - d：最大位数
  - n：数据量
  - k：基数范围（十进制时为 10）
空间复杂度：O(n + k)，需额外空间存储桶或计数数组。
稳定性：稳定（依赖子排序算法的稳定性）。

3、适用场景

整数或字符串排序：适合处理固定长度元素（如手机号、日期）。
数据范围小但规模大：当位数 d 较小且 n 较大时，效率优于 O(n log n) 算法。
稳定性要求高：如保留相同键值的原始顺序。

4、代码实现

python : (含负数实现)

def radix_sort(arr):if not arr:return arr# 处理负数：转换为非负整数min_val = min(arr)offset = -min_val if min_val < 0 else 0arr = [num + offset for num in arr]max_num = max(arr)exp = 1while max_num // exp > 0:counting_sort(arr, exp)exp *= 10# 恢复原始数值if offset != 0:arr = [num - offset for num in arr]return arrdef counting_sort(arr, exp):n = len(arr)output = [0] * ncount = [0] * 10  # 十进制基数0-9# 统计当前位出现次数for num in arr:digit = (num // exp) % 10count[digit] += 1# 计算累加位置for i in range(1, 10):count[i] += count[i-1]# 反向填充保证稳定性for i in range(n-1, -1, -1):digit = (arr[i] // exp) % 10output[count[digit] - 1] = arr[i]count[digit] -= 1# 更新原数组for i in range(n):arr[i] = output[i]# 示例
nums = [-5, 10, -3, 2, 0]
print(radix_sort(nums))  # 输出：[-5, -3, 0, 2, 10]

go:

package mainimport ("fmt""math"
)func radixSort(arr []int) []int {if len(arr) == 0 {return arr}// 处理负数minVal := arr[0]for _, num := range arr {if num < minVal {minVal = num}}offset := 0if minVal < 0 {offset = -minValfor i := range arr {arr[i] += offset}}maxVal := arr[0]for _, num := range arr {if num > maxVal {maxVal = num}}for exp := 1; maxVal/exp > 0; exp *= 10 {countingSort(arr, exp)}// 恢复负数if offset != 0 {for i := range arr {arr[i] -= offset}}return arr
}func countingSort(arr []int, exp int) {n := len(arr)output := make([]int, n)count := make([]int, 10)for _, num := range arr {digit := (num / exp) % 10count[digit]++}for i := 1; i < 10; i++ {count[i] += count[i-1]}for i := n - 1; i >= 0; i-- {digit := (arr[i] / exp) % 10output[count[digit]-1] = arr[i]count[digit]--}copy(arr, output)
}func main() {nums := []int{-5, 10, -3, 2, 0}fmt.Println(radixSort(nums)) // 输出：[-5 -3 0 2 10]
}

java:

public class RadixSort {public static void radixSort(int[] arr) {if (arr.length == 0) return;// 处理负数int min = Arrays.stream(arr).min().getAsInt();int offset = min < 0 ? -min : 0;for (int i = 0; i < arr.length; i++) {arr[i] += offset;}int max = Arrays.stream(arr).max().getAsInt();for (int exp = 1; max / exp > 0; exp *= 10) {countingSort(arr, exp);}// 恢复负数if (offset != 0) {for (int i = 0; i < arr.length; i++) {arr[i] -= offset;}}}private static void countingSort(int[] arr, int exp) {int[] output = new int[arr.length];int[] count = new int[10];for (int num : arr) {int digit = (num / exp) % 10;count[digit]++;}for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}for (int i = arr.length - 1; i >= 0; i--) {int digit = (arr[i] / exp) % 10;output[count[digit] - 1] = arr[i];count[digit]--;}System.arraycopy(output, 0, arr, 0, arr.length);}public static void main(String[] args) {int[] nums = {-5, 10, -3, 2, 0};radixSort(nums);System.out.println(Arrays.toString(nums)); // 输出：[-5, -3, 0, 2, 10]}
}

查看全文

http://www.xdnf.cn/news/683965.html