希尔排序

/*
希尔排序

在直接插入排序算法中，每次插入一个数，使有序序列只增加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,array.length);
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
}
/*
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; 
    } 
}
*/
}