四种常见的排序算法的详细解释及其对应的Python代码实现：
- 冒泡排序（Bubble Sort）
- 堆排序（Heap Sort）
- 插入排序（Insertion Sort）
- 选择排序（Selection Sort）
冒泡排序是一种简单的排序算法，重复地遍历要排序的数列，一次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有需要交换的，也就是说该数列已经排序完成。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# 提前退出标志位
swapped = False
# 每次遍历后，最大的元素会“冒泡”到末尾
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
# 交换
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 如果没有发生交换，说明数组已经有序
if not swapped:
break
return arr
# 示例使用
if __name__ == "__main__":
sample_list = [64, 34, 25, 12, 22, 11, 90]
print("原始列表:", sample_list)
sorted_list = bubble_sort(sample_list)
print("排序后列表:", sorted_list)原始列表: [64, 34, 25, 12, 22, 11, 90]
排序后列表: [11, 12, 22, 25, 34, 64, 90]
- 时间复杂度：
- 最佳情况：O(n)（当数组已经有序时）
- 平均和最坏情况：O(n²)
- 空间复杂度：O(1)（原地排序）
- 稳定性：稳定
堆排序是一种基于比较的排序算法，利用堆这种数据结构来排序。堆是一种完全二叉树，分为最大堆和最小堆。堆排序通常使用最大堆，先构建一个最大堆，然后将堆顶元素（最大值）与堆的最后一个元素交换，之后对剩下的元素重新调整为最大堆，如此反复，直到整个数组有序。
def heapify(arr, n, i):
largest = i # 初始化最大值为根节点
left = 2 * i + 1 # 左子节点
right = 2 * i + 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
# 示例使用
if __name__ == "__main__":
sample_list = [12, 11, 13, 5, 6, 7]
print("原始列表:", sample_list)
sorted_list = heap_sort(sample_list)
print("排序后列表:", sorted_list)原始列表: [12, 11, 13, 5, 6, 7]
排序后列表: [5, 6, 7, 11, 12, 13]
- 时间复杂度：
- 所有情况：O(n log n)
- 空间复杂度：O(1)（原地排序）
- 稳定性：不稳定
插入排序是一种简单直观的排序算法，类似于整理扑克牌的方式。它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i] # 当前待插入的元素
j = i -1
# 将arr[i]插入到已排序部分的正确位置
while j >=0 and arr[j] > key:
arr[j + 1] = arr[j] # 移动元素
j -=1
arr[j + 1] = key # 插入
return arr
# 示例使用
if __name__ == "__main__":
sample_list = [31, 41, 59, 26, 41, 58]
print("原始列表:", sample_list)
sorted_list = insertion_sort(sample_list)
print("排序后列表:", sorted_list)原始列表: [31, 41, 59, 26, 41, 58]
排序后列表: [26, 31, 41, 41, 58, 59]
- 时间复杂度：
- 最佳情况：O(n)（当数组已经有序时）
- 平均和最坏情况：O(n²)
- 空间复杂度：O(1)（原地排序）
- 稳定性：稳定
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
def selection_sort(arr):
n = len(arr)
for i in range(n):
# 假设当前索引为最小值
min_idx = i
# 在剩下的元素中寻找最小值
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 交换找到的最小值与当前位置的值
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 示例使用
if __name__ == "__main__":
sample_list = [64, 25, 12, 22, 11]
print("原始列表:", sample_list)
sorted_list = selection_sort(sample_list)
print("排序后列表:", sorted_list)原始列表: [64, 25, 12, 22, 11]
排序后列表: [11, 12, 22, 25, 64]
- 时间复杂度：
- 所有情况：O(n²)
- 空间复杂度：O(1)（原地排序）
- 稳定性：不稳定
以上四种排序算法各有优缺点：
- 冒泡排序：实现简单，但效率较低，适用于小规模数据。
- 堆排序：时间复杂度稳定为O(n log n)，适用于大规模数据，但不稳定。
- 插入排序：在数据基本有序的情况下效率较高，适用于小规模数据，且稳定。
- 选择排序：实现简单，但效率不高，不适合大规模数据，不稳定。
根据具体的应用场景和数据特点选择合适的排序算法，可以在保证效率的同时满足稳定性等需求。