黑马程序员技术交流社区
标题:
快速排序怎么个快法
[打印本页]
作者:
lzw123451
时间:
2013-2-27 23:07
标题:
快速排序怎么个快法
本帖最后由 李志卫 于 2013-2-28 16:22 编辑
如题, 快速排序怎么会比其他排序快~
作者:
赵海洋
时间:
2013-2-28 09:15
这个解释起来有点麻烦,我只能简单说下了,希望对你有帮助。因为详细说的话需要用到二叉树,平均时间复杂度的算法,以及其他排序算法的时间复杂度等等。尤其是算法里还涉及分治法,指针,栈等。
以下log的意思都是log以2为底。
在一般情况下,排序n个项目要O(nlog n)次比较,这就是快排的平均时间复杂度。最坏情况下的时间复杂度是O(n*n),即n方,但这种情况并不常见,快排的一个特点是越是有序的一组数,排序越慢,这是因为快排是从两头往中间排序。事实上,快排通常明显的比其他的算法快,因为它的内部循环可以在大不多的架构上很有效的被实现出来。
假设有一组数,3,2,6,8,1,7.有两个指针i,j,一个i指向3,一个j指向7。有一个辅助变量temp。
首先,把3拿出去放入temp,然后从7那端开始寻找第一个比3小的数,即1.找到后放到3那个里面。然后从i这端开始寻找第一个比3大的数放到原来1那个里面去。最后i,j指针重合时一遍排序完成,然后进行第二遍排序,具体的就不展开说了。
最终的排序平均时间复杂度是O(nlog n),在乱数的情况下,它比其他的排序算法更加快。究其原因,最好记住,否则,研究基本排序方法去吧。。。(有兴趣的话给你简单举例:交换类排序:冒泡,快速。插入类排序:直接插入排序,折半插入排序。选择类排序:简单选择排序,堆排序。归并类排序,基数排序等等。)
如果你还想知道O(nlog n)是怎么来的,天啊,你还得研究二叉树去。。。我就说这么多了,希望有帮助。
作者:
lzw123451
时间:
2013-2-28 15:21
赵海洋 发表于 2013-2-28 09:15
这个解释起来有点麻烦,我只能简单说下了,希望对你有帮助。因为详细说的话需要用到二叉树,平均时间复杂度 ...
恩恩 辛苦了。
作者:
贾文泽
时间:
2013-2-28 16:49
本帖最后由 贾文泽 于 2013-2-28 16:58 编辑
其实快速排序是一种递归实现
比如说我这一组数吧 5 2 4 3 6 5 7
1.任意选一个数作为参考元素 比如我就选 5 ,下面的参考元素我用红色标记
5
2 4 3 6 5 7
2.
把比参考元素小的放左边,比参考元素大的放右边
2 4 3
5
6 5 7
3.把参考元素两边的数分别拿出来在进行这种操作
2
4 3
6
5 7
2
4 3 5
6
7
4.同第3步操作
4
3
5 7
3
4 5 7
当参考元素两边数字的个数是0或者1的时候,那就把结果整合
2 3 4 5 5 6 7
把这中操作用递归实现,那就是最快的排序算法
用代码实现的话也简单,初始化两个数组,把比较后参考元素两边的序列分别装进两个数据里,用递归调用这种操作就O了
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2