(排序) 快速排序经典应用之快速选择

文章目录

⭐快速排序
- 🚩实现思路
- 🚩快排模板
⭐快速选择
- 🚩场景
- 🚩例题介绍 [lc1738. 找出第 K 大的异或坐标值]
- 🚩实现
⭐std::nth_element
- 🚩核心作用
- 🚩参数要求
- 🚩未定义条件
End

各种排序算法介绍：

(排序) 各种排序算法汇总_最新排序算法-CSDN博客

⭐快速排序

经典练习题：

912. 排序数组 - 力扣（LeetCode）

各种平台为了卡特殊情况，设置了长段有序数列，从而让快排的时间复杂度退化到了 $O(n^2)$

为了解决这个问题，要随机获得一个序列的值，以该值来快排，可以避免一直出现有序而效率退化的问题

🚩实现思路

传入区间是闭区间 $[f i rs t, l a s t]$

====================前置准备========================

（优化）在该区间内获得一个随机值，将该值交换到序列的某一端处（此处交换到最左端）
最左端的值作为比较值 int border = arr[left];
此时arr[left]是一个空位

====================执行划分========================

此时是左边有空置位置，所以先搜索右边
右边搜索完，存到左边的空置位置上
此时空置位置到了右边，开始搜索左边
。。。循环操作。。。
当left == right时终止
将最后的空置存储为最开始规定的border

==================一轮排序完毕======================

此时left处就是分割点
分治递归该分割点的两边

🚩快排模板

// lc912
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }

private:
    // [0, n - 1]
    void quickSort(vector<int>& arr, const int first, const int last) {
        if (first >= last) {
            return;
        }

        // （优化）随机取一个数
        // 避免每次取到固定位置上的数
        int randIdx = first + (rand() % (last - first + 1));
        swap(arr[randIdx], arr[first]);

        int left  = first;
        int right = last;
        // 获取对照值
        int border = arr[left];
        while (left < right) {
            // 过滤右侧符合的元素
            while (left < right && border <= arr[right]) {
                right += -1;
            }
            arr[left] = arr[right];
            // 过滤左侧符合的条件
            while (left < right && border >= arr[left]) {
                left += 1;
            }
            arr[right] = arr[left];
        }
        // left == right 退出
        // 此位置存储对照值
        arr[left] = border;

        const int borderIdx = left;
        quickSort(arr, first, borderIdx - 1);
        quickSort(arr, borderIdx + 1, last);
    }
};

⭐快速选择

🚩场景

这里的快速选择，指如下场景：

在序列arr中，要求获得第k大小的元素。如：

# 已知序列[0, n)
[8, 1, 9, 2, 0, 5, 7, 3, 4, 6]
# 要求获得第4小的数值，并保留在第4的位置
# 正常排序做法
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 理想实现
[8, 1, 9, 2, 4, 5, 7, 3, 0, 6]
# 基于快排思路的快速选择
[2, 1, 0, 3, 4, 5, 7, 8, 9, 6]

🚩例题介绍 [lc1738. 找出第 K 大的异或坐标值]

例题：

1738. 找出第 K 大的异或坐标值

本题是一个二维前缀和的模板题

但有一个附属需求就是要获得第k大的值，这就是经典的快速选择应用。

🚩实现

基于快速

其实原理非常简单，就是在快排进行分治递归时进行判断的进行递归。

对于得出的分解点borderIdx

正好是nth == borderIdx
- 则分治终止结束，达到了nth就是需要的第k大小
borderIdx < nth
- 说明还没满足nth个，因此要递归右侧
borderIdx > nth
- 说明满足了nth个，就是第k已经落在左侧了，但是没到第k的位置上，因此递归左侧

注意，这里抽象出一个比较规则，使用模板来进行传入。

namespace lotus {
// [first, last) 左闭区右开[0, n)
// 让第nth位置上，最终和正常排序后的结果一致
template <typename Compare>
void nth_element(vector<int>& arr, int first, int last, int nth, Compare comp) {
    if (first >= last) {
        return;
    }

    // 化为闭区间[left, right]
    int left  = first;
    int right = last - 1;
    // （优化）在范围内随机获取一个值
    int randIdx = left + (rand() % (right - left + 1));
    std::swap(arr[randIdx], arr[left]);

    // [快速排序]
    // 边界值（用于比较）
    int border = arr[left];
    while (left < right) {
        // 右侧 cmp == true
        while (left < right && comp(border, arr[right])) {
            right += -1;
        }
        arr[left] = arr[right];
        // 左侧 cmp == false
        while (left < right && !comp(border, arr[left])) {
            left += 1;
        }
        arr[right] = arr[left];
    }
    // while-end => left==right
    arr[left] = border;

    // 边界下标
    const int borderIdx = left;
    if (borderIdx == nth) {
        return;
    } else if (borderIdx < nth) {
        nth_element(arr, borderIdx + 1, last, nth, comp);
    } else if (borderIdx > nth) {
        nth_element(arr, first, borderIdx, nth, comp);
    }
}
}  // namespace lotus

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        /// [二维前缀和] begin
        const int           n = matrix.size();
        const int           m = matrix[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        vector<int>         arr;
        for (int i = 1; i <= n; i += 1) {
            for (int j = 1; j <= m; j += 1) {
                dp[i][j] = dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1] ^ matrix[i - 1][j - 1];
                arr.push_back(dp[i][j]);
            }
        }
        /// [二维前缀和] end

        // 化为[0, n)
        int nth = k - 1;
        lotus::nth_element(arr, 0, arr.size(), nth, greater<int>());
        return arr[nth];
    }
};

模仿std::nth_element

这里模仿了C++标准库的std::nth_element()的接口形式。

template <typename RandomIt, typename Compare>
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);

默认采用了随机迭代器的形式，可以直接比较相等，大小，递增n之类的。

namespace lotus {
// [first, last) 左闭区右开[0, n)
// 让第nth位置上，最终和正常排序后的结果一致
// 随机迭代器可以直接比较大小
template <typename RandomIt, typename Compare>
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp) {
    if (first == last) {
        return;
    }
    // （优化）在范围内随机获取一个值
    RandomIt randIdx = first + (rand() % std::distance(first, last));
    std::swap(*randIdx, *first);

    // 化为闭区间[left, right]
    RandomIt left  = first;
    RandomIt right = std::prev(last);
    // [快速排序]
    // 边界值（用于比较）
    const auto border = *left;
    while (left < right) {
        // 右侧 cmp == true
        while (left < right && comp(border, *right)) {
            right = std::prev(right);
        }
        *left = *right;
        // 左侧 cmp == false
        while (left < right && !comp(border, *left)) {
            left = std::next(left);
        }
        *right = *left;
    }
    // while-end => left==right
    *left = border;

    // nth划分递归
    const auto borderIdx = left;
    if (borderIdx == nth) {
        return;
    } else if (borderIdx < nth) {
        lotus::nth_element(std::next(borderIdx), nth, last, comp);
    } else if (borderIdx > nth) {
        lotus::nth_element(first, nth, borderIdx, comp);
    }
}
}  // namespace lotus

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        /// [二维前缀和] begin
        const int           n = matrix.size();
        const int           m = matrix[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        vector<int>         arr;
        for (int i = 1; i <= n; i += 1) {
            for (int j = 1; j <= m; j += 1) {
                dp[i][j] = dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1] ^ matrix[i - 1][j - 1];
                arr.push_back(dp[i][j]);
            }
        }
        /// [二维前缀和] end

        // 化为[0, n)
        int nth = k - 1;
        lotus::nth_element(arr.begin(), arr.begin() + nth, arr.end(), greater<int>());
        return arr[nth];
    }
};

⭐std::nth_element

最后稍微介绍下标准库的std::nth_element。

ref: std::nth_element - cppreference.com

在标头 <algorithm> 定义

// (C++20 起为 constexpr)
template <class RandomIt>
void nth_element(RandomIt first, RandomIt nth, RandomIt last);

// (C++17 起)
template <class ExecutionPolicy, class RandomIt>
void nth_element(ExecutionPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last);

// (C++20 起为 constexpr)
template <class RandomIt, class Compare>
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);

// (C++17 起)
template <class ExecutionPolicy, class RandomIt, class Compare>
void nth_element(ExecutionPolicy&& policy, RandomIt first, RandomIt nth, RandomIt last,
                 Compare comp);

在c++17后第一个参数，可以设定执行策略：(C++17) std算法之执行策略 execution

🚩核心作用

nth 指向的元素被更改为假如 [first, last) 已排序则该位置会出现的元素。

🚩参数要求

RandomIt 必须满足老式随机访问迭代器 (LegacyRandomAccessIterator) 。
Compare 必须满足比较 (Compare) 。

🚩未定义条件

[first, nth) 或 [nth, last) 不是有效范围。
(C++11 前)
- *first 的类型不可交换(Swappable) 。
(C++11 起)
- RandomIt 不可交换值 (ValueSwappable)。
- *first 的类型不可移动构造(MoveConstructible) 。
- *first 的类型不可移动赋值(MoveAssignable) 。