初级排序算法-选择排序、插入排序、希尔排序

选择排序

选择排序思想
1、假设第一个元素是最小元素，依次从后面的元素中一直到N位置，找到一个最小的元素记录下来，执行一次交换（与最小的元素）
2、然后开始找第二小的元素，重复第一步(以第二个元素为最小元素，依次从向后找，直到到达N位置）。

public void selectionSort(int[] a){
	int length = a.length;
	for(int i = 0; i < length; i++){
		int min = i;
		for(int j = i+1; j < length; j++){
			if(a[min]>a[j]){
				min = j;
			}
		}
		//将找到的最小值与i位置互换
		if(i != min){
			int temp = a[min];
			a[min] = a[i];
			a[i] = a[min];
		}
	}
}

插入排序

插入排序的思想:
先以第一个元素为初始插入第二个元素，组成一个临时数组，然后用插入的元素，与已经有的数组元素依次比较（有序的数组），找到合适位置执行交换。得到一个有序数组。然后插入第三个元素，依次类推。

public void selectionSort(int[] a){
	int length = a.length;
	for(int i = 1; i < length; i++){
		for(int j = i; j > 0 && a[j] < a[j-1]; j--){
			int temp = a[j];
			a[j] = a[j-1];
			a[j-1] = a[j];
		}
	}
}

希尔排序

思想 : 将数组分成h个小数组，然后插入排序，完成以后，在减小h的值，在进行插入排序。依次类推直到h=1
如： 6 5 4 3 2 1
先分成 h=4个，4小数组依次是 [6,2] 、[5,1] 、[4] 、[3]
然后进行依次进行插入排序得到 2 1 4 3 6 5

最后 h=1，进行插入排序得到 1 2 3 4 5 6
上面的例子不太好，请看下图

    public static void sort(int[] a){
        int N = a.length;
        int h = 1;
        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 temp = a[j];
					a[j] = a[j-h];
					a[j-h] = a[j];
                }
                h = h / 3;
            }
        }
    }

h可以自己定义规则，并不一定如上面代码所示

总结

选择排序、插入排序、希尔排序 都是属于数量级较小集时使用的排序。 根据测试结果比较，如果数据集大小在100以内，选择排序要比插入排序快。 如果在1000左右，插入排序要比选择排序快。 其次插入排序适合做部分有序的数据集。 对于逆序数据，选择排序要高很多。
希尔排序是插入排序的一个变种，或者说是优化。但是它的执行步骤规律比较有限，很难用数学知识进行估算。