参考：
程序员必知8大排序3大查找（一）
程序员必知8大排序3大查找（二）
程序员必知8大排序3大查找（三）
图解排序算法(一)之3种简单排序(选择，冒泡，直接插入)
图解排序算法(二)之希尔排序
图解排序算法(三)之堆排序
图解排序算法(四)之归并排序
常见排序算法C++总结
稳定排序和不稳定排序的区别和代表
目录：
1 排序
1.1 插入排序：直接插入排序、shell希尔排序
1.2 选择排序：简单选择排序、堆排序
1.3 交换排序：冒泡排序、快速排序
1.4 归并排序
1.5 基数排序
1.6 外部排序
2 查找
1 排序
1.1 插入排序
- 直接插入排序
- 基本思想：
每一步，将待排序元素从后往前插入到前面已排好的有序序列中，直到所有元素都已插入。 -
图解：
- 代码实现：
- 复杂度：
最好情况：已正序排好，2 ~ n位与前一项相比一次，n-1，O(n)。
最差情况：倒序，2 ~ n位与前面比较1 ~ n-1次，(n-1)(1+n-1)/2，O(n^2)。
平均情况：趋向于差的情况，O(n^2)。 - 稳定性：稳定
遇到一样的数不交换。
- Shell希尔排序
- 基本思想：
选择初始增量=length/2，每步增量=上一步的增量/2。直到增量=1的组排序完。
每一步，将组内元素做直接插入排序。 -
图解：
- 代码实现：
- 复杂度：
- 稳定性：不稳定
例：2 2 1 4，第一步中，第一个2与1交换，到了第二个2后面。
1.2 选择排序
- 简单选择排序
- 基本思想：
每一步，从待排元素中选择最大（/最小）的元素与首元素交换，直到所有元素都被选择。 -
图解：
- 代码实现：
- 复杂度：
所有情况：每一个数被选出来时，都与其他剩下的数比较过。也就是第1 ~ n-1个被选出的数，比较过n-1 ~ 1次，(n-1)(n-1+1)/2，O(n^2)。 - 稳定性：不稳定
例：5 8 5 2 9，第一趟中，第一个5会与2交换，到了第二个5后面。
- 堆排序
1.3 交换排序
- 冒泡排序
- 基本思想：
每一趟，从一端起通过两两交换把最大元素冒泡到另一端，直到 -
图解：
- 代码实现：
- 复杂度：
最好情况：已正序排好，一趟下来如果一次交换都没做，说明已经排好，n-1，O(n)。
最差情况：倒序，对于第1 ~ n-1大的数，比较n-1 ~ 1次，(n-1)(n-1+1)/2，O(n^2)。
平均情况：趋向于差的情况，O(n^2)。 - 稳定性：稳定
遇到一样的数不交换。
- 快速排序
- 基本思想：
每一趟，以这一组的第一个数为基准，与其他数（看图）比较并交换。
一趟后的结果：大小完全被基准数划分开。 -
图解：
- 复杂度：快排及时间复杂度简单证明
最好情况：乱，每次的基准数都是这一组的中间数，这样每次都分成两半，O(nlogn)。
最差情况：已排好序，每次的基准数都是这一组最边缘的数，这样每次都不能分成两半，O(n^2)。
平均情况：趋向于好的情况，O(nlogn)。 - 稳定性：不稳定
例：5 3 3 4 3 8 9 10 11，5与后面的3交换。
1.4 归并排序
- 基本思想：
分而治之，递归/迭代。 -
图解：
- 代码实现：
- 复杂度：
- 稳定性：
1.5 基数排序
- 基本思想：
将所有待比较正整数统一为同一数位长度，从最低位开始依次排序。 -
图解：
- 代码实现：
- 复杂度：
- 稳定性：稳定
遇到一样的数不交换。
1.6 外部排序
2 查找
[Data Structure & Algorithm] 七大查找算法
