排序算法：Python中常见的排序算法函数

在Python中，有多种常见的排序算法可以使用。下面列举了几种常见的排序算法函数。

1. 冒泡排序（Bubble Sort）：该算法通过重复比较相邻的元素，并交换位置，使较大的元素逐渐向右移动到数组的末尾。此算法的时间复杂度为O(n^2)。

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

2. 插入排序（Insertion Sort）：该算法从第二个元素开始，在已排序的部分中找到合适的位置并插入。此算法的时间复杂度为O(n^2)。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

3. 选择排序（Selection Sort）：该算法通过重复找到未排序部分的最小元素，并将其放在已排序部分的末尾。此算法的时间复杂度为O(n^2)。

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

4. 快速排序（Quick Sort）：该算法选择一个基准元素，并将其他元素分为两个子数组，大于基准的放在右边，小于基准的放在左边。然后对这两个子数组递归地应用快速排序。此算法的平均时间复杂度为O(nlogn)。

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 x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

5. 归并排序（Merge Sort）：该算法将一个数组递归地分成两半，然后对两个子数组分别应用归并排序。最后将两个有序的子数组合并成一个有序的数组。此算法的时间复杂度为O(nlogn)。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

def merge(left, right):
    result = []
    i = 0
    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

除了上述列举的排序算法外，还有许多其他的排序算法，如堆排序、计数排序、桶排序、基数排序等。每种排序算法都有其特定的应用场景和性能特点，选择适合的排序算法可以提高程序的效率。