Java插入排序：希尔排序

资料来自网络参考：

/**
 * 插入排序：希尔排序
 */
public class Shellsort2 {

	private static final int ARRAYLENGHT = 10;
	private static int[] pData = new int[ARRAYLENGHT+1];
	public static void main(String[] args) {
		
		// 随机生成待排数组,数组的第一个不赋值
		for (int i = 1; i < pData.length; i++)
			pData[i] = (int) (Math.random() * 100);

		for (int i = 1; i < pData.length; i++)
			System.out.print(pData[i] + " ");
		System.out.println("");
		// 插入排序的：希尔排序
		Shellsort2.shellSort(pData);

		System.out.println("\n***********************");

		for (int i = 1; i < pData.length; i++)
			System.out.print(pData[i] + " ");
		System.out.println("\n"+"pData[0] value is "+pData[0]);
	}
	
	//希尔排序
	public static void  shellSort(int[] seqList){
		int n = 1;
		int increment = n;//增量初值,不妨设 n>0
		do{
			increment = increment/3 + 1; //求下一增值
			shellPass(seqList,increment);//一趟增量为increment的shell插入排序
			
		}while(increment >1);
		
	}
	
	public static void  shellPass(int[] seqList,int d){
		//希尔排序中的一趟排序,d为当前增量
		int i,j;
		for(i=d+1; i<seqList.length; i++)//将seqList[d+1..n]分别插入各组当前的有序区
			if(seqList[i]<seqList[i-d]){
				seqList[0] = seqList[i];//seqList[0]只是暂存单元
				j = i-d;
				do{//查找seqList[i]的插入位置
					seqList[j+d] = seqList[j];//后移记录
					j = j-d;//查找前一记录
				}while(j>0 && seqList[0]<seqList[j]);
				seqList[j+d] = seqList[0];//插入seqList[i]到正确的位置上 
			}//endif
	}//shellPass
	
}

第二种：

import java.util.Arrays;

public class Shellsort3 {

	public static void main(String[] args) {
		int[] a = new int[10];
		for (int i = 0; i < a.length; i++) {
			a[i] = (int) (Math.random() * 100);
		}
		System.out.println("排序前：");
		System.out.println(Arrays.toString(a));

		int j = 0;
		int temp = 0;
		// 分组
		for (int increment = a.length / 2; increment > 0; increment /= 2) {
			System.out.println("increment:"+increment);
			// 每个组内排序
			for (int i = increment; i < a.length; i++) {
				temp = a[i];
				for (j = i; j >= increment; j -= increment) {
					if (temp < a[j - increment])
						a[j] = a[j - increment];
					else
						break;
				}
				a[j] = temp;
				System.out.println("   j:"+j+"  "+"a[j]:" + a[j]);//debug
				System.out.println("         ____"+Arrays.toString(a));//debug
			}
			System.out.println("____"+Arrays.toString(a));//debug
		}
		System.out.println("排序后：");
		System.out.println(Arrays.toString(a));
	}

}