前言：前段时间面试官问我懂哪些排序算法，我随口就说冒泡选择，他问为什么，我说因为很简单，瞬间我和他都沉默了。再后来问的什么二叉树什么数据结构之类的，我让他直接跳过了，我说出学校这么久了，工作中没用到的，基本都忘了。结果可想而知。所以最近我都在重拾算法数据结构一类知识。

前两周空闲时间都会研究排序算法，基本上每天都会手写一遍，忘了再写写了再忘，工作中遇到的排序问题，我都会刻意的使用一些我不常用的算法，以此来加深记忆。今天写的六种算法，是这几天我学到的，为以后忘了再来看一遍。

1.冒泡：

冒泡的中心思想是两两对比，如果前面一个大于后面一个则交换位置，不断重复这个过程arr.length-1遍后，排序完成。其中要注意的点是：n个元素，其实只需要对比n-1遍即可；内层循环每次都会减少对比i位，因为后面的元素是已经排序好的，不必再次对比。下面是代码：

2.选择：

选择的中心思想是，每次循环时选择一位元素假设是最小元素，然后在向后遍历的过程中，如果选择的最小元素比后面的元素大，则最小元素改变。其中要注意的点是：内层循环的下标应该是比外层循环的下标大一个的，总不会自己和自己比吧？内层循环结束后，添加判断min是否变化了，如果变化了则交换，否则不交换。下面是代码：

3.插入：

插入的中心思想是，假设抽出一位元素，向前对比，直到抽出的元素大于循环到的元素为止。要注意的点是：在实际写作时，我们假设第一位是已排好的的序列，抽出第二位，向前遍历比较；其实最内层实现也有两种方法，一种是后移的办法，一种是交换办法，本例中是交换的方式。下面是代码：

4.希尔：

希尔其实是插入排序的优化版，其中心思想是将数组按照一定的增量，分成若干的子序列，子序列内部排序完成后，增量减少，再次循环。所以可以说插入排序是增量为1的希尔排序。其中我们初始增量设置为arr.length/2，每次循环减少一半。下面是代码：

5.归并：

归并排序的中心思想是，将数组分从中分开（这是一个递归的过程，直到数组不能再分了），子序列内部排序号，再合并起来。不断重复这个过程，最终数组变得有序。需要注意的是，如果数组太大了，建议还是别使用递归的方式了，因为会StackOverFlow，道理都懂的。代码如下：

6.快排：

快排就是给基准数找位置的一个过程。假设左边第一个是基准数，先移动右哨兵的位置，找到一个比基准数小的数停下来，赋值给当前左哨兵；然后再动右哨兵，直到找到一个比基准数大的数停下来，赋值给当前左哨兵。直到两个哨兵相遇，然后将基准数归位。下面是代码：