快速排序算法Python实现

快速排序原理和步骤

快速排序是一种高效的排序算法，基于分治法（Divide and Conquer）来实现。其基本思想是通过一次排序将数组分成两部分，其中一部分的所有元素都小于另一部分，然后递归地对这两部分进行排序。以下是快速排序的详细步骤：

1. 选择基准元素

首先，从数组中选择一个基准元素（pivot）。基准元素的选择方法有多种，例如选择第一个元素、最后一个元素、中间元素或随机选择一个元素。基准元素用于将数组分成两部分。

2. 分区

通过遍历数组，将所有小于基准元素的元素放到基准元素的左边，所有大于基准元素的元素放到基准元素的右边。这个过程称为分区（partitioning）。分区后，基准元素的位置是其在最终排序数组中的正确位置。

3. 递归排序

对基准元素左边的子数组和右边的子数组分别递归地应用快速排序。这个过程将不断分割和排序子数组，直到所有子数组的长度为1，表示数组已经有序。

4. 合并

由于快速排序是原地排序（in-place sorting），不需要额外的合并步骤。递归过程结束后，整个数组已经有序。

快速排序的完整步骤

1. 选择基准： 选择一个基准元素。
2. 分区： 将数组分成两部分，一部分小于基准元素，另一部分大于基准元素。
3. 递归排序： 递归地对基准元素左边和右边的子数组进行排序。
4. 完成： 递归结束后，数组有序。

快速排序的伪代码

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // 获取分区点
        int pi = partition(arr, low, high);

        // 对分区点左边的子数组进行递归排序
        quickSort(arr, low, pi - 1);

        // 对分区点右边的子数组进行递归排序
        quickSort(arr, pi + 1, high);
    }
}

int partition(vector<int>& arr, int low, int high) {
    // 选择最后一个元素作为基准
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++;
            // 交换 arr[i] 和 arr[j]
            swap(arr[i], arr[j]);
        }
    }
    // 交换 arr[i + 1] 和 arr[high] (或基准)
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

Python实现：

def quick_sort(arr):
    """
    对数组进行快速排序
    :param arr: 待排序的数组
    :return: 已排序的数组
    """
    # 如果数组的长度为0或1，直接返回数组
    if len(arr) <= 1:
        return arr

    # 选择数组的最后一个元素作为基准
    pivot = arr[-1]

    # 定义两个空列表，分别存放小于和大于基准的元素
    left = []
    right = []

    # 遍历数组（不包括最后一个元素，即基准）
    for element in arr[:-1]:
        if element < pivot:
            left.append(element)
        else:
            right.append(element)

    # 递归地对左右两个子数组进行快速排序，并合并
    return quick_sort(left) + [pivot] + quick_sort(right)