希尔排序(Shell Sort)

是插入排序经过改进之后的高效版本，也称缩小增量排序。

1959 年提出，是突破时间复杂度 O(n2) 的第一批算法之一。

缩小增量排序的最优增量选择是一个数学难题，一般采用希尔建议的增量，具体如下。

思路与步骤：

首次选择的增量(即步长，下同) step = 数组长度 / 2 取整；缩小增量step ，每次减半，直到为 1 结束缩小；逐渐缩小的增量组成一个序列：[n/2, n/2/2, ... 1]
对数组进行序列里增量的个数趟排序
每趟排序，把增量作为间隔，将数组分割成若干子数组，分别对各子数组进行插入排序
当增量等于 1 时，排序整个数组后，排序完成

代码：

package constxiong.interview.algorithm;
/** *  希尔排序 * @author ConstXiong * @date 2020-04-11 11:58:58 */public class ShellSort {
  public static void main(String[] args) {    int [] array = {33, 22, 1, 4, 25, 88, 71, 4};    shellSort(array);  }
  /**   * 希尔排序   * @param array   */  private static void shellSort(int[] array) {    print(array);    int length = array.length;    int step = length / 2; //步长，默认取数组长度一半    int temp;     while (step > 0) {      for (int i = step; i < length; i++) { //从步长值为下标，开始遍历        temp = array[i]; //当前值        int preIndex = i - step; //步长间隔上一个值的下标        //在步长间隔的的数组中，找到需要插入的位置，挪动右边的数        while (preIndex >= 0 && array[preIndex] > temp) {           array[preIndex + step] = array[preIndex];          preIndex -= step;        }        //把当前值插入到在步长间隔的的数组中找到的位置        array[preIndex + step] = temp;      }      step /= 2;      print(array);    }  }
  /**   * 打印数组   * @param array   */  private static void print(int[] array) {    for(int i : array) {      System.out.print(i + " ");    }    System.out.println();  }
}

打印：

33 22 1 4 25 88 71 4 25 22 1 4 33 88 71 4 1 4 25 4 33 22 71 88 1 4 4 22 25 33 71 88

特征：

空间复杂度为 O(1)，是原地排序算法
最好、最坏、平均情况时间复杂度，都是 O(nlog2 n)
非稳定排序。因为进行了增量间隔分组排序，可能导致相等的值先后顺序变换

更多相关文章

随机推荐