以上总结
如果不考虑稳定性,快排似乎是接近完美的一种方法,但可惜它是不稳定的。 那什么是稳定性呢?
通俗的讲有两个相同的数A和B,在排序之前A在B的前面,而经过排序之后,B跑到了A的前面,对于这种情况的发生,我们管他叫做排序的不稳定性,而快速排序在对存在相同数进行排序时就有可能发生这种情况。
比如对(5,3A,6,3B ) 进行排序,排序之前相同的数3A与3B,A在B的前面,经过排序之后会变成 (3B,3A,5,6) 所以说快速排序是一个不稳定的排序
稳定性有什么意义? 个人理解对于前端来说,比如我们熟知框架中的虚拟DOM的比较,我们对一个<ul>
列表进行渲染,当数据改变后需要比较变化时,不稳定排序或操作将会使本身不需要变化的东西变化,导致重新渲染,带来性能的损耗。
辅助记忆
时间复杂度记忆
冒泡、选择、直接 排序需要两个for循环,每次只关注一个元素,平均时间复杂度为O(n²)(一遍找元素O(n),一遍找位置O(n))
快速、归并、希尔、堆基于二分思想,log以2为底,平均时间复杂度为O(nlogn)(一遍找元素O(n),一遍找位置O(logn))
稳定性记忆-“快希选堆”(快牺牲稳定性)
最后更新于