希尔排序JAVA

希尔排序：在插入排序的基础上 先对数组设置一个 递减的增量 increment ,对每个增量里面的所有数组组合进行插入排序，效率比直接插入排序要高，但是不稳定。

具体测试小例子：

public static void main(String[] args) {
// TODO Auto-generated method stub
  long [] a = {10,123,32,76,123,54,36,67,89,93,23,544,232,111123};
//   for(int j=0;j<a.length;j++){
//   System.out.print(a[j]+" ");
//   }
  for(int increment = a.length/2;increment>0;increment/=2){ // 循环增量

  for(int i=0;i<increment;i++){//循环每个增量里面的子数组 总共子数组时 increment 个  
  //对每个子数组 进行插入排序

  insertSort(a,i+1,increment);  // a代表整个数组 ，I代表 在该增量 下的 第几个子数组
  System.out.println(" ");
  } 

  }
  //输出数组
  for(int j=0;j<a.length;j++){
  System.out.print(a[j]+" ");
  }
}
private static void insertSort(long [] a,int i ,int inc) { // a代表整个数组 ，I代表 在该增量 下的 第几个子数组
long tempData ;
int k,j;

System.out.print(i+" ");
for( k=i+inc;k<=a.length;k+=inc){  // 从每个子数组的第二个开始 循环代插入的数
System.out.print(k+" ");
tempData = a[k-1];//          把待排序 数组的 第二 个数 放 入临时 变量
j =k-inc-1;//前一个数
// 把每个临时变量比较后插入到 已经排序号的数组
   while(j>=0&&tempData<a[j]){  // 按照 升序排列
   a[j+inc]=a[j];            // 后移数组
   j-=inc;
   }
   a[j+inc]=tempData;  // 因为是 j-=inc 后 把 代插入的数 插入，则需+inc

}
}

评论

1 楼 endual 2012-10-05  

乱了乱了，彻底的乱了。

public static int[] shellSort(int[] arr) {
		int i, j, n = 1, temp, len = arr.length;

		while (n <= len / 2) { // 间距的控制,设定好间距一定要保证为1的存在
			n = n * 2 + 1;     // 经典的设计  
		}
		
		//int n = 
		while (n > 0) {
			for (i = n; i < len; i++) {
				temp = arr[i];
				j = i;
				while (j >= n && arr[j - n] >= temp) {
					arr[j] = arr[j - n];
					j -= n;
				}
				arr[j] = temp;
			}
			n = (n - 1)/2; // 调整间距
			System.out.println("---" + n);
		}

		return arr;
	}