现在的位置: 首页 > 综合 > 正文

快速排序

2018年05月28日 ⁄ 综合 ⁄ 共 370字 ⁄ 字号 评论关闭

以前对排序很模糊,最近看了下书,感觉不懂得东西突然都很明朗了, 我认为啊,不是你不懂,该懂的时候老天自然让你懂。

其实快速排序很简单,做了一个总结, 其实思想就是分治法。

如何分? 

首先想到拿一个数来分, 所有的数都和这个数进行比较,小的放在左边,大的放在右边。

然后再对左边进行分割,右边继续分割

循环,一直到1

很简单那

时间复杂度

时间复杂度要看你拿到的这个数能把这个数列分为两半是怎么样的,比如每次拿到的值刚好把数列分为1/2 1/2 那复杂度很好算啊, nlgn

如果是1/100,99/100 也是nlgn

如果这个数把数列分为1 n-1 那这个就复杂了, n*n ,因为你这个1对排序几乎无影响啊。应该说就没分成功。

T(n)=T(n-1)+O(1)

所以啊,有个聪明人为了避免这种情况,就采用了,随机取数的方法,这样的话就是nlogn

代码就不写了,已经很明确了。迭代呗

抱歉!评论已关闭.