排序与查找

参考：
程序员必知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 插入排序

1. 直接插入排序

• 基本思想：
  每一步，将待排序元素从后往前插入到前面已排好的有序序列中，直到所有元素都已插入。
• 图解：
• 代码实现：

• 复杂度：
  最好情况：已正序排好，2 ~ n位与前一项相比一次，n-1，O(n)。
  最差情况：倒序，2 ~ n位与前面比较1 ~ n-1次，(n-1)(1+n-1)/2，O(n^2)。
  平均情况：趋向于差的情况，O(n^2)。
• 稳定性：稳定
  遇到一样的数不交换。

2. Shell希尔排序

• 基本思想：
  选择初始增量=length/2，每步增量=上一步的增量/2。直到增量=1的组排序完。
  每一步，将组内元素做直接插入排序。
• 图解：
• 代码实现：

• 复杂度：
• 稳定性：不稳定
  例：2 2 1 4，第一步中，第一个2与1交换，到了第二个2后面。

1.2 选择排序

1. 简单选择排序

• 基本思想：
  每一步，从待排元素中选择最大（/最小）的元素与首元素交换，直到所有元素都被选择。
• 图解：
• 代码实现：

• 复杂度：
  所有情况：每一个数被选出来时，都与其他剩下的数比较过。也就是第1 ~ n-1个被选出的数，比较过n-1 ~ 1次，(n-1)(n-1+1)/2，O(n^2)。
• 稳定性：不稳定
  例：5 8 5 2 9，第一趟中，第一个5会与2交换，到了第二个5后面。

2. 堆排序

1.3 交换排序

1. 冒泡排序

• 基本思想：
  每一趟，从一端起通过两两交换把最大元素冒泡到另一端，直到
• 图解：
• 代码实现：

• 复杂度：
  最好情况：已正序排好，一趟下来如果一次交换都没做，说明已经排好，n-1，O(n)。
  最差情况：倒序，对于第1 ~ n-1大的数，比较n-1 ~ 1次，(n-1)(n-1+1)/2，O(n^2)。
  平均情况：趋向于差的情况，O(n^2)。
• 稳定性：稳定
  遇到一样的数不交换。

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] 七大查找算法