8大排序算法汇总
以下是八大排序算法的详细介绍，包含了相应的 Python 实现代码，使用 Markdown 格式：
1. 冒泡排序 (Bubble Sort)
冒泡排序通过重复遍历待排序的数列，每次比较相邻的元素，并交换顺序错误的元素，直到整个数列有序。
Python 代码：1
2
3
4
5
6
7
8
9
10
11def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))
2. 选择排序 (Selection Sort)
选择排序每次从未排序的部分中选择最小（或最大）元素，放到已排序部分的末尾。
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# 示例
arr = [64, 25, 12, 22, 11]
print(selection_sort(arr))
3. 插入排序 (Insertion Sort)
插入排序通过将待排序的元素插入到已排序部分中的适当位置来完成排序。
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13def 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
# 示例
arr = [12, 11, 13, 5, 6]
print(insertion_sort(arr))
4. 归并排序 (Merge Sort)
归并排序是通过分治法将大问题分解成小问题，递归排序后再合并结果。
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
return arr
# 示例
arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))
5. 快速排序 (Quick Sort)
快速排序是一种分治法排序算法，通过选择一个基准元素，将数组划分为左右两部分，然后递归排序。
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12def 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)
# 示例
arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr))
6. 堆排序 (Heap Sort)
堆排序利用堆这种数据结构，通过构建最大堆来逐步将数组排序。
Python 代码：1
2
3
4
5
6
7
8
9import heapq
def heap_sort(arr):
heapq.heapify(arr)
return [heapq.heappop(arr) for _ in range(len(arr))]
# 示例
arr = [3, 5, 1, 10, 2, 7]
print(heap_sort(arr))
7. 计数排序 (Counting Sort)
计数排序是一种非比较排序算法，适用于元素的取值范围较小的情况。通过统计每个元素出现的次数，然后按次数输出排序结果。
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23def counting_sort(arr):
max_val = max(arr)
min_val = min(arr)
range_of_elements = max_val - min_val + 1
count = [0] * range_of_elements
output = [0] * len(arr)
for num in arr:
count[num - min_val] += 1
for i in range(1, len(count)):
count[i] += count[i - 1]
for num in reversed(arr):
output[count[num - min_val] - 1] = num
count[num - min_val] -= 1
return output
# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr))
8. 基数排序 (Radix Sort)
基数排序是一种非比较排序算法，通过逐位处理数字，依次从最低位到最高位进行排序。
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33def counting_sort_for_radix(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort_for_radix(arr, exp)
exp *= 10
return arr
# 示例
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print(radix_sort(arr))
总结
以上代码实现了八种常见的排序算法，包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、计数排序和基数排序。每种算法有不同的优缺点和适用场景，选择合适的算法可以提高程序效率。
