Python 数据结构之十大经典排序算法一文通关
一、前置知识
在学习本文之前，需要具备以下基础知识：
- Python 基础语法
- 算法与数据结构基础
二、十大经典排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
- 堆排序
- 计数排序
- 桶排序
- 基数排序
本文将一一讲解这十种排序算法。
三、冒泡排序
冒泡排序是一种简单的排序算法，它重复地遍历过要排序的数列，一次比较两个元素，如果顺序有误就交换位置。它的实现过程如下：
def bubble_sort(data):
for i in range(len(data)):
for j in range(len(data)-1-i):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
return data
例如，对于输入列表 [3, 1, 2, 5, 4]，冒泡排序算法的输出结果为 [1, 2, 3, 4, 5]。
四、 选择排序
选择排序是一种简单直观的排序算法。它的实现过程如下：
def selection_sort(data):
for i in range(len(data)):
min_index = i
for j in range(i+1, len(data)):
if data[j] < data[min_index]:
min_index = j
data[i], data[min_index] = data[min_index], data[i]
return data
例如，对于输入列表 [3, 1, 2, 5, 4]，选择排序算法的输出结果为 [1, 2, 3, 4, 5]。
五、插入排序
插入排序是一种简单直观的排序算法，它的实现过程如下：
def insertion_sort(data):
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j+1] = data[j]
j -= 1
data[j+1] = key
return data
例如，对于输入列表 [3, 1, 2, 5, 4]，插入排序算法的输出结果为 [1, 2, 3, 4, 5]。
六、希尔排序
希尔排序是一种改进的插入排序算法，它的实现过程如下：
def shell_sort(data):
gap = len(data) // 2
while gap > 0:
for i in range(gap, len(data)):
temp = data[i]
j = i
while j >= gap and data[j-gap] > temp:
data[j] = data[j-gap]
j -= gap
data[j] = temp
gap //= 2
return data
例如，对于输入列表 [3, 1, 2, 5, 4]，希尔排序算法的输出结果为 [1, 2, 3, 4, 5]。
七、归并排序
归并排序是一种分治思想的算法，它的实现过程如下：
def merge_sort(data):
if len(data) <= 1:
return data
mid = len(data) // 2
left = merge_sort(data[:mid])
right = merge_sort(data[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 += left[i:]
result += right[j:]
return result
例如，对于输入列表 [3, 1, 2, 5, 4]，归并排序算法的输出结果为 [1, 2, 3, 4, 5]。
八、快速排序
快速排序是一种分治思想的算法，它的实现过程如下：
def quick_sort(data):
if len(data) <= 1:
return data
pivot = data[0]
left = [x for x in data[1:] if x <= pivot]
right = [x for x in data[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
例如，对于输入列表 [3, 1, 2, 5, 4]，快速排序算法的输出结果为 [1, 2, 3, 4, 5]。
九、堆排序
堆排序是一种树形选择排序。它的实现过程如下：
def heap_sort(data):
def sift_down(start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
if child + 1 <= end and data[child] < data[child+1]:
child += 1
if data[root] < data[child]:
data[root], data[child] = data[child], data[root]
root = child
else:
break
for start in range((len(data)-2)//2, -1, -1):
sift_down(start, len(data)-1)
for end in range(len(data)-1, 0, -1):
data[0], data[end] = data[end], data[0]
sift_down(0, end-1)
return data
例如，对于输入列表 [3, 1, 2, 5, 4]，堆排序算法的输出结果为 [1, 2, 3, 4, 5]。
十、计数排序
计数排序是一种线性时间复杂度的排序算法，它的实现过程如下：
def counting_sort(data):
bucket = [0] * (max(data)+1)
for i in data:
bucket[i] += 1
index = 0
for i in range(len(bucket)):
while bucket[i] > 0:
data[index] = i
index += 1
bucket[i] -= 1
return data
例如，对于输入列表 [3, 1, 2, 5, 4]，计数排序算法的输出结果为 [1, 2, 3, 4, 5]。
十一、桶排序
桶排序是一种线性时间复杂度的排序算法，它的实现过程如下：
def bucket_sort(data):
max_num = max(data)
min_num = min(data)
bucket_size = 5
bucket_count = (max_num - min_num) // bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
for i in data:
buckets[(i-min_num)//bucket_size].append(i)
result = []
for b in buckets:
if b:
result.extend(sorted(b))
return result
例如，对于输入列表 [3, 1, 2, 5, 4]，桶排序算法的输出结果为 [1, 2, 3, 4, 5]。
十二、基数排序
基数排序是一种多关键字排序算法，它的实现过程如下：
def radix_sort(data):
max_num = max(data)
max_digits = len(str(max_num))
mod = 10
dev = 1
for i in range(max_digits):
buckets = [[] for _ in range(mod*2)]
for j in data:
bucket_index = j // dev % mod + mod
buckets[bucket_index].append(j)
dev *= 10
data = [x for b in buckets for x in b]
return data
例如，对于输入列表 [3, 1, 2, 5, 4]，基数排序算法的输出结果为 [1, 2, 3, 4, 5]。
结语
以上就是十大经典排序算法的实现过程。需要注意的是，不同的排序算法在不同场景下可能会有不同的表现。掌握不同的排序算法，能够帮助我们更好地解决实际问题。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Python 数据结构之十大经典排序算法一文通关 - Python技术站
微信扫一扫 
支付宝扫一扫 