1. 简介

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：

  1. 在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
  2. 然后逐渐将增量减小,并重复上述过程。
  3. 直至增量为1,此时数据序列基本有序,最后进行插入排序。

2. Java实现

  1. public static void shellSort(int[] arr) {
  2.     int length = arr.length;
  3.     int temp;
  4.     for (int gap = length / 2; gap >= 1; gap /= 2) {
  5.         for (int i = gap; i < length; i++) {
  6.             temp = arr[i];
  7.             int j = i - gap;
  8.             while (j >= 0 && arr[j] > temp) {
  9.                 arr[j + gap] = arr[j];
  10.                 j -= gap;
  11.             }
  12.             arr[j + gap] = temp;
  13.         }
  14.     }
  15. }

测试一下: 

  1. public static void main(String[] args) {
  2.     int[] arr = new int[100];
  3.     for (int i = 0; i < arr.length; i++) {
  4.         arr[i] = (int) (Math.random() * 100);
  5.     }
  6.     shellSort(arr);
  7.     for (int i = 0; i < arr.length; i++) {
  8.         System.out.print(arr[i]);
  9.         System.out.print(' ');
  10.     }
  11. }

3. 复杂度

  • 时间复杂度是O(nlogn) ~ O(n²)
  • 空间复杂度为常数阶 O(1)