快速排序
liweiwei1419 ... 2021-12-23 Less than 1 minute
第 1 节到第 6 节是「快速排序」的内容,希望我这样的编排,读者能够感受到一点一点、层层递进,为了解决问题,而引入的逐步优化。
并且通过多次练习,掌握写对「快速排序」也不需要背代码,而是科学、合理地设计「循环不变量」,明确地知道每一个变量 的含义,进而把代码写对。
# 归并排序与快速排序都使用了「分治思想」
# 归并排序
- 拆分:不管数组的形态,总是将数组一分为二;
- 组合:合并两个有序的数组。
# 快速排序
拆分:根据某个元素
pivot
,将数组整理成两个部分;- 前半部分小于
pivot
, 后半部分大于等于pivot
; - 把
pivot
交换到前半部分的最后一个元素。
- 前半部分小于
组合:什么都不用做。