/*希爾排序(Shell Sort)是插入排序的一種。其基本思想是：先取定一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1 
   * 個組，所有距離為d1的倍數(shù)的記錄放在同一個組中，在各個組中進行插入排序；然后，取第二個增量d2<d1，重復(fù)上述的分組和排序， 
   * 直至所取的增量dt=1(dt<dt-1<...<d2<d1),即所有記錄放在同一組中進行直接插入排序為止。 
   * new int[]{8,5,1,7,9,4,6}，開始分割集合的間隔長度為3的情況，[[6][3][0]比較排序后，[4]和[1]比較排序后，[5]和[2]比較排序后， 
   * 分割集合的間隔長度為1，這時[1]和[0]比較排序后，[2][1][0]....,和直接插入排序一樣了。*/ 
  public static void shellSort(int[] intArray) { 
     System.out.print("將要排序的數(shù)組為:    "); 
     for(int k=0;k<intArray.length;k++) 
        System.out.print(" "+intArray[k]+" "); 
      System.out.println(); 
     
    int arrayLength=intArray.length; 
    int j,k;//循環(huán)變量 
    int temp;//暫存變量 
    boolean isChange;//數(shù)據(jù)是否改變 
    int dataLength;//分割集合的間隔長度 
    int pointer;//進行處理的位置 
    dataLength=arrayLength/2;//初始集合間隔長度 
    while(dataLength!=0){//數(shù)列仍可進行分割 
      //對各個集合進行處理 
      for(j=dataLength;j<arrayLength;j++){ 
        isChange=false; 
        temp=intArray[j];//暫存，待交換值時用 
        pointer=j-dataLength;//計算進行處理的位置 
        //進行集合內(nèi)數(shù)值的比較與交換值 
        while(temp<intArray[pointer]&&pointer>=0&&pointer<arrayLength){ 
          intArray[pointer+dataLength]=intArray[pointer]; 
          //計算下一個欲進行處理的位置 
          pointer=pointer-dataLength; 
          isChange=true; 
          System.out.print("every changing result: "); 
          for(k=0;k<arrayLength;k++) 
            System.out.print(" "+intArray[k]+" "); 
          System.out.println(); 
          if(pointer<0||pointer>arrayLength) 
            break; 
        } 
        //與最后的數(shù)值交換 
        intArray[pointer+dataLength]=temp; 
        if(isChange){ 
          System.out.print("Current sorting result: "); 
          for(k=0;k<arrayLength;k++) 
            System.out.print(" "+intArray[k]+" "); 
          System.out.println(); 
        } 
      } 
      System.out.print("指定分割集合的間隔長度為"+dataLength+"，對各個集合進行處理后，Current sorting result: "); 
      for(k=0;k<arrayLength;k++) 
        System.out.print(" "+intArray[k]+" "); 
      System.out.println(); 
      dataLength=dataLength/2;//計算下次分割的間隔長度 
    } 
  } 

將要排序的數(shù)組為:     8 5 1 7 9 4 6  
every changing result: 8 5 1 8 9 4 6  
Current sorting result: 7 5 1 8 9 4 6  
every changing result: 7 5 1 8 9 4 8  
every changing result: 7 5 1 7 9 4 8  
Current sorting result: 6 5 1 7 9 4 8  
指定分割集合的間隔長度為3，對各個集合進行處理后，Current sorting result: 6 5 1 7 9 4 8  
every changing result: 6 6 1 7 9 4 8  
Current sorting result: 5 6 1 7 9 4 8  
every changing result: 5 6 6 7 9 4 8  
every changing result: 5 5 6 7 9 4 8  
Current sorting result: 1 5 6 7 9 4 8  
every changing result: 1 5 6 7 9 9 8  
every changing result: 1 5 6 7 7 9 8  
every changing result: 1 5 6 6 7 9 8  
every changing result: 1 5 5 6 7 9 8  
Current sorting result: 1 4 5 6 7 9 8  
every changing result: 1 4 5 6 7 9 9  
Current sorting result: 1 4 5 6 7 8 9  
指定分割集合的間隔長度為1，對各個集合進行處理后，Current sorting result: 1 4 5 6 7 8 9