快速排序

liweiwei1419 ... 2021-12-23 快速排序
  • 快速排序
  • 分治思想
Less than 1 minute

第 1 节到第 6 节是「快速排序」的内容,希望我这样的编排,读者能够感受到一点一点、层层递进,为了解决问题,而引入的逐步优化。

并且通过多次练习,掌握写对「快速排序」也不需要背代码,而是科学、合理地设计「循环不变量」,明确地知道每一个变量 的含义,进而把代码写对。

image-20211207114944124

# 归并排序与快速排序都使用了「分治思想」

# 归并排序

  • 拆分:不管数组的形态,总是将数组一分为二;
  • 组合:合并两个有序的数组。

# 快速排序

  • 拆分:根据某个元素 pivot,将数组整理成两个部分;

    • 前半部分小于 pivot, 后半部分大于等于 pivot
    • pivot 交换到前半部分的最后一个元素。
  • 组合:什么都不用做。

Last update: May 2, 2022 13:25
Contributors: suanfa8 , liweiwei1419