面试题：C++ 快速排序的优化实现

优化思路

三向切分：传统的快速排序每次只将数组分为两部分（小于基准和大于基准）。对于大量重复元素的数组，使用三向切分，将数组分为三部分：小于基准、等于基准和大于基准。这样可以直接将等于基准的元素放到正确位置，减少后续对这些元素的比较和交换。
随机化选择基准：为了避免在特殊情况下（如数组已经有序）快速排序退化为 O(n²) 的时间复杂度，随机选择数组中的一个元素作为基准。

代码实现

#include <iostream>
#include <cstdlib>
#include <ctime>

// 交换两个元素
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 三向切分函数
void threeWayPartition(int arr[], int low, int high, int& lt, int& gt) {
    int i = low;
    int v = arr[low];
    lt = low;
    gt = high;

    while (i <= gt) {
        if (arr[i] < v) {
            swap(arr[lt++], arr[i++]);
        } else if (arr[i] > v) {
            swap(arr[i], arr[gt--]);
        } else {
            i++;
        }
    }
}

// 快速排序递归函数
void quickSort(int arr[], int low, int high) {
    if (low >= high) return;

    std::srand(std::time(nullptr));
    int randomIndex = low + std::rand() % (high - low + 1);
    swap(arr[low], arr[randomIndex]);

    int lt, gt;
    threeWayPartition(arr, low, high, lt, gt);

    quickSort(arr, low, lt - 1);
    quickSort(arr, gt + 1, high);
}

// 快速排序主函数
void quickSort(int arr[], int n) {
    quickSort(arr, 0, n - 1);
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

你可以使用以下方式调用这个函数：

int main() {
    int arr[] = {4, 9, 4, 4, 1, 4, 5, 6, 4, 8, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original array: ";
    printArray(arr, n);

    quickSort(arr, n);

    std::cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

星途面试题库

面试题：C++ 快速排序的优化实现

知识考点

面试题答案

优化思路

代码实现