由插入排序演变而来的希尔排序

由插入排序演变而来的希尔排序 代码实现

为了展示初级排序算法的性质,接下来我们将学习一种基于插入排序的快速排序的算法.

对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到数组的另一端,例如:如果主键较小的元素正好在数组的尽头,要将它挪到正确的位置就需要N-1次移动.希尔排序为了加快速度,改进了插入排序,交换不相邻的元素以达到整体元素的有序,再进一步使用插入排序.

public class Shell { // shell排序算法
  public static void main(String[] args) {
    int[] A = {9, 10, 7, 5, 4, 6, 2, 3, 2, 1, 0, 8};
    show(A);
    sort(A);
    assert isSorted(A);
    show(A);
  }
​
  public static void show(int[] A) {
    for (int i = 0; i < A.length; i++) {
      System.out.print(A[i] + " ");
    }
    System.out.println();
  }
​
  public static void sort(int[] A) {
    int N = A.length;
    int h = 1;
    while (h < N / 3)
      h = 3 * h + 1; // h=1,4,13,40...h
    while (h >= 1) {
      for (int i = 0; i < A.length; i++) {
        for (int j = i; j >= h && A[j] < A[j - h]; j -= h) {
          exah(A, j, j - h);
        }
    }
    h /= 3;
    }
  }
​
  public static void exah(int[] A, int i, int min) { //交换值函数
    int temp = A[i];
    A[i] = A[min];
    A[min] = temp;
  }
​
  public static boolean isSorted(int[] A) { //判断是否排序正确
    for (int i = 0; i < A.length; i++) {
      if (A[i] > A[i + 1])
        return false;
    }
    return true;
  }
}

总结一下排序算法写法规律:首先得找到合适的h,然后将作为最外层循环,终止条件设为h=1,其实也就是改进了插入排序:

//插入排序
for(int i=1;i=0&&A[j-1]>A[j];j-=1){
        exch(A,j,j-1);
    }
}
//希尔排序
while(h=1){
    for(int i=h;i=0&&A[j-h]>A[j];j-=h){
            exch(A,j,j-h);
        }
    }
    h/=3;
}

很容易发现,其实希尔排序就是将插入排序两个内层循环里面所有的“1”替换成“h”,前提是加上h的变化,直到h变成1,成为简单插入排序为止.由此可见,希尔排序确实是由简单插入排序改进而来.

复杂度分析

算法的性能并不仅仅取决于h,还取决于h之间的数学性质,比如它们的公因子等.由许多论文研究了各种不同的递增序列,但都无法证明某个序列是“最好的”.实际上,希尔排序是我们唯一无法准确描述其对于乱序数组的性能特征的分析.

算法名称最优情况平均时间复杂度空间复杂度稳定性希尔排序O(n^{1.3})O(n^2)O(1)不稳定