排序知识点（时间复杂度记忆技巧）

Kitty喜欢小鱼干

1、复杂度总结
（1）、时间复杂度
    平均情况下，快速排序、希尔排序（复杂度了解即可）、归并排序和堆排序的时间复杂度均为O(nlogn)，其他都是O(n^2)。一个特殊的是基数排序，其时间复杂度为O(d(n+rd))。
    最坏情况下，快速排序的时间复杂度为O(n^2)，其他都和平均情况下相同。
    《故事助记》：如军训时，教官说：“快些以 nlogn 的速度归队。”其中，“快”指快速排序，“些”指希尔排序（发音近似），“归”指归并排序，“队”指堆排序（谐音），这4种排序的平均时间复杂度都是O(nlogn)。
（2）、空间复杂度
    记住几个特殊的就好，快速排序为O(logn)，归并排序为O(n)，基数排序为O(rd)，其他都是O(1)。
（3）、其他
    直接插容易插变成O(n)，起泡起得好变成O(logn)，所谓“容易插”或“起得好”都是指初始序列已经有序。


2、算法稳定性总结
    一句话记忆：“考研复习痛苦啊，情绪不稳定，快些选一堆好友来聊天吧”。
    这里，“快”指快速排序，“些”指希尔排序，“选”指简单选择排序，“堆”指堆排序，这4种是不稳定的，其他自然都是稳定的。

3、其他细节（与排序原理有关）

（1）、经过一趟排序，能够保证一个关键字到达最终位置，这样的排序是交换类的那两种（起泡、快速）和选择类的那两种（简单选择、堆）。
（2）、排序算法的关键字比较次数和原始序列无关——简单选择排序和折半插入排序。
（3）、排序算法的排序趟数和原始序列有关——交换类排序（起泡、快速）。

4、在次比较一下直接插入排序和折半插入排序
    二者最大的区别在于查找插入位置的方式不同。直接插入按顺序查找的方式，而折半插入按折半查找的方式。


5、一个有用的结论
    借助“比较”进行排序的算法，在最坏情况下的时间的复杂度至少为O(nlogn)。

露转溪桥

楼主这些都是从考研书籍《数据结构高分笔记》复制的吧，这确实是本很不错的书，考研的时候我就用它，在此推荐一波~

Kitty喜欢小鱼干

露转溪桥 发表于 2018-8-27 08:59
楼主这些都是从考研书籍《数据结构高分笔记》复制的吧，这确实是本很不错的书，考研的时候我就用它，在此推 ...

对的，很好用，我想把这些记下来，万一以后书丢了呢。对了，关于这个学科能分享一下你的经验吗？

露转溪桥

Kitty喜欢小鱼干 发表于 2018-8-28 12:15
对的，很好用，我想把这些记下来，万一以后书丢了呢。对了，关于这个学科能分享一下你 ...

自己有空要多动手写写代码，即使是书上一些很简单的代码，一看就会，但是自己动手也可能会遇到很多细节问题。对于书上复杂的代码，自己至少要做到看懂后能独立地写出来，不要停留在看懂思路后就嫌简单不写的状态。
不过可以说，这本书既是针对入门者制定的，但更多是针对考研制定的，所以里面很多涉及计算和画图的知识点并没有给出相应的代码，自己如果有兴趣深入学的话可以上网看看。
个人很推荐你看完这本书之后再回头看看严蔚敏版的数据结构，这本书写的很严谨，也相对不那么容易看懂。

Kitty喜欢小鱼干

露转溪桥 发表于 2018-8-28 17:17
自己有空要多动手写写代码，即使是书上一些很简单的代码，一看就会，但是自己动手也可能会遇到很多细节问 ...

好的，谢谢你！