Go 数据结构和算法篇（八）：快速排序

文章预览

一、实现原理 归并排序算法虽好，但是不是原地排序算法，需要消耗额外的内存空间，今天我们要介绍的是常规排序里综合排名最高的排序算法：快速排序，江湖人称「快排」。 快排的核心思想是这样的： 如果要排序数据序列中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot （分区点），假设对应下标是 q 。 遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数据序列 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot ，后面的 q+1 到 r 之间是大于 pivot 的。 图示如下： 快速排序图示 根据分治、递归的处理思 ………………………………