希尔排序：将相距某个”增量”的记录组成一个子序列，保证在子序列中分别进行直接插入排序后得到的结果基本有序而不是局部有序，不稳定 ，时间复杂度 O(n 3/2)

代码

  1. /**
  2.  * @Description: 希尔排序：将相距某个”增量“的记录组成一个子序列，保证在子序列中分别进行直接插入排序后得到的结果基本有序而不是局部有序
  3.  * 不稳定 ，时间复杂度 O(n 3/2)
  4.  * @Author: lizhouwei
  5.  * @CreateDate: 2018/6/23 10:50
  6.  */
  7. public class ShellSort {
  9.     public static void shellSort(Integer[] arr) {
  10.         if (arr == null || arr.length == 0) {
  11.             return;
  12.         }
  13.         SortUtil.printArray("希尔排序前", arr);
  14.         int increment = arr.length;
  15.         Integer temp;
  16.         int j;
  17.         do {
  18.             increment = increment / 3 + 1;
  19.             for (int i = increment; i < arr.length; i++) {
  20.                 if (arr[i] > arr[i - increment]) {
  21.                     continue;
  22.                 }
  23.                 temp = arr[i];
  24.                 for (j = i - increment; j >= 0 && temp < arr[j]; j = j - increment) {
  25.                     arr[j + increment] = arr[j];
  26.                 }
  27.                 arr[j + increment] = temp;
  28.             }
  29.         } while (increment > 1);
  31.         SortUtil.printArray("希尔排序后", arr);
  33.     }
  34. }

时间复杂度

时间复杂度为，由于记录时跳跃式的移动，所以希尔排序并不是一种稳定的排序算法。