以前对排序很模糊,最近看了下书,感觉不懂得东西突然都很明朗了, 我认为啊,不是你不懂,该懂的时候老天自然让你懂。
其实快速排序很简单,做了一个总结, 其实思想就是分治法。
如何分?
首先想到拿一个数来分, 所有的数都和这个数进行比较,小的放在左边,大的放在右边。
然后再对左边进行分割,右边继续分割
循环,一直到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
代码就不写了,已经很明确了。迭代呗