1.动画演示

希尔.gif

2.思路分析

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。
而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
来看下希尔排序的基本步骤，在此选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处做示例使用希尔增量。
微信图片_20210730215533.png

3.复杂度分析

1. 时间复杂度：最坏情况下，每两个数都要比较并交换一次，则最坏情况下的时间复杂度为O（n2）, 最好情况下，数组是有序的，不需要交换，只需要比较，则最好情况下的时间复杂度为O（n）。
经大量人研究，希尔排序的平均时间复杂度为O（n1.3）（这个我也不知道咋来的，书上和博客上都这样说，也没找到个具体的依据，，，）。
2. 空间复杂度：希尔排序，只需要一个变量用于两数交换，与n的大小无关，所以空间复杂度为：O（1）。

4.代码实现

交换法

  1. public class ShellSort {
  2.     public static void main(String[] args) {
  3.         int arr[] = {1,3,2,4,7,5,9,6,8,0};
  4.         System.out.println(Arrays.toString(arr));
  5.         shellSort2(arr);
  6.         System.out.println(Arrays.toString(arr));
  7.     }
  9.     /**
  10.      * arr.length/2 为分几组
  11.      * gap 增量（步长）
  12.      * @param arr
  13.      */
  14.     public static void shellSort(int[] arr){
  16.         // 使用逐步推导的方式来编写希尔排序
  17.         // 希尔排序时， 对有序序列在插入时采用交换法,
  18.         // 思路(算法) ===> 代码
  19.         //分组分组再分组
  20.         int temp = 0;
  21.         int count = 0;
  22.         for (int gap = arr.length/2; gap > 0 ;gap /= 2){  //第一轮的增量为数组长度/2，后面的增量为前面增量再/2
  23.             for (int i = gap;i < arr.length ; i++){
  24.                 for (int j = i-gap; j >= 0 ; j -= gap) {//每组的数据按小到大的顺序排序
  25.                     if (arr[j] > arr[j+gap]){
  26.                         temp = arr[j];
  27.                         arr[j] = arr[j+gap];
  28.                         arr[j+gap] = temp;
  29.                     }
  30.                 }
  32.             }
  33.             System.out.println("希尔排序"+(++count)+"轮后=" + Arrays.toString(arr));
  34.         }
  35.     }
  36. }

代码优化：移位法

  1.   //对交换式的希尔排序进行优化->移位法
  2.     public static void shellSort2(int[] arr) {
  4.         // 增量gap, 并逐步的缩小增量
  5.         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  6.             // 从第gap个元素，逐个对其所在的组进行直接插入排序
  7.             for (int i = gap; i < arr.length; i++) {
  8.                 int j = i;
  9.                 int temp = arr[j];
  10.                 if (arr[j] < arr[j - gap]) {
  11.                     while (j - gap >= 0 && temp < arr[j - gap]) {
  12.                         //移动
  13.                         arr[j] = arr[j-gap];
  14.                         j -= gap;
  15.                     }
  16.                     //当退出while后，就给temp找到插入的位置
  17.                     arr[j] = temp;
  18.                 }
  20.             }
  21.         }
  22.     }

推导

  1. // 希尔排序的第1轮排序
  2.         // 因为第1轮排序，是将10个数据分成了 5组
  3.         for (int i = 5; i < arr.length; i++) {//第一轮增量为5
  4.             // 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
  5.             for (int j = i - 5; j >= 0; j -= 5) {
  6.                 // 如果当前元素大于加上步长后的那个元素，说明交换
  7.                 if (arr[j] > arr[j + 5]) {
  8.                     temp = arr[j];
  9.                     arr[j] = arr[j + 5];
  10.                     arr[j + 5] = temp;
  11.                 }
  12.             }
  13.         }
  15.         System.out.println("希尔排序1轮后=" + Arrays.toString(arr));//
  18.         // 希尔排序的第2轮排序
  19.         // 因为第2轮排序，是将10个数据分成了 5/2 = 2组
  20.         for (int i = 2; i < arr.length; i++) {
  21.             // 遍历各组中所有的元素(共5组，每组有2个元素), 步长2
  22.             for (int j = i - 2; j >= 0; j -= 2) {
  23.                 // 如果当前元素大于加上步长后的那个元素，说明交换
  24.                 if (arr[j] > arr[j + 2]) {
  25.                     temp = arr[j];
  26.                     arr[j] = arr[j + 2];
  27.                     arr[j + 2] = temp;
  28.                 }
  29.             }
  30.         }
  34.         // 希尔排序的第3轮排序
  35.         // 因为第3轮排序，是将10个数据分成了 2/2 = 1组
  36.         for (int i = 1; i < arr.length; i++) {
  37.             // 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
  38.             for (int j = i - 1; j >= 0; j -= 1) {
  39.                 // 如果当前元素大于加上步长后的那个元素，说明交换
  40.                 if (arr[j] > arr[j + 1]) {
  41.                     temp = arr[j];
  42.                     arr[j] = arr[j + 1];
  43.                     arr[j + 1] = temp;
  44.                 }
  45.             }
  46.         }

运行结果

  1. [1, 3, 2, 4, 7, 5, 9, 6, 8, 0]
  2. 希尔排序1轮后=[1, 3, 2, 4, 0, 5, 9, 6, 8, 7]
  3. 希尔排序2轮后=[0, 3, 1, 4, 2, 5, 8, 6, 9, 7]
  4. 希尔排序3轮后=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

image.png