核心思想:
(1)要排序的一组数据中取一个数为“基准数”
(2)通过一趟排序将要排序的数据分割成独立的两部分,其中左边的数据都比“基准数”小,右边的数据都比“基准数”大。
(3)重复步骤2,对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
分治:是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。应用于快速排序,归并排序,傅立叶变换等。
书上的详细思路:
时间复杂度:
对n个数据进行排序时,平均时间复杂度为O(nlogn),最坏情况下是O(n ^ 2),最好的情况是O(n)
空间复杂度:
快速排序是一种原地排序,只需要一个很小的栈作为辅助空间,空间复杂度为O(log2n),所以适合在数据集比较大的时候使用。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)