本笔记基于ROBERT SEDGEWICK & KEVIN WAYNE开设的《Algorithms》课程，同时配有同名教材。
slides本身内容丰富详实，所以我会先甄选出重点的篇幅整理出来并做简单批注，后续会添上对应算法题的演示。
0.排序的基础：
通过对两个元素进行大小比较（小于、等于或者大于），返回不同的结果。
比较后进行两步处理：①第一个元素是否比第二个元素小（是的话返回-1）②（满足条件下）两者进行交换
1.选择排序
实现过程：①从左（第1个元素开始）到右遍历整个数组，找出当前整个数组最小的元素并放到最左边；②继续遍历整个数组（从第2个元素开始，第1个元素的位置在①中已被最小元素固定，所以不用管）找到（整组中）第2小的元素（即剩下数组元素中最小的），放在左起第2个位置；③重复直至整个数组排序完成
算法复杂度：由于每次都要遍历当前剩下的整个数组，所以需要比较
(N – 1) + (N – 2) + … + 1 + 0 ~ N ² / 2 次，交换N次
2.插入排序
每次都要从（当前的）头开始遍历，很麻烦，改进一下。
实现过程：从右边开始入手，只要当前的元素比左边的元素小，就跟左边交换，循环往复。
算法复杂度：对于一个随机的数组，平均来看，有一半的元素是已经按从小到大排序好的（不一定连在一起，可以混在没有排序好的元素中间），所以跟之前的选择排序相比，少做一半的比较，（对于选择排序来说，元素怎么排都不影响，它总是机械死板地从头开始遍历整个数组）那么算法复杂度也是选择排序的一半了，即N ² / 4次 。
插入排序在已经部分排序好的数组里的表现：
3.Shellsort （Shell是发明这个算法的人的名字）
插入排序比选择排序有进步，但它也有犯傻的时候，比如在右边的某个元素命名比前面7个元素都要小，但我们却要眼睁睁地看着这个元素连续与左边交换7次。聪明的你们想到了，直接一步到位，交换7个位置嘛！然后再每隔3个元素进行比较交换，再回到最基本的对每个元素进行比较交换，这就是Shellsort。
当然，那到底从每隔几个元素进行操作开始呢？这个间隔规律也是个数学问题，目前并没有一个严密的数学模型可以求得最优解，在这里介绍一个比较简单易用的：3x+1
每篇文章除特殊声明外均以 CC BY-NC-SA 4.0 协议发布，非商业用途可以在保留署名和来源的情况下任意转载。