九大排序算法之希尔排序
- 算法思想
排序思想 - 代码实现
import java.util.*; //希尔排序（插入排序的快速排序算法）：使数组中任意间隔为h的元素是有序的，h不断减小 //时间复杂度：NlogN,空间复杂度：1 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) { exch(a,j,j-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++) { System.out.print(a[i]+" "); } System.out.println(); } public static boolean isSorted(Comparable[] a) { for(int i=1;i<a.length;i++) { if(less(a[i],a[i-1])) return false; } return true; } public static void main(String[] args) { String[] a= {"3","2","4","5","7"}; sort(a); assert isSorted(a); show(a); } }
