Go语言视频零基础入门到精通

javalearner

基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。
    序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。程序的增量序列可采用递归表达式：
h=3*h+1。(h=1,4,13,40,121,364...)
    下面的程序只对30个元素进行希尔排序。
         在第一趟排序时的增量为13，即将相隔为13的元素编成一组共13组进行直接插入排序。第二趟排序时的增量为4，增量进一步缩小。由于在这两趟的插入排序中在子序列中逆序的关键字是跳跃式地移动，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序，只要作少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序低。  
   
  
// shellSort.java
// demonstrates shell sort
// to run this program: C>java ShellSortApp
class ArraySh
   {
   private long[] theArray;          // ref to array theArray
   private int nElems;               // number of data items
   public ArraySh(int max)           // constructor
      {
      theArray = new long[max];      // create the array
      nElems = 0;                    // no items yet
      }
   public void insert(long value)    // put element into array
      {
      theArray[nElems] = value;      // insert it
      nElems++;                      // increment size
      }
   public void display()             // displays array contents
      {
      System.out.print("A=");
      for(int j=0; j< nElems; j++)    // for each element,
         System.out.print(theArray[j] + " ");  // display it
      System.out.println("");
      }
   public void shellSort()
      {
      int inner, outer;
      long temp;
      int h = 1;                     // find initial value of h
      while(h <= nElems/3)
         h = h*3 + 1;                // (1, 4, 13, 40, 121, ...)
      while(h>0)                    // decreasing h, until h=1
         {
                                     // h-sort the file
         for(outer=h; outer< nElems; outer++)
            {
            temp = theArray[outer];
            inner = outer;
                                    
            while(inner > h-1 && theArray[inner-h] >=  temp)
               {
               theArray[inner] = theArray[inner-h];
               inner -= h;
               }
            theArray[inner] = temp;

          }  // end for
        h = (h-1) / 3;              // decrease h
       }  // end while(h>0)
      }  // end shellSort()
   }  // end class ArraySh
class ShellSortApp
   {
   public static void main(String[] args)
      {
      int maxSize = 30;             // array size
      ArraySh arr;
      arr = new ArraySh(maxSize);   // create the array
      for(int j=0; j< maxSize; j++)  // fill array with
         {                          // random numbers
         long n = (int)(java.lang.Math.random()*99);
         arr.insert(n);
         }
      arr.display();                // display unsorted array
      arr.shellSort();              // shell sort the array
      arr.display();                // display sorted array
      }  // end main()
   }  // end class ShellSortApp
[/code]  程序运行结果：
C:java>javac shellSort.java C:java>java ShellSortApp
A=91 79 22 25 91 24 85 87 78 36 16 45 19 93 78 78 49 38 41 24 86 19 84 70 4 55 63 72 13 51
A=4 13 16 19 19 22 24 24 25 36 38 41 45 49 51 55 63 70 72 78 78 78 79 84 85 86 87 91 91 93 C:java>

  
  
   
   

     
   

     
   
  



  










源码下载：http://file.javaxxz.com/2014/10/29/235935750.zip