首页 > 代码库 > 希尔排序
希尔排序
希尔排序的关键思想是使序列中任意间隔h的元素都是有序的，其中h是一个递增序列，使得该递增序列（如1/2 (3k-1))递减（从N / 3开始递减到1），当h为1时，整个序列就是有序的了。简易实现及测试用例如下：
1 import java.util.logging.Handler; 2 3 4 public class Shell { 5 6 private static void exch(Comparable[] a, int i , int j){ 7 Comparable tmp = a[i]; 8 a[i] = a[j]; 9 a[j] = tmp;10 }11 12 private static boolean less(Comparable a, Comparable b)13 {14 return (a.compareTo(b) < 0);15 }16 17 private static void show(Comparable[] a)18 {19 int N = a.length;20 for(int i = 0; i < N; i++)21 {22 System.out.print(a[i] + " ");23 }24 System.out.println();25 }26 27 public static boolean isSorted(Comparable[] a)28 {29 int N = a.length;30 for(int i = 1; i < N; i++)31 {32 if(less(a[i], a[i - 1])) return false;33 }34 return true;35 }36 37 public static void sort(Comparable[] a)38 {39 int N = a.length;40 int h = 1;41 while(h < N / 3) h = 3 * h + 1;42 while(h >= 1)43 {44 for(int i = h; i < N; i++)45 {46 for(int j = i; j >= h && less(a[j], a[j - h]); j -= h)47 exch(a, j, j - h);48 }49 h = h / 3;50 }51 }52 53 public static void main(String[] args) {54 String[] a = StdIn.readAllStrings();55 Selection.sort(a);56 show(a);57 }58 }
希尔排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。