/images/avatar.png

算法学习之快速排序

本文是学习排序系列的第四篇,主要介绍较为常用的排序算法:快速排序

前文学习了归并排序,该排序算法采用了分治(divide and conquer, D&C)的思想,我们可以使用递归对输入序列进行排序。但是归并排序与输入序列的有序程度无关,并且需要额外创建线性的空间,这对于数据规模较大的场景不是很友好。

本文要学习的快速排序同样也是基于分治思想的排序算法,相比于归并,快排的空间复杂度为常数级别,在C中,sort方法的底层实现的原型就是qsort快速排序~