python快速排序代码实例

Python 快速排序 (Quick Sort) 是一种排序算法，它利用分治思想来快速排序一个数组或序列。该算法的时间复杂度为 O(nlogn)。

要理解快速排序算法，我们需要掌握以下概念：

• 基准值 (pivot)：排序过程中用于比较的值。在每一轮的排序过程中，基准值会将数组或序列分成两部分。
• 子数组 (subarray)：对于一个数组或序列，它的一部分就是一个子数组。在快排中，子数组的划分是对基准值的判断和比较得出的。

快速排序的实现步骤

以下是快速排序算法的实现步骤：

1. 选取基准值 pivot，一般取数组的第一个元素或者随机数。
2. 将数组或序列分成小于等于和大于等于基准值的两个子数组 subarrayLeft 和 subarrayRight，并将基准值放在它们中间。
3. 对 subarrayLeft 和 subarrayRight 分别递归快排。
4. 递归出口是子数组的长度为 0 或 1。

Python 代码示例

下面给出一个 Python 的快速排序代码实例：

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

    pivot = arr[0]
    subarrayLeft = []
    subarrayRight = []

    for i in arr[1:]:
        if i <= pivot:
            subarrayLeft.append(i)
        else:
            subarrayRight.append(i)

    return quicksort(subarrayLeft) + [pivot] + quicksort(subarrayRight)

该代码实现的是递归快速排序。函数传入一个数组，如果长度小于等于 1 就直接返回该数组，否则选取第一个元素作为基准值，并将数组分成左右两部分，然后分别对左右两部分递归快排。

arr = [3, 2, 1, 5, 4]
print(quicksort(arr))  # [1, 2, 3, 4, 5]

对于上面的示例代码，如果输入的数组是 [3, 2, 1, 5, 4]，输出结果将是 [1, 2, 3, 4, 5]。

另外，我们还可以实现原地快速排序。以下是 Python 原地快速排序代码示例：

def quicksortInPlace(arr):
    def partition(left, right):
        pivot = arr[right]
        i = left - 1

        for j in range(left, right):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]

        arr[i + 1], arr[right] = arr[right], arr[i + 1]
        return i + 1

    def _quicksort(left, right):
        if left < right:
            pivotIndex = partition(left, right)
            _quicksort(left, pivotIndex - 1)
            _quicksort(pivotIndex + 1, right)

    _quicksort(0, len(arr) - 1)
    return arr

该代码实现的是原地快速排序。我们传入一个数组，然后定义 partition 函数来进行分区，该函数使用 right 作为基准值 pivot，并返回 pivot 的最终索引。在快速排序的整个过程中，比 pivot 小的数放在数组的左侧，比 pivot 大的数放在数组的右侧。

arr = [3, 2, 1, 5, 4]
quicksortInPlace(arr)
print(arr)  # [1, 2, 3, 4, 5]

对于上面的示例代码，如果输入的数组是 [3, 2, 1, 5, 4]，程序会直接通过原地排序修改原数组，输出结果将是 [1, 2, 3, 4, 5]。