C++快速排序

快速排序算法思路

快速排序是一种分治算法，通过递归地将数组分成较小和较大的子数组来排序。核心思想是选择一个基准元素（pivot），将数组分为两部分：一部分所有元素小于基准，另一部分所有元素大于基准，然后对子数组递归执行相同操作。

基准的选择通常有几种方式：

• 选择第一个元素
• 选择最后一个元素
• 随机选择
• 选择中间元素

分区操作实现

分区是快速排序的核心步骤，将数组按基准分为两部分。以下是一种常见的分区实现方式（Lomuto分区）：

1. 选择最后一个元素作为基准（pivot）。
2. 初始化一个索引i指向较小元素的末尾。
3. 遍历数组，将小于基准的元素交换到i的位置，并递增i。
4. 最后将基准交换到正确位置。

int partition(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++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

递归排序实现

分区操作完成后，递归地对左右子数组进行排序：

void quickSort(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);
    }
}

完整代码示例

以下是包含主函数的完整实现：

#include <iostream>
using namespace std;

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(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++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(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 main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

算法复杂度分析

• 时间复杂度：
  • 最佳情况：$O(nlogn)$
  • 平均情况：$O(nlogn)$
  • 最坏情况：$O(n^2)$（当数组已经有序且选择第一个/最后一个元素作为基准时）
• 空间复杂度：$O(logn)$（递归调用栈）

优化建议

1. 随机化基准选择：通过随机选择基准避免最坏情况。
2. 三数取中法：选择第一个、中间和最后一个元素的中值作为基准。
3. 小数组切换：对小规模子数组使用插入排序。
4. 尾递归优化：减少递归深度。

随机化分区示例：

int partition(int arr[], int low, int high) {
    int random = low + rand() % (high - low);
    swap(arr[random], arr[high]);
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

常用实现方法

快速排序的基本实现

快速排序的核心思想是分治法，通过选取基准值（pivot）将数组分为两部分，递归排序子数组。以下是经典实现方式：

void quickSort(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(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

使用随机化基准值

为避免最坏情况时间复杂度（如已排序数组），可采用随机化基准值：

int partitionRandom(int arr[], int low, int high) {
    int random = low + rand() % (high - low + 1);
    swap(arr[random], arr[high]);
    return partition(arr, low, high);
}

三数取中法优化

通过选择左、中、右三个元素的中值作为基准值，减少不平衡划分的概率：

int medianOfThree(int arr[], int low, int high) {
    int mid = low + (high - low) / 2;
    if (arr[low] > arr[mid]) swap(arr[low], arr[mid]);
    if (arr[low] > arr[high]) swap(arr[low], arr[high]);
    if (arr[mid] > arr[high]) swap(arr[mid], arr[high]);
    return mid;
}

迭代法实现

用栈模拟递归调用，避免递归导致的栈溢出：

void quickSortIterative(int arr[], int low, int high) {
    stack<int> st;
    st.push(low);
    st.push(high);
    while (!st.empty()) {
        high = st.top(); st.pop();
        low = st.top(); st.pop();
        int pi = partition(arr, low, high);
        if (pi - 1 > low) {
            st.push(low);
            st.push(pi - 1);
        }
        if (pi + 1 < high) {
            st.push(pi + 1);
            st.push(high);
        }
    }
}

双指针法（Hoare分区）

Hoare提出的原始分区方案，减少交换次数：

int hoarePartition(int arr[], int low, int high) {
    int pivot = arr[low + (high - low) / 2];
    int i = low - 1, j = high + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(arr[i], arr[j]);
    }
}

针对重复元素的优化

当数组中存在大量重复元素时，三向切分（Dutch National Flag）可提升效率：

void quickSort3Way(int arr[], int low, int high) {
    if (high <= low) return;
    int lt = low, gt = high;
    int pivot = arr[low];
    int i = low;
    while (i <= gt) {
        if (arr[i] < pivot) swap(arr[lt++], arr[i++]);
        else if (arr[i] > pivot) swap(arr[i], arr[gt--]);
        else i++;
    }
    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

混合排序算法

对小规模子数组使用插入排序，减少递归开销：

void insertionSort(int arr[], int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void hybridQuickSort(int arr[], int low, int high) {
    if (high - low < 16) {
        insertionSort(arr, low, high);
        return;
    }
    int pi = partition(arr, low, high);
    hybridQuickSort(arr, low, pi - 1);
    hybridQuickSort(arr, pi + 1, high);
}