【排序算法】八大经典排序算法详解

排序算法是盘算机科学中最根本且应用最广泛的焦点算法之一。本文将深入剖析八种经典排序算法的原理、实现方式及实用场景，帮助读者全面把握排序算法的焦点知识。

---

一、直接选择排序（Selection Sort）

算法头脑

通过不停选择剩余元素中的最小值，将其与当前未排序部分的起始位置交换，徐徐构建有序序列。
算法步调

• 从未排序序列中找到最小元素
  
• 将该元素与未排序序列的起始位置元素交换
  
• 将已排序序列的界限向右移动一位
  
• 重复上述过程直到整个序列有序
  

1. def selection_sort(arr):
2.     for i in range(len(arr)):
3.         min_idx = i
4.         for j in range(i+1, len(arr)):
5.             if arr[j] < arr[min_idx]:
6.                 min_idx = j
7.         arr[i], arr[min_idx] = arr[min_idx], arr[i]

复制代码

特性分析

• 时间复杂度：O(n²)（始终举行n(n-1)/2次比力）
  
• 空间复杂度：O(1)
  
• 稳固性：不稳固（交换大概粉碎原有顺序）
  
• 实用场景：讲授演示、数据量极小时利用
  

---

二、堆排序（Heap Sort）

算法头脑

利用堆这种数据布局的特性，通过构建大顶堆实现排序，将最大值依次交换到数组末端。
关键步调

• 建堆：从最后一个非叶子节点开始调解，构建大顶堆
  
• 排序阶段：
  
  
  
  • 交换堆顶与当前末端元素
    
  • 堆巨细减1
    
  • 调解新堆顶使其满意堆性子
    
  
  

1. def heapify(arr, n, i):
2.     largest = i
3.     l = 2 * i + 1
4.     r = 2 * i + 2
5.     if l < n and arr[l] > arr[largest]:
6.         largest = l
7.     if r < n and arr[r] > arr[largest]:
8.         largest = r
9.     if largest != i:
10.         arr[i], arr[largest] = arr[largest], arr[i]
11.         heapify(arr, n, largest)
13. def heap_sort(arr):
14.     n = len(arr)
15.     # 建堆
16.     for i in range(n//2-1, -1, -1):
17.         heapify(arr, n, i)
18.     # 排序
19.     for i in range(n-1, 0, -1):
20.         arr[i], arr[0] = arr[0], arr[i]
21.         heapify(arr, i, 0)

复制代码

特性分析

• 时间复杂度：O(n log n)
  
• 空间复杂度：O(1)
  
• 稳固性：不稳固
  
• 上风：恰当处置惩罚海量数据，不必要递归栈
  
• 应用场景：及时数据流处置惩罚、优先级队列实现
  

---

三、直接插入排序（Insertion Sort）

算法头脑

将待排序元素逐个插入到已排序序列的恰当位置，雷同整理扑克牌的过程。
算法步调

• 从第一个元素开始视为已排序序列
  
• 取出下一个元素，在已排序序列中从后向前扫描
  
• 找到第一个小于便是当前元素的节点，插入厥后
  
• 重复步调2-3直到全部元素处置惩罚完成
  

1. def insertion_sort(arr):
2.     for i in range(1, len(arr)):
3.         key = arr[i]
4.         j = i-1
5.         while j >=0 and key < arr[j] :
6.             arr[j+1] = arr[j]
7.             j -= 1
8.         arr[j+1] = key

复制代码

特性分析

• 最佳时间复杂度：O(n)（已排序环境）
  
• 均匀时间复杂度：O(n²)
  
• 空间复杂度：O(1)
  
• 稳固性：稳固
  
• 实用场景：小规模数据（n ≤ 1000）、根本有序数据
  

---

四、希尔排序（Shell Sort）

算法头脑

通过将原始列表分割成多个子序枚举行插入排序，随着增量逐渐减小，终极实现团体有序。
焦点概念

• 增量序列：确定子序列分别方式的隔断序列（常用Hibbard增量）
  
• 分组插入：对每个增量隔断形成的子序枚举行插入排序
  

1. def shell_sort(arr):
2.     n = len(arr)
3.     gap = n // 2
4.     while gap > 0:
5.         for i in range(gap, n):
6.             temp = arr[i]
7.             j = i
8.             while j >= gap and arr[j-gap] > temp:
9.                 arr[j] = arr[j-gap]
10.                 j -= gap
11.             arr[j] = temp
12.         gap //= 2

复制代码

特性分析

• 时间复杂度：O(n^1.3) ~ O(n²)（取决于增量序列）
  
• 空间复杂度：O(1)
  
• 稳固性：不稳固
  
• 上风：中等规模数据高效排序
  
• 汗青意义：第一个突破O(n²)时间复杂度的排序算法
  

---

五、冒泡排序（Bubble Sort）

算法头脑

通过相邻元素的比力和交换，使较大元素逐渐"浮"到数列顶端。
优化计谋

• 提前停止：设置交换标志位检测是否已有序
  
• 界限优化：记录最后一次交换位置，淘汰无效比力
  

1. def bubble_sort(arr):
2.     n = len(arr)
3.     for i in range(n):
4.         swapped = False
5.         for j in range(0, n-i-1):
6.             if arr[j] > arr[j+1]:
7.                 arr[j], arr[j+1] = arr[j+1], arr[j]
8.                 swapped = True
9.         if not swapped:
10.             break

复制代码

特性分析

• 最佳时间复杂度：O(n)（已排序环境）
  
• 均匀时间复杂度：O(n²)
  
• 空间复杂度：O(1)
  
• 稳固性：稳固
  
• 应用代价：算法讲授、简单场景应用
  

---

六、快速排序（Quick Sort）

算法头脑

采取分治计谋，通过选定基准元素将数组分别为两个子数组，递归排序。
关键步调

• 基准选择：通常选第一个/中心/随机元素
  
• 分区操纵：将小于基准的元素放在左侧，大于的放在右侧
  
• 递归处置惩罚：对左右子数组重复上述过程
  

1. def quick_sort(arr):
2.     if len(arr) <= 1:
3.         return arr
4.     pivot = arr[len(arr)//2]
5.     left = [x for x in arr if x < pivot]
6.     middle = [x for x in arr if x == pivot]
7.     right = [x for x in arr if x > pivot]
8.     return quick_sort(left) + middle + quick_sort(right)

复制代码

特性分析

• 均匀时间复杂度：O(n log n)
  
• 最坏时间复杂度：O(n²)（已排序数组+选择首元素为基准）
  
• 空间复杂度：O(log n)（递归栈深度）
  
• 稳固性：不稳固
  
• 优化方向：三数取中法、尾递归优化、小数组切换插入排序
  

---

七、归并排序（Merge Sort）

算法头脑

典范的分治算法，将数组递归分割到最小单位后归并有序子数组。
焦点操纵

• 分割阶段：递归地将数组二分至单个元素
  
• 归并阶段：将两个有序数组归并为新的有序数组
  

1. def merge_sort(arr):
2.     if len(arr) > 1:
3.         mid = len(arr)//2
4.         L = arr[:mid]
5.         R = arr[mid:]
6.         merge_sort(L)
7.         merge_sort(R)
8.         
9.         i = j = k = 0
10.         while i < len(L) and j < len(R):
11.             if L[i] < R[j]:
12.                 arr[k] = L[i]
13.                 i += 1
14.             else:
15.                 arr[k] = R[j]
16.                 j += 1
17.             k += 1
18.         
19.         while i < len(L):
20.             arr[k] = L[i]
21.             i += 1
22.             k += 1
23.         
24.         while j < len(R):
25.             arr[k] = R[j]
26.             j += 1
27.             k += 1

复制代码

特性分析

• 时间复杂度：O(n log n)
  
• 空间复杂度：O(n)
  
• 稳固性：稳固
  
• 上风：恰当链表布局、外部排序
  
• 应用场景：大数据排序（内存不敷时利用外部归并）
  

---

八、基数排序（Radix Sort）

算法头脑

按位分割的非比力排序，从最低位（LSD）或最高位（MSD）开始举行多轮排序。
执行步调

• 初始化10个桶（0-9）
  
• 从最低位到最高位依次举行：
  
  
  
  • 分配：按当前位数字将元素放入对应桶
    
  • 收集：按桶顺序将元素放回原数组
    
  
  
• 重复直随处置惩罚完全部位数
  

1. def radix_sort(arr):
2.     max_num = max(arr)
3.     exp = 1
4.     while max_num // exp > 0:
5.         buckets = [[] for _ in range(10)]
6.         for num in arr:
7.             buckets[(num // exp) % 10].append(num)
8.         arr = [num for bucket in buckets for num in bucket]
9.         exp *= 10
10.     return arr

复制代码

特性分析

• 时间复杂度：O(nk)（k为最大位数）
  
• 空间复杂度：O(n+k)
  
• 稳固性：稳固（依赖桶排序的稳固性）
  
• 限定条件：仅实用于整数排序
  
• 优化本领：结合计数排序、动态确定位数
  

---

九、排序算法对比

算法优缺点对比

算法最佳场景上风范围性稳固性直接选择排序讲授演示实现简单服从低下不稳固堆排序内存敏感的大数据无递归栈溢出风险缓存局部性差不稳固插入排序小规模有序数据自顺应性能好大规模数据服从骤降稳固希尔排序中等规模随机数据突破O(n²)屏障增量序列选择复杂不稳固冒泡排序检测数据有序性实现简单服从最低稳固快速排序通用排序场景均匀性能最优最坏环境性能差不稳固归并排序大数据外部排序稳固且时间复杂度优空间复杂度高稳固基数排序固定范围整数排序线性时间复杂度数据类型限定稳固算法复杂度对比

总结

明白这些根本排序算法不但是把握数据布局的关键，更是优化实际工程题目的根本。发起读者通过可视化工具（如 Visualgo）观察算法的执行过程，并尝试本身实现差别版本的排序算法来加深明白。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告