python写排序算法

Python 有许多内置的排序算法，比如 `sorted()` 函数和 `list.sort()` 方法。

如果你想手写排序算法，常见的选择有：冒泡排序、选择排序、插入排序、归并排序和快速排序。

下面是一个简单的冒泡排序算法的例子：

def bubble_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort([5, 2, 9, 1, 5, 6]))  # [1, 2, 5, 5, 6, 9]

冒泡排序的时间复杂度是 O(n^2)，也就是说，对于一个长度为 n 的数组，需要进行 n^2 次比较和交换。它的优点是实现简单，缺点是效率较低。

选择排序、插入排序和归并排序的时间复杂度都是 O(n^2)，但是它们的常数因子比冒泡排序小，因此在实际应用中更快一些。

快速排序是一种分治算法，时间复杂度为 O(n*log n)，在大多数情况下都会比前面几种算法快得多。

下面是一个简单的快速排序算法的例子：

def 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