shellSort
//测试工具类在这里 https://www.cnblogs.com/paidaxing7090/p/15080493.html import 测试工具类.SortTestHelper; public class ShellSort { // 我们的算法类不允许产生任何实例 private ShellSort(){} public static void sort(Comparable[] arr){ int n = arr.length; // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093... int h = 1; while (h < n/3) h = 3*h + 1; while (h >= 1) { // h-sort the array for (int i = h; i < n; i++) { Comparable e = arr[i]; int j = i; for ( ; j >= h && e.compareTo(arr[j-h]) < 0 ; j -= h) arr[j] = arr[j-h]; arr[j] = e; /* for (int k =0;k<arr.length;k++) { System.out.print(arr[k] + " "); if (k==arr.length - 1){System.out.println();} }*/ } h /= 3; } } public static void main(String[] args) { int N = 100000; Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10000); Integer[] clone = arr.clone(); SortTestHelper.testSort("sort.InsertionSort2", clone); SortTestHelper.testSort("sort.ShellSort", arr); return; } }
可以看到shellSort 比直接插入排序效率要高很多。
希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行依次直接插入排序。
shellSort 会导致想等元素的相对位置发生变化,所以是不稳定的。