怎么使用Python进行高效的排序操作

Python内置排序函数

Python的内置排序函数非常方便，可以对列表或其他可迭代对象进行排序。内置函数包含sorted()和sort()。sorted()函数可对任何可迭代对象进行排序并返回一个新的列表，而sort()函数则原地对列表进行排序。

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = sorted(numbers)
numbers.sort()
print(sorted_numbers)
print(numbers)

上述代码将对列表numbers进行排序，sorted()函数返回新的已排序列表sorted_numbers，而sort()函数原地对原列表numbers进行排序。输出结果为[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]和[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]。

冒泡排序

冒泡排序是一种基本的排序算法。它比较相邻的元素，并在必要时交换它们的位置，以便将序列按升序排列。每次冒泡操作将会将待排序序列中最大的元素“冒泡”到序列的末尾。由于冒泡排序的操作只涉及相邻的元素，因此它的空间复杂度为O(1)。

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

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = bubble_sort(numbers)
print(sorted_numbers)

上述代码通过定义一个bubble_sort()函数实现了冒泡排序。通过嵌套循环，内层循环比较并交换相邻的元素，直到序列有序。最终将排序后的序列返回。输出结果为[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]。

快速排序

快速排序是一种基于分治思想的排序算法。它通过选取一个元素作为基准，将序列分成两个部分，其中一个部分的所有元素均小于基准，而另一个部分的所有元素均大于基准。然后递归地对这两个部分进行排序，最终将整个序列排序。快速排序的时间复杂度为O(nlogn)。

def quick_sort(items):
    if len(items) <= 1:
        return items
    pivot = items[0]
    left = []
    right = []
    for item in items[1:]:
        if item < pivot:
            left.append(item)
        else:
            right.append(item)
    return quick_sort(left) + [pivot] + quick_sort(right)

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = quick_sort(numbers)
print(sorted_numbers)

上述代码通过定义一个quick_sort()函数实现了快速排序。通过选取序列的第一个元素作为基准，将序列分成两个部分，然后递归地对这两个部分进行排序。最终将排序后的序列返回。输出结果为[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]。

堆排序

堆排序是一种基于堆（完全二叉树）的排序算法。它先将序列构建成一个最大堆或最小堆，然后依次将堆顶元素（即最大值或最小值）与堆末尾的元素交换，再调整堆以维护堆的性质。重复这个过程，最终就可以得到一个有序序列。堆排序的时间复杂度为O(nlogn)。

def heapify(items, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and items[l] > items[largest]:
        largest = l
    if r < n and items[r] > items[largest]:
        largest = r
    if largest != i:
        items[i], items[largest] = items[largest], items[i]
        heapify(items, n, largest)

def heap_sort(items):
    n = len(items)
    for i in range(n // 2 - 1, -1, -1):
        heapify(items, n, i)
    for i in range(n - 1, 0, -1):
        items[i], items[0] = items[0], items[i]
        heapify(items, i, 0)
    return items

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_numbers = heap_sort(numbers)
print(sorted_numbers)

上述代码通过定义一个heapify()函数和一个heap_sort()函数实现了堆排序。heapify()函数用于维护堆的性质，heap_sort()函数则将待排序序列转换成最大堆，并通过交换堆顶元素和堆末尾元素的方式将序列从大到小排序。输出结果为[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]。