python 常见的排序算法实现汇总

1. 冒泡排序

冒泡排序是一种简单直观的排序算法。它重复地遍历待排序的列表，一次比较两个元素，并且如果它们的顺序错误就交换它们，直到遍历完整个列表。冒泡排序的时间复杂度是O(n^2)。

步骤：

比较相邻的元素。如果第一个比第二个大，就交换它们两个。

对每一对相邻元素做同样的工作，从开始第一对到最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

下面是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

冒泡排序的优化：

在上述的冒泡排序实现中，即使已经排好序的列表还会继续遍历和比较。为了优化这个算法，在每一次遍历中，可以判断是否发生了交换，如果没有发生交换，说明列表已经有序，可以提前退出循环。

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

使用冒泡排序对列表排序：

arr = [5, 3, 8, 4, 2]
sorted_arr = bubble_sort_optimized(arr)
print(sorted_arr)

冒泡排序每次只交换相邻两个元素，因此它是一种稳定的排序算法。