最近，在通过《算法4》这本书来重新学习一下算法，从最初级的排序算法。初级的排序算法有3种：选择排序、插入排序、希尔排序。
选择排序
假定我们有一组没有顺序的数组，如{5,8,1,7,3,9,4,6}。那么，选择排序是这样的：
1、找到这个数组中最小的元素，然后与第一个元素交换；
2、在剩下的元素中找到最小的元素，与第二个元素交换；
如此重复，直至整个数组中的所有元素都按顺序排列，这样的方法就被称为选择排序。
简单排序如果用java来实现的话是这样的。
选择排序
pubic class Selection{
public static void sort(int[] numbers){
int length = numbers.length;
for(int i = 0; i < N; i++){
int min = i; //最小的数从第i位开始排起
for(int j = i+1; j < N ; j++){
//循环判断，获取最小的数值的下标
if(numbers[min] > numbers[j]){
min = j;
}
}
//更换最小值的位置
int t = numbers[i];
numbers[i] = numbers[min];
numbers[min] = t;
}
//打印出重新排序后的数值
for(int i : numbers)
System.out.print(i + " ");
}
}
其实，这和我们用眼睛在一堆数字里面找最小值没什么区别，而这个算法只是把找的步骤完整的复述出来而已。
插入排序
玩过扑克牌的知道，每一次抽牌，我们都会把牌插入手里牌组中合适的位置。而在计算机中，每次数据要插入的时候，都得先移动一下已有的数据，腾出一个空间来给这个数据插入。比如，在一个有序的数据集【1，5，8，15】中，要插入【6】，我们可以直观的看出是插入在5和8之间。但是，在计算机中，它是一个固定数组，由固定的4个空间存放这四个数字，如果要插入6，就必须把8和15往后移动一个空间，腾出来的位置才能插入6。
从这里可以看出，每一次的插入排序其实是把拿到的数字去与已经排好顺序的数组（即使一开始没有排好序的数组也不影响）进行对比，然后把它插入到合适的顺序中。
用代码说事
插入排序
public void insertionSort(){
int[ ] a = new int[ ]{3,6,9,1,5,2,8};
int len = a.length;
for(int i=1;i<len;i++){
for(int j=i; j>0 && a[j] < a[j-1]; j--){
int k = a[j];
a[j] = a[j-1];
a[j-1] = k;
}
}
for(int b : a){
System.out.print(b+" ");
}
}
首先，第一个数不进行排序，从第二个数开始，当这个数小于它的前一个数时，则两个数交换位置。交换完后通过j--继续与前一个数进行比较，直至找到合适的位置。然后再用第三个数进行比较，直接全部排序完。这样就通过插入排序得到了一个从小到大的数组。
因为插入排序每次只能比较合交换相邻的两个数字，如果数据规模过大的话，效率就显得很低了。
希尔排序
希尔排序是在插入排序的基础上做一定改进来加快排序的速度。
希尔排序
public class Shell{
public static void sort(Comparable[] a){
int N = a.length;
int h = 1;
//通过不断除以3，得到一个比N/3略大的数 h
while(h < N/3){
h = 3 * h + 1;
}
while(h >= 1){
for(int i = h;i < N ; i++){
for(int j = i ;j >= h && a[j] < a[j-h]; j -= h){
int k = a[j];
a[j] = a[j-h];
a[j-h] = k;
}
}
h = h/3;
}
}
}
希尔排序本质上还是插入排序，区别在于希尔排序一开始是把整个数组分成了若干份（这若干份数组中的元素在整个大数组中是间隔的，间隔距离是h），对这若干份先一一进行排序，然后再重新分成更少的若干份，再进行排序，直到最后只剩下一份，也就是整个数组时，这时候整个数组的排序已经接近我们想要的排序了，进行一次插入排序，需要移动的元素就很少了。相对来说，也就比直接使用插入排序会高效很多。
