?2.1.9按照算法2.3所示轨迹的格式给出希尔排序是如何将数组 E A S Y S H E L L S O R T Q U E S T I O N排序的。
答：灰底色表示相关元素未互换，黄底色表示相关元素互换。1-sort省略，与插入排序相同。
public class Shell{??? public static void sort(Comparable[] a)??? {??????? int N=a.length;??????? int h=1;??????? while (h<N/3) h=3*h+1;??????? while (h>=1)??????? {??????????? for (int i=h;i<N;i++)??????????? {???????????? //?? for (int j=i;j>=h && less(a[j],a[j-h]);j-=h)???????????????? for (int j=i;j>=h ;j-=h)??????????????? {?????????????????? if(h>1) StdOut.printf("h=%-5d i=%-5d j=%-5dn",h,i,j);??????????????????? if( less(a[j],a[j-h]))?? exch(a,j,j-h);??????????????? }??????????? }??????????? h=h/3;??????? }??? }??? ??? private static boolean less(Comparable v,Comparable w)??? { return v.compareTo(w)<0;}??? ??? private static void exch(Comparable[] a,int i,int j)??? {??????? Comparable t=a[i];??????? a[i]=a[j];??????? a[j]=t;??? }??? ??? private static void show(Comparable[] a)??? {??????? for (int i=0;i<a.length;i++)??????????? StdOut.print(a[i]+" ");??????? StdOut.println();??? }??? ??? public static boolean isSorted(Comparable[] a)??? {??????? for (int i=0;i<a.length;i++)??????????? if(less(a[i],a[i-1])) return false;??????? return true;??? }??? ??? public static void main(String[] args)??? {??????? String[] a={"E","A","S","Y","H","E","L","O","R","T","Q","U","I","N"};??????? sort(a);??? }?? }
