前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【优选算法篇】分治策略,速战速决:快速选择排序的神奇之处(下篇)

【优选算法篇】分治策略,速战速决:快速选择排序的神奇之处(下篇)

作者头像
熬夜学编程的小王
发布于 2024-12-24 02:22:22
发布于 2024-12-24 02:22:22
16900
代码可运行
举报
文章被收录于专栏:编程小王编程小王
运行总次数:0
代码可运行

须知

💬 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力! 👍 点赞、收藏与分享:觉得这篇文章对你有帮助吗?别忘了点赞、收藏并分享给更多的小伙伴哦!你们的支持是我不断进步的动力! 🚀 分享给更多人:如果你觉得这篇文章对你有帮助,欢迎分享给更多对C++算法感兴趣的朋友,让我们一起进步!

接上篇: 【优选算法篇】揭秘快速排序:分治算法如何突破性能瓶颈(上篇)-CSDN博客

引言:通过上篇文章带大家简单了解“分治(快速排序)算法”,小试牛刀。接下来将让大家感受一下分治(快速排序)在解题的更多妙处。

1. C++ 分治(快速选择排序)算法详解

1.1 分治法的定义:

分治法是一种将一个大问题分解为多个子问题并解决这些子问题的策略,通常包含三个步骤:

  • 分解(Divide): 将原始问题分解成多个子问题。
  • 解决(Conquer): 递归地解决每个子问题。
  • 合并(Combine): 将子问题的解合并成原始问题的解。

分治法的关键在于能否将问题成功分解,并且保证每个子问题都能被有效解决。

1.2 快速选择排序(Quick Select)算法的核心思想:

快速选择排序(Quick Select)是一种基于快速排序思想的选择算法,它用于找到数组中的第 k 小元素,而不是对数组进行完全排序。它的核心思想如下:

  • 与快速排序类似,选择一个“枢纽”(pivot)元素,通常使用“三数取中法”选择枢纽,以避免最坏情况。
  • 将数组分成两部分:
    • 左边部分包含所有小于枢纽的元素。
    • 右边部分包含所有大于枢纽的元素。
  • 根据第 k 小元素的位置来决定递归的方向:
    • 如果第 k 小元素在左部分,则递归在左部分继续查找。
    • 如果第 k 小元素在右部分,则递归在右部分继续查找。
    • 如果第 k 小元素就是枢纽元素的位置,则直接返回该元素。
1.3 快速选择排序的应用:

快速选择排序的经典应用主要集中在以下几个领域:

  • 寻找第 k 小/大元素: 在实际应用中,快速选择排序广泛用于查找数据集合中的第 k 小或第 k 大的元素,尤其在大数据量的处理下,能够有效减少时间复杂度。
  • 数据分析和统计: 在数据分析中,常常需要查找排名前 k 的数据项,快速选择排序在这些场景中表现出色。
  • 排名算法: 在搜索引擎中,用于排名结果时,快速选择排序可以高效地找出前 k 个最相关的文档。
1.4 快速选择排序的优势和重要性:
  • 时间复杂度: 快速选择排序的平均时间复杂度为 O(n),而最坏情况为 O(n²)(类似于快速排序),但通过三数取中法或随机选择枢纽,可以大大降低最坏情况发生的概率。大多数情况下,快速选择排序的时间复杂度为 O(n),比起需要完全排序的 O(n log n) 快速排序来说要高效得多。
  • 空间复杂度: 快速选择排序是原地排序算法,不需要额外的存储空间,所以它的空间复杂度为 O(1),比其他排序算法(如归并排序)的 O(n) 空间复杂度要好。
  • 经典的分治法应用: 快速选择排序是分治法的经典应用之一,通过选择合适的枢纽,将原问题分解为两个子问题,在不断缩小问题规模的过程中找到第 k 小的元素。
1.5 快速选择排序的核心思想:

快速选择排序的核心思想是在分治法框架下进行快速查找第 k 小元素,步骤包括:

  1. 选择枢纽(Pivot): 选择一个枢纽元素,可以使用三数取中法来避免极端情况。
  2. 分区(Partition): 将数组按照枢纽分成两部分,左边部分小于枢纽,右边部分大于枢纽。
  3. 定位第 k 小元素:
    • 如果枢纽正好位于第 k 小元素的位置,返回枢纽。
    • 如果第 k 小元素在左部分,递归地在左部分查找。
    • 如果第 k 小元素在右部分,递归地在右部分查找。
1.6 快速选择排序的代码示例:
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
#include <vector>
#include <algorithm>

// 分区函数
int partition(std::vector<int>& nums, int left, int right) {
    int pivot = nums[right];  // 选择最右边的元素作为枢纽
    int i = left - 1;
    
    for (int j = left; j < right; ++j) {
        if (nums[j] < pivot) {
            i++;
            std::swap(nums[i], nums[j]);
        }
    }
    std::swap(nums[i + 1], nums[right]);
    return i + 1;
}

// 快速选择函数
int quickSelect(std::vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];  // 只有一个元素时直接返回
    
    int pivotIndex = partition(nums, left, right);
    
    if (k == pivotIndex) {
        return nums[k];  // 如果枢纽位置就是第 k 小元素,返回它
    } else if (k < pivotIndex) {
        return quickSelect(nums, left, pivotIndex - 1, k);  // 在左半部分查找
    } else {
        return quickSelect(nums, pivotIndex + 1, right, k);  // 在右半部分查找
    }
}

int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;  // 查找第 2 小的元素
    std::cout << "The " << k << "th smallest element is: " << quickSelect(nums, 0, nums.size() - 1, k - 1) << std::endl;
    return 0;
}
1.7 总结:
  • 快速选择排序利用分治法对数组进行分区,递归地查找第 k 小元素,避免了排序整个数组的高时间复杂度。
  • 它的平均时间复杂度为 O(n),适合用于大规模数据集中的选择问题,尤其是在只需要找到某个特定位置的元素而不是排序整个数组时。
  • 通过灵活选择枢纽元素(如三数取中法或随机选择),可以有效降低最坏情况的发生概率,确保算法的高效性。

2. 题目1:数组中第k个最大元素

题目链接:215. 数组中的第K个最大元素 - 力扣(LeetCode)

题目描述:

2.1 算法思路:

核心算法思想

  • 快速排序的核心思想是通过选择一个基准元素(pivot),将数组分为两个部分:一部分小于基准元素,另一部分大于基准元素。在对每一部分继续递归排序后,整个数组被排序好。
  • 快速选择的思想是类似的,但与快速排序不同,快速选择只关心第 k 大的元素,而不需要对整个数组排序。通过在每次分区后缩小查找的范围,最终定位到第 k 大的元素。

算法流程

  1. 随机化: 通过 getRandom() 函数随机选择一个基准元素(pivot),这能够避免最坏情况(即每次选择的基准元素是当前子数组的最大或最小元素,导致退化为 O(n²) 的时间复杂度)。
  2. 三路分区: 使用三路分区算法(Dutch National Flag Algorithm)将数组分为三部分:
    • 小于基准元素的部分。
    • 等于基准元素的部分。
    • 大于基准元素的部分。
  3. 递归选择: 根据第 k 大元素的位置决定下一步递归:
    • 如果第 k 大元素在右边部分,递归到右边部分。
    • 如果第 k 大元素就是基准元素,直接返回基准元素。
    • 如果第 k 大元素在左边部分,递归到左边部分。
  4. 返回结果: 最终找到第 k 大元素时返回。
2.2 代码实现:
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution 
{
public:
    // 主函数,找到数组中的第 k 大元素
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(NULL));  // 使用当前时间初始化随机数生成器,确保每次执行时选择不同的基准元素
        return qsort(nums, 0, nums.size() - 1, k);  // 调用快速选择算法的主函数
    }

    // 快速选择算法的递归实现,返回第 k 大元素
    int qsort(vector<int>& nums, int l, int r, int k)
    {
        if (l == r) return nums[l];  // 如果当前子数组只剩下一个元素,直接返回该元素

        int i = l, left = l - 1, right = r + 1;  // 初始化三个指针:i、left 和 right
        int key = getRandom(nums, l, r);  // 随机选择一个基准元素

        // 三路分区:小于基准、等于基准和大于基准
        while (i < right)
        {
            if (nums[i] < key) 
                swap(nums[++left], nums[i++]);  // 如果 nums[i] 小于基准,移动到左侧
            else if (nums[i] == key) 
                i++;  // 如果 nums[i] 等于基准,跳过当前元素
            else 
                swap(nums[i], nums[--right]);  // 如果 nums[i] 大于基准,移动到右侧
        }

        // 计算基准元素在数组中所占的大小
        int b = right - left - 1;  // 等于基准元素的数量
        int c = r - right + 1;     // 大于基准元素的数量

        // 根据第 k 大元素的位置来决定下一步的递归
        if (c >= k) 
            return qsort(nums, right, r, k);  // 如果第 k 大元素在右侧部分,递归右部分
        else if (b + c >= k) 
            return key;  // 如果第 k 大元素是基准元素,返回基准元素
        else 
            return qsort(nums, l, left, k - b - c);  // 否则,第 k 大元素在左侧部分,递归左部分
    }

    // 随机选择一个基准元素
    int getRandom(vector<int>& nums, int left, int right)
    {
        int n = rand();  // 生成一个随机数
        return nums[n % (right - left + 1) + left];  // 从区间 [left, right] 中随机选择一个元素
    }
};
2.2.1 代码解读
  1. findKthLargest:
    • 接受一个整数数组 nums 和一个整数 k,返回数组中第 k 大的元素。
    • 使用 srand(time(NULL)) 来初始化随机数种子,确保每次运行时随机数不同。
    • 调用 qsort 函数来执行快速选择算法,查找第 k 大元素。
  2. qsort (快速选择算法):
    • 接受参数:nums(数组),l(子数组的左边界),r(子数组的右边界),k(第 k 大的元素)。
    • if (l == r):如果子数组只包含一个元素,直接返回该元素。
    • 随机选择一个基准元素 key,并使用三路分区法(类似于快速排序)将数组分为三个部分:小于基准、大于基准和等于基准。
    • 根据分区结果,递归地选择下一部分来查找第 k 大的元素。
  3. 三路分区法:
    • leftright 分别指向小于基准和大于基准的元素的边界,i 用来遍历数组。
    • 如果 nums[i] < key,将 nums[i] 移到小于基准的部分。
    • 如果 nums[i] == key,保持该元素位置不动,继续扫描。
    • 如果 nums[i] > key,将 nums[i] 移到大于基准的部分。
  4. 递归逻辑:
    • 根据分区后的情况判断第 k 大元素的位置:
      • 如果第 k 大元素在右侧(大于基准的部分),递归右部分。
      • 如果第 k 大元素正好是基准元素,返回基准元素。
      • 如果第 k 大元素在左侧(小于基准的部分),递归左部分。
  5. getRandom:
    • 用于从 [left, right] 范围内随机选择一个元素作为基准。通过 rand() 生成一个随机数,并利用模运算确保结果在给定区间内。
2.3 多种解法
2.3.1 解法2: 堆(Heap)

使用堆(通常是最小堆)可以有效地找到数组中的第 K 大元素。通过构建一个大小为 K 的最小堆,堆中的最小元素将始终是第 K 大元素。

算法思路:

  • 创建一个最小堆,堆的大小为 K。
  • 遍历数组,对于每个元素:
    • 如果堆中有不到 K 个元素,则直接加入堆。
    • 如果堆已满且当前元素大于堆顶元素,则替换堆顶元素。
  • 最终,堆顶元素就是第 K 大元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;  // 创建一个最小堆
        for (int num : nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop();  // 维持堆的大小为 k
            }
        }
        return minHeap.top();  // 堆顶元素即为第 k 大元素
    }
};

时间复杂度:

  • 插入每个元素的时间复杂度是 O(log k),因此整个过程的时间复杂度为 O(n log k)。
2.3.2 解法3:排序法

最直接的解法是将数组排序,然后返回排序后数组的第 K 个元素。由于排序的时间复杂度为 O(n log n),这虽然简单,但在效率上不如快速选择和堆。

算法思路:

  • 对数组进行排序,返回数组中倒数第 K 个元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k - 1];  // 排序后返回第 K 个元素
    }
};

时间复杂度:

  • 排序的时间复杂度为 O(n log n)。
2.3.3 解法4:快排(快速排序)

快速排序可以修改为只排序部分数组,达到在 O(n log n) 时间内找到第 K 大元素。通过每次递归仅对部分数组进行排序来优化。

算法思路:

  • 对数组进行快速排序,只排序包含第 K 大元素的部分。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        quickSort(nums, 0, nums.size() - 1, k);
        return nums[k - 1];
    }

    void quickSort(vector<int>& nums, int left, int right, int k) {
        if (left < right) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == k - 1) return;
            else if (pivotIndex < k - 1) quickSort(nums, pivotIndex + 1, right, k);
            else quickSort(nums, left, pivotIndex - 1, k);
        }
    }

    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        swap(nums[i], nums[right]);
        return i;
    }
};

时间复杂度:

  • 最坏情况下时间复杂度为 O(n^2),但平均情况下是 O(n log n)。
2.3.4 解法5:计数排序法(桶排序)

如果数组中的元素范围比较小,可以使用计数排序来找出第 K 大元素。计数排序在元素范围已知且较小的情况下非常高效。

算法思路:

  • 统计每个元素出现的次数,然后从最大元素开始统计,直到找到第 K 大的元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int maxNum = *max_element(nums.begin(), nums.end());
        vector<int> count(maxNum + 1, 0);
        
        // 统计每个数字的出现频率
        for (int num : nums) {
            count[num]++;
        }

        // 从最大值开始查找第 K 大元素
        for (int i = maxNum; i >= 0; i--) {
            if (count[i] > 0) {
                k -= count[i];
                if (k <= 0) return i;
            }
        }
        return -1;  // 默认情况不应到达
    }
};

时间复杂度:

  • 计数排序的时间复杂度为 O(n + m),其中 n 是数组的大小,m 是元素的范围。
2.3.5 总结
  • 快速选择算法(Quick Select):时间复杂度为 O(n)(平均情况),适用于大多数情况,避免了不必要的排序。
  • 堆排序法(Heap):时间复杂度为 O(n log k),适合 K 较小的情况。
  • 排序法:时间复杂度为 O(n log n),简单易懂,但效率较低。
  • 快速排序:O(n log n),但可以通过调整递归范围来优化。
  • 计数排序法:适用于元素范围较小的情况,时间复杂度为 O(n + m)。
2.4 算法的时间复杂度
  • 平均时间复杂度: 在平均情况下,快速选择算法的时间复杂度为 O(n),因为每次分区后,问题规模大约减半。
  • 最坏时间复杂度: 在最坏情况下(每次选择的基准元素都是最小或最大的元素),时间复杂度退化为 O(n²)。但是,随机选择基准元素大大减少了最坏情况发生的概率。
  • 空间复杂度: 快速选择算法的空间复杂度是 O(1),因为它是原地操作,不需要额外的存储空间。
2.5 总结

该算法实现了 快速选择(Quick Select)算法来查找数组中的第 k 大元素,使用了随机化和三路分区的策略来提高效率。通过随机选择基准元素,避免了最坏情况的发生,通常在平均情况下,算法的时间复杂度为 O(n),比直接排序(O(n log n))更高效。

3. 题目2:面试题 17.14. 最小k个数

题目链接:面试题 17.14. 最小K个数 - 力扣(LeetCode)

题目描述:

3.1 算法思路:

  1. 随机化快速选择(Quick Select):
    • 快速选择算法通过选择一个随机基准(pivot),然后将数组分为三部分:
      1. 小于基准的部分
      2. 等于基准的部分
      3. 大于基准的部分
    • 通过递归选择包含第 K 个最小元素的那部分来找到前 K 小的元素。
  2. 核心操作:
    • qsort 是一个递归函数,其目标是根据基准值将数组分为两部分,最终将最小的 K 个元素放到数组的前 K 个位置。
    • 选择一个随机的基准元素,然后通过三路划分(Three-way partition)将数组分为三部分。
    • 递归的调整左右边界,直到得到前 K 个最小的元素。
3.2 代码实现:
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution 
{
public:
    vector<int> smallestK(vector<int>& arr, int k) 
    {
        srand(time(NULL));  // 初始化随机数种子
        qsort(arr, 0, arr.size()-1, k);  // 调用快速选择函数

        return {arr.begin(), arr.begin() + k};  // 返回数组中最小的 K 个元素
    }

    void qsort(vector<int>& arr, int l, int r, int k)
    {
        if(l >= r) return;  // 如果区间内只有一个元素,结束递归

        int left = l - 1, right = r + 1, i = l;
        int key = getRandom(arr, l, r);  // 随机选择一个基准元素
        while(i < right)
        {
            if(arr[i] < key) 
                swap(arr[++left], arr[i++]);  // 将小于基准的元素移到左边
            else if(arr[i] == key) 
                i++;  // 如果等于基准元素,直接跳过
            else 
                swap(arr[--right], arr[i]);  // 将大于基准的元素移到右边
        }

        int a = left - l + 1, b = right - left - 1;

        if(a > k) 
            qsort(arr, l, left, k);  // 如果前 a 个元素已经包含了 K 个最小的元素,递归左半部分
        else if(a + b >= k) 
            return;  // 如果已经找到前 K 个最小的元素,结束
        else 
            qsort(arr, right, r, k - a - b);  // 否则递归右半部分
    }

    int getRandom(vector<int>& arr, int left, int right)
    {
        return arr[rand() % (right - left + 1) + left];  // 随机选择一个基准元素
    }
};
3.2.1 核心步骤解析:
  1. smallestK 函数:
    • 输入:arr(整数数组),k(需要找到最小的 K 个元素)。
    • 调用 qsort 进行快速选择,递归地确定前 K 个最小的元素,并且返回前 K 个元素作为结果。
  2. qsort 函数:
    • 这是一个递归函数,通过快速选择算法实现。
    • 三路划分:通过随机选择一个基准元素,将数组分为三个部分:
      • 小于基准的部分
      • 等于基准的部分
      • 大于基准的部分
    • 递归地处理包含最小 K 个元素的部分,直到找到第 K 小元素。
  3. getRandom 函数:
    • 用于从数组的子区间中随机选择一个元素作为基准。
    • rand() % (right - left + 1) + left 是一个经典的随机选择区间元素的方法。

递归分治过程:

  • 假设我们每次选择一个基准元素,然后将数组分成了小于基准、等于基准和大于基准的三部分:
    • a:表示小于基准的元素数量。
    • b:表示等于基准的元素数量。
  • 如果 a >= k,意味着最小的 K 个元素都在基准左边,因此递归处理左边部分。
  • 如果 a + b >= k,说明当前基准元素是第 K 小的元素,直接返回,不需要再递归。
  • 如果 a + b < k,递归处理右边部分,寻找剩余的第 k - a - b 小的元素。
3.3 多种解法
3.3.1 解法 2:排序法

最直观的方法是对数组进行排序,然后返回前 k 个元素。

步骤:

  1. 对数组 arr 进行升序排序。
  2. 返回排序后的前 k 个元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());  // 对数组进行升序排序
        return vector<int>(arr.begin(), arr.begin() + k);  // 返回前 k 个元素
    }
};

时间复杂度:

  • 排序的时间复杂度是 O(nlogn),其中 n 是数组的长度。
  • 返回前 k 个元素的时间复杂度是 O(k),但通常可以认为 O(k)O(nlogn) 要小,因此总时间复杂度是 O(nlogn)

空间复杂度:

  • 使用了 O(n) 的额外空间来存储排序后的数组。

3.3.2 解法 3:最小堆(优先队列)

使用最小堆来维护当前数组中最小的 k 个元素。可以通过构建一个大小为 k 的最小堆来解决。

步骤:

  1. 使用一个大小为 k 的最小堆(或者最大堆,下面我们将使用最大堆)。
  2. 遍历数组的每个元素:
    • 如果堆的大小小于 k,则直接将当前元素加入堆中。
    • 如果堆的大小已经达到 k,则与堆顶元素比较,如果当前元素更小,则弹出堆顶元素,并将当前元素加入堆中。
  3. 最终堆中存储的就是最小的 k 个元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <queue>

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        priority_queue<int> maxHeap;  // 最大堆
        for (int num : arr) {
            if (maxHeap.size() < k) {
                maxHeap.push(num);  // 堆的大小小于 k,直接加入
            } else if (num < maxHeap.top()) {
                maxHeap.pop();  // 弹出堆顶元素
                maxHeap.push(num);  // 加入当前元素
            }
        }

        vector<int> result;
        while (!maxHeap.empty()) {
            result.push_back(maxHeap.top());
            maxHeap.pop();
        }
        reverse(result.begin(), result.end());  // 由于是最大堆,最后要反转结果
        return result;
    }
};

时间复杂度:

  • 对于每个元素的操作(插入堆或删除堆顶元素)需要 O(log k) 时间。
  • 遍历整个数组需要 O(n) 次操作。
  • 因此,总时间复杂度为 O(n log k)

空间复杂度:

  • 使用一个大小为 k 的堆,空间复杂度为 O(k)

3.3.3 解法4: 使用排序并维护最小 k 个元素

这是一种通过逐步维护前 k 个元素的方法。可以使用 std::partial_sort 来高效地获取数组的前 k 个最小元素。

步骤:

  1. 使用 std::partial_sort 对数组进行排序,只将前 k 个元素排序,而不对整个数组进行排序。
  2. 返回前 k 个元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <algorithm>

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        partial_sort(arr.begin(), arr.begin() + k, arr.end());
        return vector<int>(arr.begin(), arr.begin() + k);
    }
};

时间复杂度

  • std::partial_sort 的时间复杂度是 O(n log k)

空间复杂度

  • 空间复杂度为 O(n),主要是由于排序时可能需要额外的空间。
3.3.4 总结:
3.4 时间复杂度:
  • 平均情况下,快速选择的时间复杂度为 O(n),因为它通过递归缩小问题规模,每次将数组分成两部分,平均每次会处理约一半的元素。
  • 最坏情况下,时间复杂度为 O(n^2),但通过随机选择基准元素可以避免最坏情况,因此大多数情况下是 O(n)。

优点:

  • 效率高:由于快速选择算法的平均时间复杂度为 O(n),该方法在实际应用中通常表现很好,尤其是当 k 比较小或者数组很大的时候。
  • 避免了不必要的排序:与全排序(时间复杂度 O(n log n))相比,快速选择通过分治策略避免了对整个数组的排序,只聚焦于最小的 K 个元素,节省了计算时间。

缺点:

  • 最坏情况较差:虽然通过随机化可以减少最坏情况的出现,但最坏情况的时间复杂度仍然是 O(n^2),需要注意。
3.5 总结:

这段代码通过 快速选择算法 来有效地找到数组中最小的 K 个元素。算法利用随机化技术避免了最坏情况,并通过分治策略将时间复杂度保持在 O(n)(平均情况下),非常适合大规模数据的处理。

4.总结

我们发现,排序法适用于简单场景,最小堆适合 K 较小的数据集,快速选择算法在大数据量下效率最高,部分排序法则能够快速得到前 K 个元素,尤其适用于空间敏感和实时计算的场景。

在处理数组元素的选择问题时,选择合适的算法不仅能提高效率,也能在大数据和高性能计算需求中展现出明显优势,特别是在 时间复杂度敏感数据量较大的 应用中。

5.最后

通过上面几个例题:「最小的 K 个数字」的多种解法「快速选择算法」的应用最小堆排序、以及排序法,我们总结出高效解决数组中最小 K 个元素问题的几种常见策略。 排序法最小堆快速选择算法部分排序法在数组问题中有着广泛的应用。它们的本质是在数组中寻找前 K 个元素,虽然方法不同,但都具有显著的时间复杂度优化特性。

  • 排序法通过将数组完全排序,然后截取前 K 个元素,简单易懂,但其时间复杂度较高,适用于元素数量不大或要求实现简单的场景。
  • 最小堆方法通过构建堆来维护前 K 个最小的元素,它的优势在于时间复杂度为 O(n log k),特别适合大规模数据且 K 较小的情况,常用于实时数据处理。
  • 快速选择算法通过分治法(与快速排序类似)定位第 K 小的元素,平均时间复杂度为 O(n),其空间复杂度较低,适用于处理大数据集时提高效率,特别适用于要求时间效率高且能够容忍最坏情况的应用。
  • 部分排序法使用 partial_sort 来进行部分排序,只排序前 K 个元素,时间复杂度为 O(n log k),它能够在不完全排序的情况下快速获得结果,适合对部分元素有要求的场景。

路虽远,行则将至;事虽难,做则必成

亲爱的读者们,下一篇文章再会!!!

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-12-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
看一遍就理解:order by详解!
日常开发中,我们经常会使用到order by,亲爱的小伙伴,你是否知道order by 的工作原理呢?order by的优化思路是怎样的呢?使用order by有哪些注意的问题呢?本文将跟大家一起来学习,攻克order by~
macrozheng
2021/07/02
1.4K0
看一遍就理解:order by详解!
面试官:order by 怎么优化?
刚换了新工作,用了两周时间准备,在 3 天之内拿了 5 个 offer,最后选择了广州某互联网行业独角兽 offer,昨天刚入职。这几天刚好整理下在面试中被问到有意思的问题,也借此机会跟大家分享下。
JavaFish
2021/07/05
2.5K0
面试官:order by 怎么优化?
MySQL排序内部原理探秘
一、我们要解决什么问题 二、排序,排序,排序 三、索引优化排序 四、排序模式 4.1实际trace结果 4.2排序模式概览 4.2.1回表排序模式 4.2.2不回表排序模式 4.2.3打包数据排序模式 4.2.4三种模式比较 五、外部排序 5.1普通外部排序 5.1.1两路外部排序 5.1.2多路外部排序 5.2MySQL外部排序 5.2.1MySQL外部排序算法 5.2.2sort_merge_passes 六、trace 结果解释 6.1 是否存在磁盘外部排序 6.2 是否存在优先队列优
沃趣科技
2018/03/26
2.7K0
MySQL排序内部原理探秘
mysql 之order by工作流程
Extra 中 Using index condition; 这个是之前文章中提到的索引下推 ICP Using filesort 这个表示需要排序 mysql会给每个线程分配一块内存 叫做sort_buffer
科技新语
2025/03/20
840
mysql 之order by工作流程
MySQL order by 是怎么工作的?
这个排序过程叫做全字段排序,因为需要返回的字段都放入了 sort_buffer 参与排序过程。
dys
2019/05/13
1.8K0
MySQL order by 是怎么工作的?
Mysql中orderby底层执行流程
前言 在实际的开发中一定会碰到根据某个字段进行排序后来显示结果的需求,但是你真的理解order by在 Mysql 底层是如何执行的吗? 假设你要查询城市是苏州的所有人名字,并且按照姓名进行排序返回前 1000 个人的姓名、年龄,这条 sql 语句应该如何写? 首先创建一张用户表,sql 语句如下: CREATE TABLE user ( id int(11) NOT NULL, city varchar(16) NOT NULL, name varchar(16) NOT NULL, ag
爱撒谎的男孩
2020/04/21
2K0
Mysql中orderby底层执行流程
MySQL - order by 出现 using filesort根因分析及优化
当然了实际工作中是基本不会出现这种情况的, 假设真的取了100万数据, 无论是MySQL内存缓冲区的占用,还是网络带宽的消耗都是巨大的。
小小工匠
2021/11/10
6.8K1
MySQL - order by 出现 using filesort根因分析及优化
MySQL Order By工作原理
Extra中包含Using filesort表示需要排序,在排序时,MySQL会为每个线程分配一块内存区域用于排序,称之为sort_buffer。
shysh95
2022/02/16
8640
MySQL Order By工作原理
order by 原理以及优化
一 简介 偏向于业务的(MySQL)DBA或者业务的开发者来说,order by 排序是一个常见的业务功能,将结果根据指定的字段排序,满足前端展示的需求。然而排序操作也是经常出现慢查询排行榜的座上宾。本文将从原理和实际案例优化,order by 使用限制等几个方面来逐步了解order by 排序。
用户1278550
2018/08/09
7610
order by的工作原理
where条件后面是city字段,然后根据name排序,可以看到,执行计划中有:using filesort字样。这是因为name字段没有索引,所以需要借助sort_buffer来进行排序操作。
AsiaYe
2020/06/22
7540
MySQL排序原理与优化方法(9/16)
**内存临时表排序:**在MySQL中,使用InnoDB引擎执行排序操作时,当处理的数据量较小,可以在内存中完成排序时,MySQL会优先使用内存进行排序操作。在这种情况下,MySQL会创建一个临时内存表来存储排序结果,这样可以快速地对数据进行排序,提高查询效率。
十里桃花舞丶
2024/04/12
2480
MySQL怎样处理排序⭐️如何优化需要排序的查询?
在MySQL的查询中常常会用到 order by 和 group by 这两个关键字
菜菜的后端私房菜
2024/06/21
3240
工作中遇到的99%SQL优化,这里都能给你解决方案(二)
利用最左前缀法则:中间字段不能断,因此查询用到了name索引,从key_len=74也能看出,age索引列用在排序的过程中,因为Extra字段里没有using filesort。
程序员小强
2019/09/10
5020
工作中遇到的99%SQL优化,这里都能给你解决方案(二)
Mysql order by 优化
本节描述MySQL何时可以使用索引来满足ORDER BY子句,当不能使用索引时使用filesort,以及优化器中有关ORDER BY的执行计划信息。
XING辋
2019/03/26
1.5K0
Mysql进阶优化篇05——子查询的优化和排序优化
MySQL 从 4.1 版本开始支持子查询,使用子查询可以进行 SELECT 语句的嵌套查询,即一个 SELECT 查询的结果作为另一个 SELECT 语句的条件。子查询可以一次性完成很多逻辑上需要多个步骤才能完成的操作 。
半旧518
2022/10/26
2.4K0
Mysql进阶优化篇05——子查询的优化和排序优化
盘点MySQL慢查询的12个原因
日常开发中,我们经常会遇到数据库慢查询。那么导致数据慢查询都有哪些常见的原因呢?今天田螺哥就跟大家聊聊导致MySQL慢查询的12个常见原因,以及对应的解决方法。
捡田螺的小男孩
2023/02/24
1.6K0
盘点MySQL慢查询的12个原因
MySQL Order By实现原理分析和Filesort优化
在使用explain分析查询的时候,利用有序索引获取有序数据显示Using index。而文件排序显示Using filesort。
黄规速
2022/04/14
1.5K0
MySQL Order By实现原理分析和Filesort优化
Mysql的SQL优化指北
在一次和技术大佬的聊天中被问到,平时我是怎么做Mysql的优化的?在这个问题上我只回答出了几点,感觉回答的不够完美,所以我打算整理一次SQL的优化问题。
luozhiyun
2020/02/11
1K0
浅谈MySQL分页查询的工作原理
MySQL 的分页查询在我们的开发过程中还是很常见的,比如一些后台管理系统,我们一般会有查询订单列表页、商品列表页等。
政采云前端团队
2023/11/09
2.2K0
浅谈MySQL分页查询的工作原理
mysql中走与不走索引的情况汇集(待全量实验)
在MySQL中,并不是你建立了索引,并且你在SQL中使用到了该列,MySQL就肯定会使用到那些索引的,有一些情况很可能在你不知不觉中,你就“成功的避开了”MySQL的所有索引。
小勇DW3
2020/07/23
11.6K2
推荐阅读
相关推荐
看一遍就理解:order by详解!
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档