笔试时总是会有各种排序的题层出不穷。
虽然是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、对稳定性的考察
稳定排序：冒泡排序、插入排序、归并排序、（计数排序、桶排序、基数排序）；
不稳定排序：选择排序。、希尔排序、快速排序、堆排序。
其余题型等待后面刷题再更新~~
网友评论