归并排序（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
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
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
# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = merge_sort(arr)
print("排序后的数组:", sorted_arr)
堆排序（Heap Sort）
原理： 堆排序（Heap 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
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(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)
# 测试代码
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("排序后的数组:", arr)
计数排序（Counting Sort）
原理： 计数排序是一种线性时间复杂度的排序算法，适用于元素范围较小的情况。它统计每个元素的出现次数，然后根据统计信息构建排序结果。
Python 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def counting_sort(arr):
max_val = max(arr)
count_arr = [0] * (max_val + 1)
sorted_arr = [0] * len(arr)
for num in arr:
count_arr[num] += 1
for i in range(1, len(count_arr)):
count_arr[i] += count_arr[i - 1]
for num in reversed(arr):
sorted_arr[count_arr[num] - 1] = num
count_arr[num] -= 1
return sorted_arr
# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = counting_sort(arr)
print("排序后的数组:", sorted_arr)
桶排序（Bucket 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
def bucket_sort(arr):
bucket_size = 10 # 桶的大小
max_val = max(arr)
min_val = min(arr)
# 计算桶的数量
num_buckets = (max_val - min_val) // bucket_size + 1
buckets = [[] for _ in range(num_buckets)]
for num in arr:
index = (num - min_val) // bucket_size
buckets[index].append(num)
sorted_arr = []
for bucket in buckets:
sorted_arr.extend(sorted(bucket))
return sorted_arr
# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bucket_sort(arr)
print("排序后的数组:", sorted_arr)