Python程序：对数组进行排序

排序是程序中非常常见的操作之一，Python提供了丰富的排序函数和方法，可以用来对数组进行排序。

冒泡排序

冒泡排序是最基本的排序算法之一，其思想是每次比较相邻的两个元素，若它们顺序不对则交换它们的位置，这样一趟排序后最大元素就被放在了正确的位置上。多次这样的排序后，整个数组就有序了。

下面是一个简单的冒泡排序Python实现：

def bubble_sort(arr):
    n = len(arr)

    # 进行n-1轮比较
    for i in range(n-1):

        # 每轮比较n-1-i次
        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

以上代码的时间复杂度为O(n^2)，空间复杂度为O(1)。

快速排序

快速排序是排序算法中十分流行的一种，它通过递归地将数组划分为较小和较大两个子数组，然后分别对子数组进行快速排序。

下面是一个简单的快速排序Python实现：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    left = []
    right = []

    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])

    return quick_sort(left) + [pivot] + quick_sort(right)

以上代码的时间复杂度为O(nlogn)，空间复杂度为O(nlogn)。

归并排序

归并排序是另一种十分流行的排序算法，它采用分治法的思想，将数组不断分成两个子数组，直到每个子数组只有一个元素，然后不断将相邻的子数组进行合并，直到整个数组有序为止。

下面是一个简单的归并排序Python实现：

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):
    res = []

    while len(left) > 0 and len(right) > 0:
        if left[0] < right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))

    res += left
    res += right

    return res

以上代码的时间复杂度为O(nlogn)，空间复杂度为O(n)。

插入排序

插入排序是一种简单且高效的排序算法，其思想是通过迭代将未排序元素插入到已排序的位置上，以达到排序的目的。

下面是一个简单的插入排序Python实现：

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

以上代码的时间复杂度为O(n^2)，空间复杂度为O(1)。

选择排序

选择排序是一种简单的排序算法，其思想是在未排序元素中找到最小元素，并放到已排序序列的末尾。

下面是一个简单的选择排序Python实现：

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return arr

以上代码的时间复杂度为O(n^2)，空间复杂度为O(1)。

堆排序

堆排序是一种高效的排序算法，其思想是先将数组构建为一个最大堆（或最小堆），然后重复将堆顶元素（即最大元素或最小元素）与末尾元素交换，并调整堆的大小和结构，直到整个数组有序。

下面是一个简单的堆排序Python实现：

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[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

    return arr

以上代码的时间复杂度为O(nlogn)，空间复杂度为O(1)。