search

krahets / hello-algo

《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 代码。简体版和繁体版同步更新，English version ongoing
https://hello-algo.com
Other
86.4k stars 10.96k forks source link

11.5快速排序 #1355

Closed gggggwen closed 2 months ago

gggggwen commented 2 months ago

1.关于11.5.5快速排序的尾递归优化,只选取了较短子路径进行递归操作,而较长那一部分数组没有进行处理 2.我想请教一下关于快速排序:中partition函数里面:while循环内先找第一个大于再找第一个小于不能够完成排序,这是为什么?算法书里面没有详细解释 屏幕截图 2024-05-10 162212

rongyi commented 2 months ago

尝试回答一下你，

  1. 注意外围的while循环，在选择较短的一部分排序之后会对应调整left/right，你可以认为较短一块已经排好序(递归下去可以暂时忽略），然后while循环又去处理没排好序的部分去了。
  2. partition是从右找比参照点： arr[left] 小的，从左找比参数点大的数，然后进行交换，为什么要交换？ 因为我们默认大于参照点的“站”右边，所以从右找不合规范的小。小于等于“站”左边。原因类似。然后一直循环这样的操作。partion本身不是排序，只能笼统的分去左右两个区间。这也是快排里一直递归下去的原因，小到长度为2时就严格了
krahets commented 2 months ago

这个问题在本章小结的 Q&A 中有分析哈