常见排序

1. 选择排序（了解）

思路：每一轮选取未排定的部分中最小的那个元素交换到未排定部分的最开头，经过若干个步骤，就能排定整个数组。即：先选出最小的，再选出第二小的，以此类推。
算法思想 1：贪心算法
每一次决策只看当前，当前最优，则全局最优。注意：这种思想不是任何时候都适用。
算法思想 2：减治思想
外层循环每一次都能排定一个元素，问题的规模逐渐减少，直到全部解决，即「大而化小，小而化了」。运用「减治思想」很典型的算法就是大名鼎鼎的「二分查找」。
选择排序的优点：交换次数最少
「选择排序」看起来好像最没有用，但是如果在交换成本较高的排序任务中，就可以使用「选择排序」（《算法 4》相关章节课后练习题）。
依然是建议大家不要对算法带有个人色彩，在面试回答问题的时候和看待一个人和事物的时候，可以参考的回答模式是「具体问题具体分析，在什么什么情况下，用什么什么算法」。
复杂度分析：

• 时间复杂度：，这里 是数组的长度；

• 空间复杂度：，使用到常数个临时变量。

  练习：

  912. 排序数组

  2. 冒泡排序（熟悉）

  思路：
  1、相邻的两个元素进行比较，把比较大的元素排在后面，这样一轮循环下来，就可以找到这一轮循环中最大的那个元素，我们把这个过程形象地称之为「冒泡」；
  2、由于每一轮循环都「冒泡」出一个这一轮循环最大的元素，所以上一轮循环的最后一个元素，不应该参加下一轮循环的比较了，这就是为什么内层循环的结束条件是 j < arr.length -i -1 的原因了。
  优化思路：
  如果在一次循环中，都没有「冒泡」行为发生，则整个排序任务都可以终止了。

  3. 插入排序（熟悉）

  思路：每次将一个数字插入一个有序的数组里，成为一个长度更长的有序数组。有限次操作以后，数组整体有序。
  结论：「插入排序」是稳定排序，在接近有序的情况下，表现优异。
  特点：

• 「插入排序」可以提前终止内层循环（体现在 nums[j - 1] > temp 不满足时）；

• 在数组「几乎有序」的前提下，「插入排序」的时间复杂度可以达到 ，因此「插入排序」可以作为高级排序算法的一个子过程（后面再「归并排序」和「快速排序」算法里我们会看到）。

写法一：基于交换
写法二（优化）：基于赋值
复杂度分析：

• 时间复杂度：，这里 是数组的长度；

• 空间复杂度：，使用到常数个临时变量。

  练习：

  147. 对链表进行插入排序

  4. 希尔排序（了解）

  首先回顾一下「插入排序」在什么情况下效率高呢？

• 在待排序数组「基本有序」的时候；

• 在待排序数组的元素个数较少的时候。

基本思想：
开始的时候逐渐让数组变得基本有序，最后使用一次使用「插入排序」就变得高效了。

• 「逐渐让数组变得基本有序」的方法是让移动的「步幅」增大，不是一步一步挪过去，而是「大步流星」、「连蹦带跳」走过去；
• 「逐渐缩小增量」「分组实施插入排序让数组变得逐渐接近有序」「最后执行一次标准的插入排序」（ 最后一轮就是「原汁原味」的插入排序。

「希尔排序」的实现比较多，我们这里只选取希尔排序的一种比较容易理解的实现。「希尔排序」也可以理解为「分组插入排序」。

5. 归并排序（重点）

基本思路：借助额外空间，合并两个有序数组，得到更长的有序数组。
算法思想：分而治之（分治思想）。「分而治之」思想的形象理解是「曹冲称象」、MapReduce，在一定情况下可以并行化。

「归并排序」是理解「递归思想」的非常好的学习材料，大家可以通过理解：递归完成以后，合并两个有序数组的这一步骤，想清楚程序的执行流程。即「递归函数执行完成以后，我们还可以做点事情」。因此，「归并排序」我个人觉得非常重要，一定要掌握。

5.1 基本实现

这是我们首次接触递归算法的实现。下面我将一步一步展示如何编写递归函数实现归并排序。
第 1 步：先写出最顶层函数
我们对下标在 [0, len - 1] ，左闭且右闭的这个区间里的元素使用递归的「归并排序」算法。
第 2 步：写出递归函数
注意应该先考虑递归终止的条件。
第 3 步：编写 mergeTwoSortedArray 方法

5.2 优化的方向

• 优化 1：小区间排序使用「插入排序」。在「小区间」里转向使用「插入排序」，Java 源码里面也有类似这种操作，「小区间」的长度是个超参数，需要测试决定，我这里参考了 JDK 源码；
• 优化 2： 如果数组有序则无须归并。在「两个数组」本身就是有序的情况下，无需合并；
• 优化 3：全局使用一个临时数组用于归并。全程使用一份临时数组进行「合并两个有序数组」的操作，避免创建临时数组和销毁的消耗，避免计算下标偏移量。
• 注意：实现归并排序的时候，要特别注意，不要把这个算法实现成非稳定排序，区别就在 <= 和 < ，已在代码中注明。

「归并排序」比「快速排序」好的一点是，它借助了额外空间，可以实现「稳定排序」，Java 里对于「对象数组」的排序任务，就是使用归并排序（的升级版 TimSort，在这里就不多做介绍）。
「归并排序」也有「原地归并排序」和「不使用递归」的归并排序，但是我个人觉得不常用，编码、调试都有一定难度。递归、分治处理问题的思想在基础算法领域是非常常见的，建议多练习编写「归并排序」学习递归思想，了解递归的细节，熟悉分治的思想。

5.3 自底向上的归并排序（选学、基本不考）

以上我们使用的是「自顶向下」的归并排序，下面我们介绍「自底向上」的归并排序算法。我们并不须要递归，只须要迭代就可以了。

练习：

88. 合并两个有序数组

剑指 Offer 51. 数组中的逆序对

315. 计算右侧小于当前元素的个数

6. 快速排序

快速排序也是使用「分治思想」实现的一种排序算法。但「归并排序」不同的是：快速排序首先想方设法通过排定一个元素，并且在排定这个元素的同时，对整个数组也做了一次划分。这个过程叫做切分。

• 基本思路：快速排序每一次都排定一个元素（这个元素呆在了它最终应该呆的位置），然后递归地去排它左边的部分和右边的部分，依次进行下去，直到数组有序；
• 算法思想：分而治之（分治思想），与「归并排序」不同，「快速排序」在「分」这件事情上不想「归并排序」无脑地一分为二，而是采用了 partition 的方法（书上，和网上都有介绍，就不展开了），因此就没有「合」的过程。
• 实现细节（注意事项）：（针对特殊测试用例：顺序数组或者逆序数组）一定要随机化选择切分元素（pivot），否则在输入数组是有序数组或者是逆序数组的时候，快速排序会变得非常慢（等同于冒泡排序或者「选择排序」）；

以下是针对特殊测试用例（有很多重复元素的输入数组）有 3 种版本的快排：

• 版本 1：基本快排：把等于切分元素的所有元素分到了数组的同一侧，可能会造成递归树倾斜；
• 版本 2：双指针快排：把等于切分元素的所有元素等概率地分到了数组的两侧，避免了递归树倾斜，递归树相对平衡；
• 版本 3：三指针快排：把等于切分元素的所有元素挤到了数组的中间，在有很多元素和切分元素相等的情况下，递归区间大大减少。

这里有一个经验的总结：之所以快排有这些优化，起因都是来自「递归树」的高度。关于「树」的算法的优化，绝大部分都是在和树的「高度」较劲。类似的通过减少树高度、使得树更平衡的数据结构还有「二叉搜索树」优化成「AVL 树」或者「红黑树」、「并查集」的「按秩合并」与「路径压缩」。

• 写对「快速排序」的技巧：保持「循环不变量」，即定义的变量在循环开始前、循环过程中、循环结束以后，都保持不变的性质，这个性质是人为根据问题特点定义的。
• 「循环不变量」的内容在《算法导论》这本书里有介绍。我个人觉得非常有用。「循环不变量」是证明算法有效性的基础，更是写对代码的保证，遵守循环不变量，是不是该写等于号，先交换还是先 ++ ，就会特别清楚，绝对不会写错，我在编码的时候，会将遵守的「循环不变量」作为注释写在代码中。

快速排序丢失了稳定性，如果需要稳定的快速排序，需要具体定义比较函数，这个过程叫「稳定化」，在这里就不展开了。

练习：

75. 颜色分类

215. 数组中的第K个最大元素

方法一：暴力解法
方法二：partition
方法三：优先队列