希尔排序（交换式和移位式）

交换式

代码

protected static void shellSort1(int[] arr) {
		int temp = 0;
		for(int gap = arr.length / 2;gap > 0; gap /= 2){
			for(int i = gap;i < arr.length; i ++){
				for(int j = i - gap; j >= 0; j-=gap){
					if(arr[j] > arr[j + gap]){
						temp = arr[j];
						arr[j] = arr[j + gap];
						arr[j + gap] = temp;
					}
				}
			}
		}
	}

结果

运行效率（8万个随机数）

测试10次之后，大多数在8s左右，少几次在6s

移位式（目前所有排序最快的）

代码

protected static void shellSort2(int[] arr) {
		for(int gap = arr.length / 2;gap > 0; gap /= 2){
			for(int i = gap;i < arr.length; i ++){
				int j = i;
				int temp = arr[j];
//				if(arr[j] < arr[j - gap]){
					while((j - gap) > 0 && temp < arr[j - gap]){
						arr[j] = arr[j - gap];
						j -= gap;
					}
					arr[j] = temp;
//				}
			}
		}
	}

运行效率

		//8000 0000 39095ms
		//800 0000 2594ms
		//80 0000 178ms
		//8 0000 28ms