排序算法（九）总结
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
1 简单选择排序
是最简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素
作为首元素，直到所有元素排完为止，简单选择排序是不稳定排序。
数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次
(O(N2))
2 冒泡排序O(N2)
的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素
“浮”到顶端，最终达到完全有序
3 直接插入排序O(N2)
基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
最大区别：冒泡时在 [未排序的部分] 里面找最大（或小），放到一端。插入是往 [已排序好] 的部分里面插入当前数。
不变条件(invarient)不同：冒泡是，最大的数会先被排序好到一端。插入是，当前点的一侧是已排序的（ sorted ），
这些数并不一定是最大的。
循环终止条件不同：冒泡必须遍历未排序的所有数字才能找到最大，插入找到合适位置就可以停。*/
插入排序越往后面，动静越大(两两比较（第二个会和前（前移动继续向前移动）后比较，），找一个合适的位置，)
因为涉及到的元素越来越多；
冒泡排序越往后面（一轮两两排序找到最大或者最小固定位置，再继续剩下两个元素两两排序），
动静越小，因为涉及到的元素越来越少。
4 希尔排序
简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，
比如[5,4,3,2,1,0]这种倒序序列， 数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次
。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，
随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1
是插入排序法的一种，时间复杂度最快为O(n)，最慢为O(n^2)，每个小区间内都采用插入排序的方式，不需要申请额外辅助空 间O(1)。
5 归并排序
时间复杂度是O(nlogn)级的，每次都要申请一个为gap长度的辅助空间用来归并2个，所以空间复杂度为 O(n)。
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治 法将问题分(divide)
成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
6 堆排序
堆排序是不稳定的排序方法，辅助空间为O(1)， 最坏时间复杂度为O(nlog2n)
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，
它也是不稳定排序。首先简单了解下堆结构。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会
得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
7 快速排序O(nlogn)
在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。在此我们采用三数取中法，
也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方 法
对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
8 基数排序
是另外一种比较有特色的排序方式，它不需要直接对元素进行相互比较，也不需要将元素相互交换，
你需要做的就是对元素进行“分类”。它是怎么排序的呢？
基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：
(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如53,个位为3，则放入3号桶中）
(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中
重复(1)(2)过程，从个位到最高位（比如32位无符号整形最大数4294967296，最高位10位）
例如现在我们要将下列一组数进行排序： {13,25,1111,232,4454,79,86,98,61,447};
1）先按照各位数字进行排序，排序后结果为{1111,61,232,13,4454,25,86,447,98,79}
2) 然后再按照十位进行排序，排序结果为{1111，13，25，232，447，4454，61，79，86，98}
3）然后按照百位进行排序，如果百位为空，则认为百位为0，排序结果为{13，25，61，79，86，98，1111，232，447， 4454}
4）最后按照千位排序，排序结果为{13,25,61,79,86,98,232,447,1111,4454}