一. 冒泡排序
1. 思想：利用比较相邻的两个元素，发现两个数前者大于后者则进行交换，这样每一轮可以把最大数放到后面，只要做n轮便可以使得序列有序。
2. 举例，例如序列 8 7 3 4 5 0 1
第一轮：8 7 3 4 5 0 1
8 7 3 4 5 0 1 -> 7 8 3 4 5 0 1
7 8 3 4 5 0 1 -> 7 3 8 4 5 0 1
7 3 8 4 5 0 1 -> 7 3 4 8 5 0 1
7 3 4 8 5 0 1 -> 7 3 4 5 8 0 1
7 3 4 5 8 0 1 -> 7 3 4 5 0 8 1
7 3 4 5 0 8 1 -> 7 3 4 5 0 1 8 // 得到最大值8在最后一个位置
第二轮：7 3 4 5 0 1
...........
3. 从上面的例子我们可以知道，冒泡排序的时间复杂度为O(n^2)，不需要额外的空间辅助，是一个稳定的算法
4. 示例代码
二. 插入排序
1. 思想：每次选择未排序序列的第一个数插入已经排好序的序列中，使得这个序列依然有序
2. 举例：例如序列 8 7 3 4 5 0 1
第一次：未排序序列为8 7 3 4 5 0 1，第一个数是8，没有排好的序列，因此排好序列为8
第二次：未排序序列为7 3 4 5 0 1，第一个数7，排好序序列为8，则插入到8前面，序列为7 8
第三次：未排序序列为3 4 5 0 1，第一个数为3，排好序序列为3，则插入到7前面，序列为3 7 8
........
3. 只要把所有的未排序的数全部插入到已经排好序的序列中，这样整个序列就是有序的。时间复杂度为O(n^2)，是一个稳定的排序算法
三. 选择排序
1. 思想：每次从未排序的序列中选择一个最小的数未排序序列第一个数交换，相当于每次选择一个最小的数放到排好序的序列最后一个位子，当未排序序列为空的时候整个序列即为有序
2. 举例：例如序列8 7 3 4 5 0 1
第一次：序列 8 7 3 4 5 0 1，未排序序列最小的数0，和8交换，此时排好序序列为0
第二次：序列 0 7 3 4 5 8 1，未排序序列最小的数1，和7交换，此时排好序序列为0 1
第三次：序列 0 1 3 4 5 8 7，未排序序列最小的数3，本身不用交换，此时排好序序列为0 1 3
...............
3. 当未排序序列为空的时候说明整个序列为有序，时间复杂度为O(n^2)，是一个不稳定的排序算法
四. 快速排序
1. 思想：利用一个基准arrNum[k]每次把区间[l,r]划分成两个部分[l,k-1],[k+1,r]使得[l,k-1]这个子区间的所有值全部小于等于arrNum[k]，[k+1,r]这个区间的值全部大于等于arrNum[k]的值，然后递归对这两个子区间进行排序。
2. 举例：例如序列8 7 3 4 5 0 1，每次选择区间中间那个数作为基准
第一次：区间为[0, 6]，选择基准为arrNum[3] = 4
（1）先把基准4和最后一个数交换，得到8 7 3 1 5 0 4
（2）设置两个指针p1和p2，p1用来枚举所有数，p2用来保存左子区间全部小于基准的下标，初始化p1和p2都是指向区间左端点
（3）手动推算结果如下
3. 快速排序时间复杂度为O(NlogN)，是一个不稳定的算法，有可能会退化为O(n^2)，不需要额外的空间
五. 归并排序
1. 思想：利用分治的思想，每次把要排序的区间平均划分成两部分，然后递归排序，再合并这两个区间
2. 举例：例如序列8 7 3 1 5 0 4
3. 归并排序的时间复杂度为O(NlogN)，是一个稳定的排序算法，但是需用一个和原来一样大的内存空间
六. 堆排序
1. 堆排序利用堆的性质，最小堆满足根结点的值比左右子树都小，最大堆满足根结点的值比左右子树都大
2. 一个无序系列建立最小堆方法是，从第一个叶子到根结点，每个结点往下调整，调整完所有结点之后即为最小堆
为什么叶子结点不用调整？因为叶子结点已经满足最小堆的性质
3. 一个无序序列调整为最小堆的过程，序列为8 7 3 4 5 0 1
4. 建立最小堆的时间复杂度为O(n)，很多人认为是O(NlogN)，为什么不是呢？证明如下
假设堆中有N个元素，则树高为H = logN，对于树高为h的结点建堆时间复杂度为O(H-h)。因此从最底层到根结点所有结点的建堆时间复杂度和为
S = 0*2^(H-1)+1*2^(H-2)+2*2^(H-3)+........+(H-1)*2^0
<= 2^(H)+2^(H-1)+2^(H-2)+.......+2^0
<= 2^(H+1)
因为H = logN，则2^(H+1) = 2^H*2 = 2N，则时间复杂度为O(N)。
5. 建立最小堆代码
6. 堆排序只需要每次把最小堆的根结点值取出并删除根结点，然后把最后一个叶子结点补到根结点并删除指，然后从根结点往下调整即可，时间复杂为O(NlogN)，是一个不稳定的排序算法，不需要额外空间
总结：
稳定排序算法：冒泡排序、插入排序、归并排序、基数排序
不稳定排序算法：选择排序、快速排序、堆排序、希尔排序