C++如何实现快速排序算法_C++经典排序算法Quick Sort的分治思想

快速排序采用分治法，通过选取基准分区实现高效排序。1. 分解：选基准（如首元素），用双指针将小于基准的放左，大于的放右；2. 解决：递归对左右子数组排序；3. 合并：无需显式合并，划分后基准已就位。常用Lomuto分区法，以首元素为pivot，遍历并交换元素，最后将基准置于正确位置。C++实现中，partition函数返回基准索引，quickSort递归处理两侧。平均时间复杂度O(n log n)，最坏O(n²)，优化策略包括随机选基准、三数取中和小数组用插入排序。关键细节在于边界控制与基准放置，理解分区逻辑即可灵活实现。

快速排序（Quick Sort）是一种高效的排序算法，采用分治思想实现。它的核心思路是：从数组中选择一个“基准”元素，将小于基准的元素移到左边，大于基准的移到右边，然后对左右两部分递归处理，最终使整个数组有序。

分治三步走：分解、解决、合并

快速排序虽然不需要显式的“合并”步骤，但完整体现了分治法的逻辑：

• 分解：选取基准值（pivot），将数组划分为两个子数组，左半边都小于等于基准，右半边都大于基准。
• 解决：递归地对左右两个子数组进行快速排序。
• 合并：由于每轮划分后基准已处于正确位置，递归完成后数组自然有序，无需额外操作。

如何选择基准和分区？

分区（Partition）是快速排序的关键步骤。常用方法是双指针法，从数组两端向中间扫描，交换不符合条件的元素。

以下是基于首元素为基准的Lomuto分区方式简化实现（也可使用Hoare分区）：

立即学习“C++免费学习笔记（深入）”；

AssemblyAI

转录和理解语音的AI模型

65

查看详情

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[low];  // 选第一个元素为基准
    int i = low + 1;
    for (int j = low + 1; j <= high; j++) {
        if (arr[j] < pivot) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[low], arr[i - 1]);  // 基准放到正确位置
    return i - 1;
}

C++完整实现代码

结合递归调用，完成完整的快速排序函数：

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);        // 排右半部分
    }
}

调用示例：

vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr, 0, arr.size() - 1);
// 输出结果：11 12 22 25 34 64 90

性能分析与优化建议

快速排序平均时间复杂度为O(n log n)，最坏情况为O(n²)，但实际表现通常优于其他O(n log n)算法。

• 最好情况：每次划分都能均分数组。
• 最坏情况：数组已有序，且每次都选到最小或最大元素作基准。
• 优化方式：随机选取基准、三数取中法、小数组改用插入排序等。

基本上就这些。理解分治逻辑和分区过程，就能灵活实现并优化快速排序。不复杂但容易忽略细节，比如边界控制和基准放置。

以上就是C++如何实现快速排序算法_C++经典排序算法Quick Sort的分治思想的详细内容，更多请关注php中文网其它相关文章！