排序算法是計(jì)算機(jī)科學(xué)中的基礎(chǔ)課題，無(wú)論是在日常開(kāi)發(fā)還是算法面試中都占據(jù)重要地位。本文將通過(guò)動(dòng)態(tài)圖解和詳細(xì)代碼，帶你全面掌握十種經(jīng)典排序算法。
一、冒泡排序（Bubble Sort）
原理：重復(fù)比較相鄰元素，將較大元素逐步“冒泡”至右側(cè)。
動(dòng)態(tài)圖解：
假設(shè)數(shù)組 [5,3,8,6,4]
第一輪：
5>3 → 交換 → [3,5,8,6,4]
5<8 → 保持
8>6 → 交換 → [3,5,6,8,4]
8>4 → 交換 → [3,5,6,4,8]
后續(xù)輪次繼續(xù)處理未排序部分。
代碼實(shí)現(xiàn)（Python）：`python
def bubble_sort(arr):
n = len(arr)
for i in range(n-1):
for j in range(n-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr`
二、選擇排序（Selection Sort）
原理：每次從未排序部分選擇最小元素，放到已排序序列末尾。
代碼實(shí)現(xiàn)：`python
def selectionsort(arr):
n = len(arr)
for i in range(n-1):
minidx = i
for j in range(i+1, n):
if arr[j] < arr[minidx]:
minidx = j
arr[i], arr[minidx] = arr[minidx], arr[i]
return arr`
三、插入排序（Insertion Sort）
原理：將每個(gè)元素插入到已排序序列的適當(dāng)位置。
動(dòng)態(tài)圖解：
初始：[5,3,8,6,4]
第一步：3插入5前 → [3,5,8,6,4]
第二步：8保持 → [3,5,8,6,4]
第三步：6插入5和8之間 → [3,5,6,8,4]
第四步：4插入3和5之間 → [3,4,5,6,8]
代碼實(shí)現(xiàn)：`python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr`
四、希爾排序（Shell Sort）
原理：改進(jìn)的插入排序，通過(guò)增量分組進(jìn)行預(yù)處理。
代碼實(shí)現(xiàn)：`python
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
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`
五、歸并排序（Merge Sort）
原理：分治策略，先遞歸分解數(shù)組，再合并有序子序列。
代碼實(shí)現(xiàn)：`python
def mergesort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = merge_sort(arr[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`
六、快速排序（Quick Sort）
原理：選取基準(zhǔn)值，將數(shù)組分為小于基準(zhǔn)和大于基準(zhǔn)的兩部分，遞歸排序。
動(dòng)態(tài)圖解：
數(shù)組 [5,3,8,6,4]，選擇基準(zhǔn)5：
分區(qū)過(guò)程：
3<5 → 放左側(cè)
8>5 → 放右側(cè)
6>5 → 放右側(cè)
4<5 → 放左側(cè)
得到 [3,4] 5 [8,6]
遞歸處理左右子數(shù)組。
代碼實(shí)現(xiàn)：`python
def quicksort(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 quicksort(left) + middle + quick_sort(right)`
七、堆排序（Heap Sort）
原理：構(gòu)建最大堆，反復(fù)取出堆頂元素完成排序。
代碼實(shí)現(xiàn)：`python
def heapify(arr, n, i):
largest = i
left = 2i + 1
right = 2i + 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[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr`
八、計(jì)數(shù)排序（Counting Sort）
原理：統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，按統(tǒng)計(jì)結(jié)果輸出有序序列。
代碼實(shí)現(xiàn)：`python
def countingsort(arr):
if not arr:
return []
maxval = max(arr)
count = [0] (max_val+1)
for num in arr:
count[num] += 1
result = []
for i in range(len(count)):
result.extend([i] count[i])
return result`
九、桶排序（Bucket Sort）
原理：將數(shù)據(jù)分到有限數(shù)量的桶中，每個(gè)桶單獨(dú)排序。
代碼實(shí)現(xiàn)：`python
def bucketsort(arr, bucketsize=5):
if not arr:
return []
minval, maxval = min(arr), max(arr)
bucketcount = (maxval - minval) // bucketsize + 1
buckets = [[] for in range(bucketcount)]
for num in arr:
buckets[(num - minval) // bucketsize].append(num)
result = []
for bucket in buckets:
result.extend(sorted(bucket))
return result`
十、基數(shù)排序（Radix Sort）
原理：按位數(shù)從低位到高位依次進(jìn)行穩(wěn)定排序。
動(dòng)態(tài)圖解：
數(shù)組 [170,45,75,90,802,24,2,66]
第一輪按個(gè)位排序：
桶0: 170,90
桶2: 802,2
桶4: 24
桶5: 45,75
桶6: 66
得到 [170,90,802,2,24,45,75,66]
第二輪按十位排序...
代碼實(shí)現(xiàn)：`python
def radixsort(arr):
maxnum = max(arr)
exp = 1
while maxnum // exp > 0:
buckets = [[] for in range(10)]
for num in arr:
buckets[(num // exp) % 10].append(num)
arr = []
for bucket in buckets:
arr.extend(bucket)
exp *= 10
return arr`
算法對(duì)比與
| 算法 | 平均時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 穩(wěn)定性 | 適用場(chǎng)景 |
|------|---------------|------------|--------|----------|
| 冒泡排序 | O(n2) | O(1) | 穩(wěn)定 | 教學(xué)示例，小規(guī)模數(shù)據(jù) |
| 選擇排序 | O(n2) | O(1) | 不穩(wěn)定 | 簡(jiǎn)單實(shí)現(xiàn) |
| 插入排序 | O(n2) | O(1) | 穩(wěn)定 | 小規(guī)模或基本有序數(shù)據(jù) |
| 希爾排序 | O(n log n) | O(1) | 不穩(wěn)定 | 中等規(guī)模數(shù)據(jù) |
| 歸并排序 | O(n log n) | O(n) | 穩(wěn)定 | 大數(shù)據(jù)量，需要穩(wěn)定排序 |
| 快速排序 | O(n log n) | O(log n) | 不穩(wěn)定 | 通用場(chǎng)景，平均性能最優(yōu) |
| 堆排序 | O(n log n) | O(1) | 不穩(wěn)定 | 內(nèi)存受限場(chǎng)景 |
| 計(jì)數(shù)排序 | O(n+k) | O(k) | 穩(wěn)定 | 整數(shù)排序，值范圍較小 |
| 桶排序 | O(n+k) | O(n+k) | 穩(wěn)定 | 均勻分布的數(shù)據(jù) |
| 基數(shù)排序 | O(nk) | O(n+k) | 穩(wěn)定 | 多關(guān)鍵字排序 |
學(xué)習(xí)建議
- 理解優(yōu)先：先理解算法原理，再記憶代碼
- 可視化學(xué)習(xí)：使用排序可視化工具觀(guān)察算法執(zhí)行過(guò)程
- 動(dòng)手實(shí)現(xiàn)：獨(dú)立編寫(xiě)每種算法的代碼
- 對(duì)比分析：通過(guò)不同數(shù)據(jù)集測(cè)試算法性能
- 場(chǎng)景選擇：根據(jù)實(shí)際需求選擇合適的排序算法
掌握這十種排序算法，不僅能夠應(yīng)對(duì)技術(shù)面試，更能深入理解算法設(shè)計(jì)的核心思想。建議讀者將代碼實(shí)際運(yùn)行，并嘗試用不同數(shù)據(jù)測(cè)試，觀(guān)察排序過(guò)程的變化。
