希尔排序

/*
希尔排序

在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

希尔排序是不稳定的，其时间复杂度为O(n ^2)。
*/

public class ShellSort{
	
	 public static void main(String[] args){
//		 int[] array = {49,38,65,97,76,13,27};
		 int[] array = {49,38,65,97,76,13,27,49,55,04};
		 shellSort(array);
		 for(int i=0;i<array.length;i++){
			 System.out.print(array[i]+" ");
		 }
	 }
          
           public static void shellSort(int[] data) {  
	        int j = 0;  
	        int temp = 0;  
	        for (int increment = data.length / 2; increment > 0; increment /= 2) {  
	            for (int i = increment; i < data.length; i++) {  
	                temp = data[i];  
	                for (j = i; j >= increment; j -= increment) {  
	                    if(temp < data[j - increment]){  
	                        data[j] = data[j - increment];  
	                    }else{  
	                        break;  
	                    }  
	                }   
	                data[j] = temp;  
	            }  
	        }  
	    } 
	 /*
	public static void shellSort(int[] arr,int length){
		int h;
		
		while(arr.length/3>h){
			h = h*3+1;
		}
		
		while(h>0){
			for(int i=h;i>0;i++){
				int temp = arr[i];
				int j =i;
				while(j >h-1 && arr[j-h]>temp ){
					arr[j] = arr[j-h];
					j -=h;
				}
				arr[j] = temp;
			}
			h=(h-1)/3;
		}
	}
	*/
	 /*
	 public static void  shellSort(int[] array,int length){
	    int increment=length/2; //增量初值,不妨设n>0
	    do {
	    	shellPass(array,increment,length);//一趟增量为increment的Shell插入排序
	          increment=increment/3+1;//求下一增量
	       }while(increment>1);
	 } //ShellSort

	 public static void shellPass(int[] array,int d,int length){//希尔排序中的一趟排序,d为当前增量
	     for(int i=d+1;i<length;i++) //将R[d+1．．n]分别插入各组当前的有序区
	       if(array[i]<array[i-d]){
	         array[0]=array[i];
	         int j=i-d;//R[0]只是暂存单元,不是哨兵
	         do {//查找R[i]的插入位置
	            array[j+d]=array[j];//后移记录
	            j=j-d;//查找前一记录
	         }while(j>0&&array[0]<array[j]);
	         array[j+d]=array[0]; //插入R[i]到正确的位置上
	       } //endif
	   } //ShellPass
	*/
	 /*
	 //希尔排序, array要排序的数据, len数据的个数
	 public static void shellSort(int[] array, int len){
	     //以step分组,step每次减为原来的一半。
	     for (int step = len / 2; step > 0; step /= 2){
	         //对每个组进行排序
	         for (int i = 0 ;i < step; i++){
	             sortGroup(array, len, i, step);
	         }
	     }

	 }
	 
	 public static void sortGroup(int[] array, int len, int start,int step){
	     for (int i = start + step; i < len; i += step){
	         //寻找i元素的位置,
	         for (int j = start; j < i; j+= step){
	             //如果比他小,则这里就是他的位置了
	             if (array[j]>array[i]){
	                 int nTemp = array[i];
	                 for (int k = i; k > j; k -= step){
	                     array[k] = array[k - step];
	                 }
	                 array[j] = nTemp;
	             }
	         }
	     }
	 }
	

	 
	 
	 public static void shellSort2(int arr[], int n){  
	     int i, j;  
	     int key;  
	     int h;  
	   
	     for (h = 1; h <= (n-1)/9; h = 3*h + 1)   
	    	 for (; h > 0; h /= 3)  
	    		 for (i = h; i < n; i++){  
		             key = arr[i];  
		             j = i;  
		             while ((j >= h) && (arr[j-h] > key)){  
		                 arr[j] = arr[j-h];  
		                 j -= h;  
		             }  
		             arr[j] = key;  
	    		 }  
	 }
	 */
}