排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。 
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

内部排序的分类：

• 一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，快速排序，插入排序，希尔排序，归并排序，堆排序等。

• 另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

冒泡排序

通过上面的动图也可以看出来，冒泡通过两重循环遍历每一个数后将最大的’冒’出去 
冒泡是相邻元素之间的比较，每次把最大的’冒’出去

由于需要经过两重循环，所以时间复杂度为：O(n2)

选择排序

选择排序相比冒泡排序不稳定，时间复杂度也是。 
选择排序没趟都会产生最小值，它不是相邻元素的比较而是在该元素设置一个索引i。 
然后与数组的其他元素依次比较（除了上一个索引值），直到找到小于该元素（索引j）时交换两元素， 
接着继续从i索引（此时已经不是原来的数值）值与索引j+1值比较。重复上述比较过程：

冒泡是相邻元素比较，选择不是相邻元素比较

选择排序是把最小的选出来

快速排序

(1) 从数列中挑出一个基准值。 
(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于最终它应该在的地方。 
(3) 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序。

快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。

假设有如下数组，将两个哨兵设在左右端，最左端的值为基准 
1.右边向左运动，直到找到一个比基准小的数 
2.左边向右运动，直到找到一个比基准大的数 

3.交换两个数 

4.如果两个哨兵不相遇，则继续上述步骤 

5.相遇之后和基准交换 

这样‘6’就永远在它最终应该待的地方了，对6的前一半和后一半进行上述完整操作即可（递归）

插入排序

(1) 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1 
(2) 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。 
(3) i++并重复第二步直到i==n-1。排序完成。

直接插入排序的时间复杂度是O(n2)

希尔排序

是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。分组的插入排序

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

如排序数据为[ 5 9 7 2 3 1 6 ]，那么数据长度为7

第一次分割gap=7/2=3 
i和j之间总是间隔gap个单位，其中j从gap遍历到数据中的最后一个数，j=i-gap 

如上图，最后一次交换时j−gap>=0，但在这里没有什么影响，下面将看出使用j−gap的作用

第二次分割gap=3/2=1 

当分割的间隔是1的时候，首先交换前两个的值，当j和i分别移到3和1的时候，首先交换，因为3>1，然后应该往前迭代，即j−=gap，否则的话我们只比较了3和1，而实际上最前面的2也是大于1的，也应该交换。

如此往复，我们就会得到最终的排序结果。

是分治法的一种，上图可以清晰的描述排序过程

先拆分（递归），后合并

效率为 O(n log n)