算法-希尔排序

package com.arithmetic.sort;
/**
 * Shell Sort 其實是對Insert Sort的優化，因為當一個初始化的數組有序或者比較有序，且數據量
 * 也不是太大的時候，可能沒啥大問題，當初始化的數組很大且雜亂無章，插入排序的時候，插入的次數就很多
 * 這樣對效率也大打折扣。所以此時Shell Sort可以 是一組數組 接近有序，然後再進行插入排序，這樣的話
 * 插入的次數就很少了
 * @author Administrator
 *
 */
public class ShellSort {
	public static void main(String[] args) {
		int [] arrays = new int[]{1002,2,989,344,24,3,15,6,909,13,12,112,56,100,67,81,671,456,23,231,34,456,567,98,123};
		//计算数组长度
		int len = arrays.length;
		//控制增量变化，变多少，自己结合实际情况而定，此处我们假设增量为5，每一次递减2，但是要确保增量最后大于0
		for(int gap = 5; gap > 0; gap -= 2){
			//我们需要从0开始，遍历数据，但是长度变量长度最好不超过（len-gap）因为超过了又是以前便利过的那一组去了
			for(int x = 0; x < len-gap; x++){
				//此时我们需要根据每一个组第一个数据，去得到该组的所有数据
				for(int y = x; y < len; y += gap){
					//开始进行插入排序
					for(int index = y; index > 0; index-=gap){
						//如果 开始位置下标小于增量，我们就跳过本次循环，否则数组下标越界
						if(index < gap){
							continue;
						}
						if(arrays[index] < arrays[index-gap]){
							int tmp = arrays[index];
							arrays[index] = arrays[index-gap];
							arrays[index-gap]= tmp;
						}
					}
				}
			}
		}
		for(int i = 0; i<arrays.length;i++){
			System.out.print(arrays[i]+" ");
		}
		System.out.println();
	}
	
}