Web前端之路让前端飞程序员

排序算法总结

2017-09-03  本文已影响100人  公子七

笔试时总是会有各种排序的题层出不穷。
虽然是FE,但是面试时面试官也会经常让你手撕个剑指offer或者是顺便问问常见排序算法的时间复杂度 or 稳定性。
最近有点小心累很久没有写过总结。
但事实证明写总结是让心静下来的一种方式~

关于各种算法的原理还有伪代码就不赘述了~有看到大神总结的表格直接copy过来用了。



看似简简单单的表格,蕴含的信息量却相当的大~
一个刷题功利性患者就从刷题的角度来对表格总结写吧~

题型1、对时间复杂度的考察

① 给定场景,选择最优的排序算法

考察的是各算法的最好/最坏使用场景。

插入排序
最好情况,正序有序,只需要比较n次,且不需要移动。时间复杂度为O(n)。
最坏情况,逆序有序,n个元素,每个元素都需要比较n-1次,时间复杂度为O(n^2)。

冒泡排序
最好情况,正序有序,时间复杂度为O(n);
最坏情况,逆序有序,时间复杂度为O(n^2)。

快速排序
最好情况:均匀分布,每次都将序列分为两个部分(一般二分复杂度都与logn有关),时间复杂度为O(nlogn);
最坏情况:序列基本有序,时间复杂度为O(n^2)。

希尔排序,和步长有关

选择排序
最好情况:正序有序,交换0次,但是每次都要找到最小元素,因而只是减少了交换次数,时间复杂度为O(n^2)

②给定场景,直接考察时间复杂度
③与初始状态相关,比较次数,时间复杂度

比较次数和时间复杂度还是有区别的,堆排序的时间复杂度不会因为待排序序列的有序程度而改变,但是待排序序列的有序程度会影响比较次数,选择排序每选一个输出来数出来都要和剩余的所有数比较,这样待排序序列的有序程度不会影响比较次数。
元素的移动次数与关键字的初始排列次序无关的是:基数排序
元素的比较次数与初始序列无关的是:选择排序
元素的时间复杂度与初始序列无关的是:选择排序、归并排序、堆排序

题型2、考察对排序算法的理解

①给定一个数组,写出在某种排序算法遍历1次/n次的排列。
②给定原序列和经过N次排序后的序列,判断最有可能是用什么算法进行排序。

这一点其实更多考察的是各排序算法进行一次排序后元素的位置。
其中,冒泡、选择、快排、堆都是可以确定一个元素的位置的。
快排确定的是标杆元素的位置,而插入排序确定的是元素的相对位置。

题型3、对空间复杂度的考察

归并排序空间复杂度为O(n),快排为O(logn),其余都是O(1)。

题型4、对稳定性的考察

稳定排序:冒泡排序、插入排序、归并排序、(计数排序、桶排序、基数排序);
不稳定排序:选择排序。、希尔排序、快速排序、堆排序。

其余题型等待后面刷题再更新~~

参考:十大经典排序算法总结(JavaScript版)
常见排序算法小结

上一篇 下一篇

猜你喜欢

热点阅读