请写一下快速排序算法

问题

请写一下快速排序算法

我的回答

快排的核心思想是分治法，我们选择一个基准值，然后将数组分为小于基准值和大于基准值的两部分，再递归地对这两部分进行排序。

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;  // 递归终止条件
    
    // 选择基准值，这里简单地选择最左边的元素
    int pivot = arr[left];
    
    // 分区过程
    int i = left, j = right;
    while (i < j) {
        // 从右向左找第一个小于基准的数
        while (i < j && arr[j] >= pivot) j--;
        // 从左向右找第一个大于基准的数
        while (i < j && arr[i] <= pivot) i++;
        // 交换这两个数
        if (i < j) {
            std::swap(arr[i], arr[j]);
        }
    }
    // 将基准值放到正确的位置
    std::swap(arr[left], arr[i]);
    
    // 递归排序左右两部分
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

这个实现中，我选择了最左边的元素作为基准值，然后通过双指针法进行分区。当然，这种选择基准值的方式在最坏情况下（如已排序数组）会导致O(n²)的时间复杂度。

为了优化，我们可以使用随机选择基准值或三数取中法：

int median3(int arr[], int left, int right) {
    int mid = left + (right - left) / 2;
    // 三数取中
    if (arr[left] > arr[mid]) std::swap(arr[left], arr[mid]);
    if (arr[left] > arr[right]) std::swap(arr[left], arr[right]);
    if (arr[mid] > arr[right]) std::swap(arr[mid], arr[right]);
    
    // 将基准值放到left+1位置
    std::swap(arr[mid], arr[left + 1]);
    return arr[left + 1];
}

快排的平均时间复杂度是O(nlogn)，最坏情况是O(n²)，但通过优化基准值选择，可以降低最坏情况发生的概率。空间复杂度主要是递归调用栈的深度，平均为O(logn)，最坏为O(n)。

快排是不稳定的排序算法，相同值的相对顺序可能会改变。在实际应用中，对于小规模数据，我们通常会在快排的基础上结合插入排序来提高效率。"