#Leetcode 912 Sort an Array 快排 改进
2022/8/3 6:23:52
本文主要是介绍#Leetcode 912 Sort an Array 快排 改进,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
改进版快排,pivot 不再是左边第一个元素,而是正中间元素(或者随机)。
有一个比较坑的地方就是,在每一趟双指针完成所有交换后,需要判断 pivot 需不需要被交换。
比如 test case 1 2 4 3
,第一趟开始时 pivot 是 2, 先动右边的指针 j, 找到第一个比 2 小的数也就是 1。此时 1 不应该和 2 交换,否则会打破“每趟交换后,pivot 左边的数比 pivot 小,右边的数则更大”这一规则。
出现这个问题的原因就是指针 j 穿过了 pivot,那么就不知道这一轮 1 是最终的 pivot, 还是 2 是最终的 pivot。需要把相遇点和旧 pivot 比较后才能得出结论。
class Solution { public: vector<int> sortArray(vector<int>& nums) { if (nums.size() <= 1) return nums; if (is_sorted(nums.begin(), nums.end())) return nums; qsort(nums, 0, nums.size() - 1); return nums; } private: void qsort(vector<int>& vec, int l, int r) { if (l >= r) return; int pivot = l + (r - l) / 2, x = vec[pivot], i = l, j = r; while (i < j) { while (i < j && vec[j] >= x) --j; while (i < j && vec[i] <= x) ++i; if (i != j) swap(vec[i], vec[j]); } // Maybe cross the pivot, so may exchange pivot if (j < pivot && vec[j] > x) swap(vec[pivot], vec[j]); if (j > pivot && vec[j] < x) swap(vec[pivot], vec[j]); // 此时相遇点是新的 pivot qsort(vec, l, j); qsort(vec, j+1, r); } };
AcWing 的 Y 神给出了一个快排的模板,也挺好用,代码十分简洁,省去了判断 cross the pivot 后的各种处理, 两个指针相遇的位置就是最终 pivot 的位置。
不过也有比较细节的地方,比如:
- 使用了 do while 避免越界
- 不能在两个里层循环里面添加 i < j 的设定
- 比较关系是严格的大/小于
- 交换两个指针值的前提是 i < j
可以使用 test case 49 59 88 37 3 97 68 54 31 98
来分析这些细节。
class Solution { public: vector<int> sortArray(vector<int>& nums) { if (nums.size() <= 1) return nums; qsort(nums, 0, nums.size() - 1); return nums; } private: // ACWing Y 神的模板 void qsort(vector<int>& q, int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1; // 从开区间往中间遍历 int mid = l + (r - l) / 2, x = q[mid]; while (i < j) { // 太坑了, 这两个 while 不能添加 i < j 的设定! // 手动模拟了一遍,发现如果增加了 i < j 的设定,那么 j 的位置会偏移 1, 从而使得找到的区间有偏差 // 此时 i = j,但是 nums[i] = nums[j] > x,所以区间 [left, j] 包含了一个大于 x 的值 do ++i; while(q[i] < x); do --j; while(q[j] > x); if (i < j) swap(q[i], q[j]); } qsort(q, l, j); qsort(q, j+1, r); } };
这篇关于#Leetcode 912 Sort an Array 快排 改进的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!