当前位置: 首页> 汽车> 维修 > 【数组分三段快排】分而治之的快排算法

【数组分三段快排】分而治之的快排算法

时间:2025/7/10 12:47:36来源:https://blog.csdn.net/2302_79031646/article/details/141612641 浏览次数: 0次

在这里插入图片描述

目录

  • 1.前言
  • 2.题目简介
  • 3.求解思路
  • 4.示例代码

1.前言

算法中的快排

2.题目简介

题目链接:LINK
在这里插入图片描述

3.求解思路

这个题很简单写一个快排就行。

数组分三段(分而治之):但是相对于我们之前写的霍尔版、挖坑法、交换法快排,这个题目可能有很多重复的数字,这些重复的数字无疑会大大提高栈帧消耗,很有可能导致崩溃。于是我们使用数组分三段的方法来做。
在这里插入图片描述
在这里插入图片描述

随机选key:之后为了进一步去优化,我们key值(中间参照值)可以随机取,不仅仅限于三数取中,在某些情况下比三数取中选key略好一点点。

4.示例代码

class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(nullptr));//种子qsort(nums, 0, nums.size() - 1);return nums;}void qsort(vector<int>& nums, int begin, int end){if(begin >= end) return;//1.选择基准值int key = getRandom(nums, begin, end);//2.数组分三块int left = begin - 1, right = end + 1;int i = begin;while(i < right){if(nums[i] < key){swap(nums[i++], nums[++left]);}else if(nums[i] == key){i++;}else //nums[i] > key{swap(nums[i], nums[--right]);}}//3.对其左右区域依次再次划分三块qsort(nums, begin, left);qsort(nums, right, end);} int getRandom(vector<int>& nums, int left, int right){int r = rand();return nums[r % (right - left + 1) + left];}
};

在这里插入图片描述


EOF

关键字:【数组分三段快排】分而治之的快排算法

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: