Python中的10个快速排序函数

快速排序是一种常用的排序算法，它的时间复杂度为O(nlogn)，它的核心思想是选择一个基准元素，将比它小的元素放在它的左边，将比它大的元素放在它的右边，然后分别递归处理左右两个子序列。在Python中，我们可以使用多种方式来实现快速排序，下面介绍10个常用的快速排序函数。

1. 基础版快排

基础版的快排实现非常简单，它只需要一个递归函数和一个partition函数即可实现。

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left, right = [], []
    for i in arr:
        if i == pivot:
            continue
        if i < pivot:
            left.append(i)
        else:
            right.append(i)
    return quicksort(left) + [pivot] + quicksort(right)

2. 原地版快排

在基础版的快排中，我们使用了额外的空间来存储左右子序列，这不是一个很好的做法。原地版的快排不需要额外的空间，它是通过将数组中的元素交换位置来实现的。

def partition(arr, low, high):
    i = low - 1
    pivot = arr[high]
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1
    
def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi-1)
        quicksort(arr, pi+1, high)
    return arr

3. 双指针原地版快排

在原地版的快排中，我们使用了一个分界点来将原数组分为左右两个子序列，这种做法有些繁琐。双指针版的快排使用两个指针，分别指向数组的开头和结尾，从两端向中间扫描，交换位置后继续扫描，直到两个指针相遇。

def quicksort(arr, low, high):
    if low < high:
        i, j = low, high
        pivot = arr[(low+high)//2]
        while i <= j:
            while arr[i] < pivot:
                i += 1
            while arr[j] > pivot:
                j -= 1
            if i <= j:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
                j -= 1
        quicksort(arr, low, j)
        quicksort(arr, i, high)
    return arr

4. 随机化快排

在基础版的快排中，我们选择的基准元素是数组的中间位置元素，如果数据的分布不均匀，可能会导致快排的时间复杂度变成O(n^2)。为了解决这个问题，随机化快排可以将基准元素随机选择，避免数据的不均匀分布。

import random

def quicksort(arr, low, high):
    if low < high:
        i, j = low, high
        pivot = arr[random.randint(low, high)]
        while i <= j:
            while arr[i] < pivot:
                i += 1
            while arr[j] > pivot:
                j -= 1
            if i <= j:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
                j -= 1
        quicksort(arr, low, j)
        quicksort(arr, i, high)
    return arr

5. 三路快排

在双指针版的快排中，我们使用i和j两个指针分别从数组的开头和结尾向中间扫描。如果原数组中存在大量重复元素，会导致分界点处左右两个子数组的长度不均匀，影响快排的效率。三路快排可以将数组分成小于、等于和大于基准元素的三部分。

def quicksort(arr, low, high):
    if low < high:
        lt, i, gt = low, low+1, high
        pivot = arr[low]
        while i <= gt:
            if arr[i] < pivot:
                arr[i], arr[lt] = arr[lt], arr[i]
                i += 1
                lt += 1
            elif arr[i] > pivot:
                arr[i], arr[gt] = arr[gt], arr[i]
                gt -= 1
            else:
                i += 1
        quicksort(arr, low, lt-1)
        quicksort(arr, gt+1, high)
    return arr

6. 堆排序

堆排序可以看成是一种选择排序，它的时间复杂度为O(nlogn)。堆排序的核心思想是将数组看成一棵完全二叉树，将每个节点的值与其孩子节点的值进行比较，将最大值或最小值放到根节点上，再将其从堆中删除，然后继续进行调整，直到所有的元素都被删除。

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

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

7. 插入排序优化

插入排序可以看做是一种冒泡排序的优化，它的时间复杂度为O(n^2)。对于小规模的数据，插入排序的效率非常高，因此，在快排中，我们可以使用插入排序来处理小规模的子数组。

def insertion_sort(arr, left, right):
    for i in range(left+1, right+1):
        pivot = arr[i]
        j = i - 1
        while j >= left and arr[j] > pivot:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = pivot

def quicksort(arr, left, right):
    if left >= right:
        return
    if right - left + 1 < 10:
        insertion_sort(arr, left, right)
        return
    i, j = left, right
    pivot = arr[random.randint(left, right)]
    while i <= j:
        while arr[i] < pivot:
            i += 1
        while arr[j] > pivot:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
    quicksort(arr, left, j)
    quicksort(arr, i, right)

8. 递归和非递归结合

在快排中，递归的深度可能会很深，造成栈溢出的问题，因此我们可以采用非递归的方式进行优化。

`python

def quicksort(arr, left, right):

stack = [(left, right)]

while stack:

left, right = stack.pop()

if right - left + 1 < 10:

insertion_sort(arr, left, right)

continue