算法面试章-排序：彻底拿下插入排序和冒泡排序
算法章：包含排序、链表、堆、栈、二叉树、图的简单应用等常见最新面试算法的题目与题解。
算法章节一律图文并茂，不讲废话，并循序渐进地提供C/C++和Java两种版本的优秀写法，保证简单、好记。
今天教大家手撕插入排序与冒泡排序
按我们的统计，这两道算法题出现频率大概是8%，拿下这两个算法，至少面试官会认为小兄弟你的基础很扎实。
不说废话直接上菜！
插入排序
以从小到大排序为例，插入排序到底干了什么？
一次插入过程
假设一个array长度为6，且前4个element已经有序排布了，如图
现在将第5个element = 7 依次与它之前的有序部分从后向前对比，即与第4个element、第3个element、第2个element、第1个element对比：
如果发现7比有序部分element更小，则有序部分element向后移动一位；
如果发现7比有序部分element更大，则7应该放在这个element之后，才能保证依然有序
经过如上的比较、移动，最终12、10、8分别向后移动一位，7遇到5后停止比较，插入到5之后，array形成如下的模样：
现象归纳：原本前4个element有序的array，经过基于第5个element的一次插入，变成了一个前5个element有序的array
理解了一次插入的原理后，我们就很容易建立插入排序的过程：
最初array前1个element有序（废话），基于第2个element的一次插入，array变为前2个element有序；
array前2个element有序，基于第3个element的一次插入，array变为前3个element有序；
array前3个element有序，基于第4个element的一次插入，array变为前4个element有序；
以次类推；
array前N-1个element有序，基于第N个element的一次插入，array变为前N个element有序；
array前N个element有序，也就是array完全有序了，插入排序完成！
一句话归纳：对第2个element到最后1个element，都做一次基于它的向前插入，这就是插入排序。
好了，配合文字看图帮助理解：
C/C++代码
void insert_sort(int* array, int size) {//从第二个element开始向前比较for (int i = 1;i < size; ++i) {int pivot = array[i];//需要被比较的elementint j = i - 1; //从最近的element开始比较，即i-1// 如果尚未到array的头部、且之前的element相比pivot更大while (j >= 0 && pivot < array[j]) {array[j + 1] = array[j];//将array[j]向后移动一位--j;}// 退出循环后，说明pivot已经遇到了比它小的element=array[j]// 或者已经到了边界j=-1// 将pivot插入到停止位置的后一位array[j + 1] = pivot;}}
刨除注释comment，这段代码不到10行，可以死记！
Java代码
看起来代码很多？只不过是加了点儿test代码而已，淡定。
public class InsertSort {// 插入排序代码private static void insertSort(int[] array) {for (int i = 1;i < array.length; ++i) {int pivot = array[i];//需要被比较的elementint j = i - 1; //从最近的element开始比较，即i-1while (j >= 0 && pivot < array[j]) {array[j + 1] = array[j];//将array[j]向后移动一位--j;}array[j + 1] = pivot;}}// 测试程序public static void main(String[] args) {int[] array = {6, 5, 3, 1, 8, 7, 2, 4};insertSort(array);for (int i = 0;i < array.length; ++i) {System.out.print(array[i] + " ");}System.out.println();}}
怎么样，是不是很简单？
冒泡排序
冒泡排序为什么叫冒泡排序？因为你可以将这种排序类比成重量不同的气泡。
一个特别好记的现实生活场景：
一堆重量不同的气泡被堆积到一起，质量更大的气泡将会把它下面比它质量小的气泡挤压上去，即质量更大的气泡会下沉，最终质量最大的气泡被下沉到底部，而质量最小的气泡被挤压到顶部，气泡形成了按质量从小到大的排序。
一次冒泡
依次比较array中每两个相邻element，如果后面的大，则交换：
最终可以发现，最大的element=8会被冒泡到array最后位
现象归纳：对于array[0, n) 来说，一次冒泡将会使得最大element被交换到最后一位。
理解了一次冒泡的原理，我们很容易构建整个冒泡流程：
对array[0, n)即整个array进行一次冒泡，于是最大element将出现在最后1位；
对array[0, n-1) 进行一次冒泡，于是第2大element将出现在倒数第2位；
对array[0, n-2) 进行一次冒泡，于是第3大element将出现在倒数第3位；
以此类推
最终，最小element将出现在第1位。
配合文字看图帮助理解：
得分中等的代码
按照上述描述写出的代码如下：
void bubble_sort(int* array, int size) {int N = size;// 对前几个element执行冒泡？最开始设置为array的大小for (int N = size;N > 1; --N) {// 一次冒泡for (int i = 1;i < N; ++i) {if (array[i - 1] > array[i]) {// 前比后大，执行交换，模拟冒泡int temp = array[i - 1];array[i - 1] = array[i];array[i] = temp;}}}}
这段代码是逻辑上正确的，满分5分的话你可以得到2.5分。
Excuse me？一顿操作猛如虎，结果得分2.5？别急，听我慢慢说。
这个解法不是最优解：假设array在运行bubble_sort函数前就已经有序了，这段代码的时间复杂度依然是O(n^2)。
更高级的做法是利用冒泡动作：
冒泡排序的冒泡行为可以很轻松判断出目前array是否有序，我们可以利用这一点，在冒泡过程中，发现array已经有序就退出冒泡，防止做无用功。
得分满分的思路
设置一个布尔类型变量sorted，用来记录目前array是否有序；
在相邻比较中，如果有发现相邻元素达到交换条件，说明array目前仍然还是未有序的，标记sorted=false；
而如果未发现相邻元素达到交换条件，说明array已经有序，标记sorted=true，不再进行下一轮比较。
那么对于事先就已经有序的array，冒泡排序仅会执行一次冒泡，即时间复杂度为O(n)。
C/C++代码
void bubble_sort(int* array, int size) {bool sorted = false; //标记：目前array是否已有序int N = size; //对array前N个元素进行相邻比较while (sorted == false) {sorted = true; //比较前，先假定是已有序for (int i = 1;i < N; ++i) {if (array[i - 1] > array[i]) {sorted = false;// 说明还未有序, 标记// 交换，模拟冒泡int temp = array[i];array[i] = array[i - 1];array[i - 1] = temp;}}--N;}}
Java代码
public class BubbleSort {//冒泡排序private static void bubbleSort(int[] array) {boolean sorted = false; //标记：目前array是否已有序int N = array.length;while (sorted == false) {sorted = true;for (int i = 1;i < N; ++i) {if (array[i - 1] > array[i]) {sorted = false;// 说明还未有序, 标记// 交换，模拟冒泡int temp = array[i];array[i] = array[i - 1];array[i - 1] = temp;}}--N;}}// 我是测试代码public static void main(String[] args) {int[] array = {6, 5, 3, 1, 8, 7, 2, 4};bubbleSort(array);for (int i = 0;i < array.length; ++i) {System.out.print(array[i] + " ");}System.out.println();}}
下期预告
《笔试/面试不知道准备什么？我来给你划重点好了》