快速排序,又称划分交换排序。以分治法为策略实现的快速排序算法。
本文主要要谈的是利用javascript实现in-place思想的快速排序
分治法:
在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。(摘自维基百科)
快速排序的思想
数组中指定一个元素作为标尺,比它大的放到该元素后面,比它小的放到该元素前面,如此重复直至全部正序排列。
快速排序分三步:
选基准:在数据结构中选择一个元素作为基准(pivot)
划分区:参照基准元素值的大小,划分无序区,所有小于基准元素的数据放入一个区间,所有大于基准元素的数据放入另一区间,分区操作结束后,基准元素所处的位置就是最终排序后它应该所处的位置
递归:对初次划分出来的两个无序区间,递归调用第 1步和第 2步的算法,直到所有无序区间都只剩下一个元素为止。
现在先说说普遍的实现方法(没有用到原地算法)
通过断点调试,可得出结果。
弊端:
它需要Ω(n)的额外存储空间,跟归并排序一样不好。在生产环境中,需要额外的内存空间,影响性能。
同时,很多人认为上边的就是真正的快速排序了。 所以,在下面,很有必要的推荐in-place算法的快速排序
有关于原地算法可参考维基百科,被墙的同学,百度也差不多。
in-place
快速排序一般是用递归实现,最关键是partition分割函数,它将数组划分为两部分,一部分小于pivot,另一部分大于pivot。具体原理上边提过
分区的优化
这里细心的同学可能会提出,选取不同的基准时,是否会有不同性能表现,答案是肯定的,但,因为,我是搞前端的,对算法不是很了解,所以,这个坑留给厉害的人来填补。
复杂度
快速排序是排序速度最快的算法,它的时间复杂度是O(log n)
在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较.
以上所述是小编给大家介绍的JavaScript实现in-place思想的快速排序方法,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的,在此也非常感谢大家对编程之家网站的支持!