examp8_3.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自Clifford A.Shaffer著张铭等译“数据结构与算法分析”第 161 页，例8.3
//Shell排序问题解法
//Shell sort
import java.io.*;
class Examp8_3
 {
  static void shellsort(int[] array)
     {
      for(int i=array.length/2;i>2;i/=2)
       for(int j=0;j<i;j++)
       inssort2(array,j,i);
       inssort2(array,0,1);  
       
     } 
  static void inssort2(int[] a,int start,int incr)
     {
      for(int i=start+incr;i<a.length;i+=incr)
       for(int j=i;(j>=incr)&&key(a,j)<key(a,j-incr);j-=incr)
       swap(a,j,j-incr);
     }
   public static void swap(int[] q,int i,int j)
     {
      int temp;
      temp=q[i];q[i]=q[j];q[j]=temp;
     }
  public static int key( int [] q,int p)
     {  return q[p];}
  public static void main(String args[]) 
     {
     int[] a={59,20,17,13,28,14,23,83,36,98,11,70,65,41,42,15};
     System.out.println("Shell排序之前");
     for(int i=0;i<=a.length-1;i++)
     System.out.print(a[i]+"  ");
     System.out.println();
   shellsort(a);
     System.out.println("Shell排序之后");
     for(int i=0;i<=a.length-1;i++)
     System.out.print(a[i]+"  ");
     System.out.println();
    }
 }