插入排序&&希爾排序

插入排序我看了下動圖，哦，對對，推薦個好的網站，動态展示算法，排序的

位址：https://visualgo.net/en

嗯，言歸正傳，插入排序把，就是

把第一個标記成已排序了，然後第二個拿出來，跟第一個比一下，比第一個大就不用動，比第二個小就挪到前邊去，效果就是小的前邊大的後邊，接下來，再把第三個拿出來，跟前邊的都比，從第二個開始，然後第一個，倒序比，找個比前變大比後邊小的位置，插進去，就跟上圖展示的一樣

代碼實作：

package com.eyuninfo.bean.exception;

public class Order {
	public static void main(String[] args) {
		int[] array = { 5, 2, 100, 2, 3, 8, 10 };
		order(array);
		for (int i = 0; i < array.length; i++) {
			System.out.println(array[i]);
		}
	}

	public static int[] order(int[] array) {

		for (int i = 1; i < array.length; i++) {
			int current = array[i];
			while (i >= 1 && array[i - 1] > current) {
				array[i] = array[i - 1];
				i--;
			}
			array[i] = current;
		}

		return array;
	}
}
           

希爾排序：

在插入排序基礎上進一步優化

希爾排序的基本步驟，在此我們選擇增量gap=length/2，縮小增量繼續以gap = gap/2的方式，這種增量選擇我們可以用一個序列來表示，{n/2,(n/2)/2...1}，稱為增量序列。希爾排序的增量序列的選擇與證明是個數學難題，我們選擇的這個增量序列是比較常用的，也是希爾建議的增量，稱為希爾增量，但其實這個增量序列不是最優的。

如圖展示的，數組大小除以2，是5就按着每隔4個取數，把得到的分組分别進行插入排序，然後5再除以2餘2，再按着每隔一個取數，插入排序，最後再除以2=1，進行最後一次插入排序

package com.eyuninfo.bean.exception;

public class Order {
	public static void main(String[] args) {
		int[] array = { 5, 2, 100, 2, 3, 8, 10 };
		shellSort(array);
		for (int i = 0; i < array.length; i++) {
			System.out.println(array[i]);
		}
	}

	public static void shellSort(int[] a){
		int n = a.length;
		for(int h = n / 2; h > 0; h /= 2){//希爾增量
			for(int i = h; i < n; i++){
				//将a[i]插入到a[i-h],a[i-2h],a[i-3h]...中
				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] = temp;
				}
			}
		}
	}
}