常用算法介绍--＞快速排序

本篇文章我们来介绍一下快速排序的算法

1.简介

快速排序是对冒泡排序的一种改进，它是不稳定的。由C. A. R. Hoare在1962年提出的一种划分交换排序，采用的是分治策略（一般与递归结合使用），以减少排序过程中的比较次数，它的最好情况为O(nlogn)，最坏情况为O(n^2)，平均时间复杂度为O(nlogn)。

2.基本思想

选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以达到全部数据变成有序。

3.步骤

(1) 从数列中挑出一个基准值。 (2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)，在这个分区退出之后，该基准就处于数列的中间位置。 (3) 递归地把基准值前面的子数列和基准值后面的子数列进行排序。

注意：基准元素/左游标/右游标都是针对单趟排序而言的，也就是说在整个排序过程的多趟排序中，各趟排序取得的基准元素/左游标/右游标一般都是不同的。对于基准元素的选取，原则上是任意的，但是一般我们选取数组中第一个元素为基准元素（假设数组随机分布）。

4.以下是介绍详细步骤

选取上述数组的第一个元素6作为基准元，左游标是 i 哨兵，右游标是 j 哨兵，它们遵循的规则如下：一、左游标向右扫描，跨过所有小于基准元素的数组元素, 直到遇到一个大于或等于基准元素的数组元素，在那个位置停下。二、右游标向左扫描，跨过所有大于基准元素的数组元素, 直到遇到一个小于或等于基准元素的数组元素，在那个位置停下。然后进行交换即可相遇在进行最后一次交换

最后一次两个哨兵相遇探测结束作为最后一次交换

以下是代码实例:

#include <iostream>
#include <vector>

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

// 分区函数，将小于pivot的元素放在左边，大于等于pivot的元素放在右边
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选取最后一个元素作为pivot
    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]); // 将pivot放在正确的位置上
    return i + 1; // 返回分区位置
}

// 快速排序函数
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int partitionIndex = partition(arr, low, high); // 获取分区位置

        quickSort(arr, low, partitionIndex - 1); // 对左半部分递归排序
        quickSort(arr, partitionIndex + 1, high); // 对右半部分递归排序
    }
}

// 打印数组元素
void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr = {5, 9, 3, 1, 8, 6, 2, 7};

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

    quickSort(arr, 0, arr.size() - 1);

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

    return 0;
}