各种排序算法
冒泡排序：是从左边第一个与右边的每一个都一个一个对比，如果大于的，则交换，然后用交换完的继续与更右边的元素对比，直到最后一个，最后n-1的位置存储的就是值最大的元素。。。然后再从左边开始...与右边对比，然后放到n-2位置上......然后n-3..最后再到0位置.....就排序完成
时间复杂度是O(n^2)，而且正常情况下交换数据次数较多，效率比其他O(n^2)排序算法低一些，更不用说O(nlogn)的排序算法了
选择排序：从整个数组中找出最小的，与数组的第0元素交换，然后从索引1元素开始再往右找最小的元素，然后再与索引1元素交换。。。从索引2...索引3....索引n...排序完成(复杂度与冒泡差不多，代码具体效率会高一点，因为交换次数比较少)
时间复杂度O(n^2)
直接插入排序:一组数据无序的数组k，2, 5, 6, 0, 3, 9, 1, 7, 4, 8
当第i+1个元素小于第i个元素时，把第i+1个元素插入到0~i元素之间，插入后保证0~i+1元素之间是有序的。
以上面的数据为例，从左往右对比，k[2]>k[3]，
所以此时需要把k[3]插入到k[0]~k[2]之间，并且保持有序。插入后数组为:0 , 2, 5, 6, 3, 9, 1, 7, 4, 8。
然后再从K[3]开始往右对比....剩下的与上面一样。
希尔排序：是对直接插入排序的改进。
将序列分为若组，分组不是逐段分的，而是设置一个增量d,距离为d的倍数为一组，再将d=d/2(也可以是d=d/3+1等等)进行分组，直至d=1，每次分组的数据都使用直接插入排序算法进行排序。
分析：数组a[10]={5,8,4,3,9,6,1,7,2,10}
5 8 4 3 9 6 1 7 2 10
第一趟：n=10，d=n/2=5
5 - - - - 6
8 - - - - 1
4 - - - - 7
3 - - - - 2
9 - - - -10
这里分了五组，对着五组每组都使用直接插入排序。
排序完后的五组为：
5 - - - - 6
1 - - - - 8
4 - - - - 7
2 - - - - 3
9 - - - -10
得到：5 1 4 2 9 6 8 7 3 10
第二趟：d=d/2=2
5 - 4 - 9 - 8 - 3
1 - 2 - 6 - 7 - 10
这里分了两组，对着两组每组都分别使用直接插入排序。
排序完后的两组为：
3 - 4 - 5 - 8 - 9
1 - 2 - 6 - 7 - 10
得到：3 1 4 2 5 6 8 7 9 10
第三趟：d=d/2=1
当间隔d=1时，只分为一组
则直接对所有数据进行直接插入排序就行了。
得到：1 2 3 4 5 6 7 8 9 10
堆排序：把一组无序的数据，先排成大顶堆或者小顶堆。当元素有n个，排成大顶堆时(以数组形式存储)，第一次把堆顶元素(死索引为0)与索引为n-1位置元素交换，然后重新把0~n-2之间的元素再排成大顶堆(此时操作范围是0~n-2之间，然后把堆顶元素进行下沉操作就行了)
归并排序：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序示例：
实现方法：把一组数据每次分为两个序列，然后这两序列每个序列又再次分为两个序列。。。直到每个序列的元素只有一个为止（对应于上图的第一行）。然后第一个序列与第二个序列融合进一个大的序列，融合后这个大序列里面的元素保持有序（对应于上图的第二行）。。。然后这个大序列又与另一个大序列融合进一个更大的序列，融合后更大序列的元素是有序的（对应于上图的第三行）....直到最后融合的序列元素个数与总元素个数相等....
可以用递归实现，也可以用循环实现。
基数排序：
第一步
以LSD为例，假设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
第二步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
第三步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
快速排序:
找第一个元素a[0]的值作为 基数，从数组最右边 往左对比，找出比a[0]小的值，与a[0]对换，然后记下这个值位置(假设a[9]）。。现在a[9]是之前的a[0]，然后，开始从数组的左边开始对比(由于a[0]现在的值是比小，所以 为了节省效率 没必要再对比了，让i++以后再比较，也就是从a[1]开始)。。此时从左往右，找到一个比基数大的值，再与基数交换……以此类推。。。第一个大循环结束后，该基数左边的数肯定比基数小，右边的比基数大(这样，基数在数组中的位置就确定了)，然后，再把基数左边的数 看成一个新数组，右边的数也看成一个新数组，再利用前面的方法，各自再找一个基数……递归下去。。。然后，每个数都做过基数，那么 这些基数最终都会找到自己的位置，然后，排序完成。。
优化快速排序:
(1).基数的选择要更加合理，方法:每一个序列中头、中、尾选择三个元素，这三个中值处于中间大小的作为基数。
(2).交换次数可以减少，变成赋值运行。。把基数取出，记住基数被交换后的索引即可，被交换的其他元素只需直接赋值到基数所处位置。