八大排序算法 —— 快速排序全揭秘：从基础到优化

创作时间:

作者:

@小白创作中心

八大排序算法 —— 快速排序全揭秘：从基础到优化

引用

CSDN

https://blog.csdn.net/charlie_lee_cs/article/details/139554753

快速排序简介

定义

快速排序：快速排序也采用分治策略，选择一个基准元素，将数组分成比基准小和比基准大的两部分，再对两部分递归地进行排序。快速排序的平均时间复杂度为O(n log n)，是目前应用广泛的排序算法之一。

时间复杂度

最坏情况：O(n²)
平均情况：O(n log₂n)
最佳情况：O(n log₂n)

最优的Partition算法 🔥

Introsort简介

Introsort（内排序）从快速排序开始作为主要排序算法。在最坏情况下（例如，数组已经排序或接近排序），快速排序可能退化为O(n²)时间复杂度。为了避免快速排序的最坏情况，Introsort引入了一个最大递归深度。当递归深度超过这个阈值时，算法切换到堆排序或归并排序，以确保更好的最坏情况性能。

template <typename Tp>
int partition(vector<Tp>& nums, int lIdx, int rIdx) {
    int randomIndex = lIdx + rand() % (rIdx - lIdx + 1);
    std::swap(nums[randomIndex], nums[rIdx]);
    Tp pivot = nums[rIdx];
    int lBoundary = lIdx;
    int rBoundary = rIdx - 1;
    for(; ; ++lBoundary, --rBoundary){
        for (; lBoundary <= rBoundary && nums[lBoundary] < pivot; ++lBoundary) {}
        for (; lBoundary <= rBoundary && nums[rBoundary] > pivot; --rBoundary) {}
        if (lBoundary > rBoundary) {
            break;
        }
        std::swap(nums[lBoundary], nums[rBoundary]);
    }
    std::swap(nums[rIdx], nums[lBoundary]);
    return lBoundary;
}

过程示例

假设
nums = [7, 3, 5, 1, 2, 6, 4]
，随机选择的pivot下标为5，即6与最右的4交换，得到
nums = [7, 3, 5, 1, 2, 4, 6]
。
分区指针起始如图：
left (lIdx) -> 7, 3, 5, 1, 2, 4 <- right (rIdx), 6(pivot)
。
左指针移动到第一个大于或等于主元的元素(即7)，右指针移动到第一个小于或等于主元的元素(为4)：
left (lIdx) -> 7, 3, 5, 1, 2, 4 <- right (rIdx), 6(pivot)
。
交换左右指针处的元素：
left (lIdx) -> 4, 3, 5, 1, 2, 7 <- right (rIdx), 6(pivot)
。
继续该过程，直到左右指针相遇：
4, 3, 5, 1, 2 <- right (rIdx), left (lIdx) -> 7, 6(pivot)
。
将枢轴元素（当前位于右指针处）与左指针处的元素交换（6和7交换）。

非递归快速排序

实现

template <typename Tp>
void quickSort(vector<Tp>& nums) {
    std::stack<std::pair<int, int>> stack;
    stack.push(std::make_pair(0, nums.size() - 1));
    while (!stack.empty()) {
        std::pair<int, int> current = stack.top();
        stack.pop();
        int lIdx = current.first;
        int rIdx = current.second;
        if (lIdx < rIdx) {
            int boundary = partition(nums, lIdx, rIdx);
            stack.push(std::make_pair(lIdx, boundary - 1));
            stack.push(std::make_pair(boundary + 1, rIdx));
        }
    }
}

递归快速排序

实现

template <typename Tp>
void qSortRecursion(vector<Tp>& nums, const int& lIdx, const int& rIdx) {
    if (lIdx < rIdx) {
        int boundary = partition(nums, lIdx, rIdx);
        qSortRecursion(nums, lIdx, boundary - 1);
        qSortRecursion(nums, boundary + 1, rIdx);
    }
}
template <typename Tp>
void quickSort(vector<Tp>& nums) {
    qSortRecursion(nums, 0, nums.size() - 1);
}

有问题的Partition

实现

大量重复元素会超时:

template <typename Tp>
int partition(vector<Tp>& nums, int lIdx, int rIdx) {
    // 较为有序时, 避免超时
    int randIdx = lIdx + rand() % (rIdx - lIdx + 1);
    std::swap(nums[randIdx], nums[rIdx]);
 
    int pivot = nums[rIdx];
    int boundary = lIdx;
    for (int idx = lIdx; idx < rIdx; ++idx) {
        if (nums[idx] < pivot) {
            std::swap(nums[idx], nums[boundary]);
            ++boundary;
        }
    }
    std::swap(nums[boundary], nums[rIdx]); // pivot
    return boundary;
}

通过内排序Introsort修复:

template <typename Tp>
void quickSort(vector<Tp>& nums) {
    double recThreshold = log10(nums.size()) / log10(2);
    int recDepth = 0;
    std::stack<std::pair<int, int>> stack;
    stack.push(std::make_pair(0, nums.size() - 1));
    while (!stack.empty()) {
        ++recDepth;
        if (recDepth >= recThreshold) {
            heapSort(nums);
            break;
        }
        std::pair<int, int> current = stack.top();
        stack.pop();
        int lIdx = current.first;
        int rIdx = current.second;
        if (lIdx < rIdx) {
            int boundary = partition(nums, lIdx, rIdx);
            stack.push(std::make_pair(lIdx, boundary - 1));
            stack.push(std::make_pair(boundary + 1, rIdx));
        }
    }
}

三中位数主元选择

实现

template <typename Tp>
int choosePivot(vector<Tp>& nums, int lIdx, int rIdx) {
    int mid = lIdx + (rIdx - lIdx) / 2;
    if (nums[lIdx] > nums[mid]) {
        std::swap(nums[lIdx], nums[mid]);
    }
    if (nums[mid] > nums[rIdx]) {
        std::swap(nums[mid], nums[rIdx]);
    }
    if (nums[lIdx] > nums[mid]) {
        std::swap(nums[lIdx], nums[mid]);
    }
    return mid;
}
template <typename Tp>
int partition(vector<Tp>& nums, int lIdx, int rIdx) {
    int pivotIdx = choosePivot(nums, lIdx, rIdx);
    std::swap(nums[pivotIdx], nums[rIdx]);
    Tp pivot = nums[rIdx];
    int lBoundary = lIdx;
    int rBoundary = rIdx - 1;
    for(; ; ++lBoundary, --rBoundary){
        for (; lBoundary <= rBoundary && nums[lBoundary] < pivot; ++lBoundary) {}
        for (; lBoundary <= rBoundary && nums[rBoundary] > pivot; --rBoundary) {}
        if (lBoundary > rBoundary) {
            break;
        }
        std::swap(nums[lBoundary], nums[rBoundary]);
    }
    std::swap(nums[rIdx], nums[lBoundary]);
    return lBoundary;
}