目录

要求代码复杂度时间复杂度空间复杂度 稳定性

要求

将数值数组按从小到大排序。

代码

public class Shell { public static void sort(Comparable[] a) { int N = a.length; // 确定增长量h的最大值 int h = 1; while(h<N/2) { h = h * 2 + 1; } // 当增长量h小于1，排序结束 while(h>=1) { // 找到待插入的元素 for(int i=h;i<N;i++) { // a[i]就是待插入的元素 // 把a[i]插入到a[i-h],a[i-2h],a[i-3h]....序列中 for(int j=i;j>=h;j-=h) { // a[j]就是待插入的元素，依次和a[j-h],a[j-2h],a[j-3h]进行比较，如果a[j]小，那么交换位置 if(greater(a[j-h],a[j])) { exch(a, j, j-h); }else { break; } } } h /= 2; } } // 比较v元素是否大于w元素 private static boolean greater(Comparable v, Comparable w) { return v.compareTo(w) > 0; } // 交换数组a中，索引i和索引j处的值 private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } } public class Test { public static void main(String[] args) { Integer[] a = {4,8,6,1,3,5,6}; Shell.sort(a); System.out.println(Arrays.toString(a)); } } [1, 3, 4, 5, 6, 6, 8]

复杂度

时间复杂度

最好情况O(n)，最坏情况O(n^2)，平均O(n ^ 1.3)

空间复杂度

O(1)

稳定性

不稳定