2
选择排序(Selection Sort)
说到选择排序，这个也是灰常易于理解的。相信大家看一眼基本原理就懂了。还是以数组A[n]与升序排列为例说明问题。
基本原理：
1）先从A[0]~A[n]中找最小的元素A[i]，交换A[0]和A[i]的位置。
2）再从剩下的元素A[1]~A[n]中找最小的元素A[j]，交换A[1]和A[j]的位置。
3）不断在剩下的元素中找最小的元素丢到开头，直到剩下最后一个元素。
还不懂？再来看看个图片：
代码哪能少？
选择排序每次将最小值丢到开头的时候，有可能会打乱相等元素的位置。因此，它是不稳定的。也注意区分其和冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。
3
插入排序(Insertion Sort)
大家打过扑克牌嘛？我们在对手上的扑克牌进行排序的时候，是不是将右手上的牌插到左手上已经排序好的牌之间？这跟我们的插入排序是有点类似的。
还是以A[n]为例说明问题。
基本原理：
1）从A[0]开始，则A[0]可认为是已排序列。
2）取出下一个元素(比如A[1])，在已排序列中从右往左扫描，如果已排序列中的元素大于取出的元素，那么就将该元素（已排序列中的）往后挪一个位置。
3）直到在已排序列中找到一个小于等于取出元素的元素。将取出元素插入该元素（已排序列中的）后一个位置。
4）不断重复步骤2-3.直到所有元素都插入到已排序列。
还不明白？看看图片
请问代码在哪里？？？
亲，这么详细的注释，
别跟我说你看不懂
可以看出，关于相等元素，排序前后并不会改变他们的位置。因此，插入排序又是稳定的。
4
希尔排序(Shell Sort)
希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。其中希尔排序是基于以下几点做出改进的：
1）直接插入排序对于几乎排好的数据有着极高的效率。基本可以达到线性排序时的效率。
2）但是对于一般的乱序数据来说，直接插入排序由于每次只能将数据往后搬一位，从这点上来说它效率又是及其低下的。
基本原理：
1）将无序数据分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行直接插入排序；
2）然后再选择一个更小的增量，再将数据分割为多个子序列进行直接插入排序......
3）不断重复步骤2，直到最后增量变为1，即对所有数据使用直接插入排序（此时所有数据几乎都排好了，直接插入效率较高），最终排序完成。
唉，小编就不指望你们能看懂，还是来看看图片吧。
关于不同增量的选取对于希尔排序性能的影响，有不同的观点。这里就不过多赘述。
代码！代码！代码在哪里！！！？？？
值得一提的是，由于数据划分为多个区域，在每个区域中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。因此希尔排序是不稳定的排序。
