排序 - 插入排序 [2 - 希尔排序]

墨蓝 2022-10-02 02:00 105阅读 0赞

在上一篇中我说了基本插入排序的基本算法，不知道你是不是花了正好20分钟。

这一篇我说下对基本插入排序的改进算法，希尔排序。shell sort.

为什么改进：

基本插入排序的算法决定了一个事实，那就是每次都跟紧邻的上一个元素进行比较，如果满足条件就交换，交换的步长也就只能是： 1 （因为相邻）。

对于这样的序列：\{3, 5, 9, 2\},

当对最后一个元素 2 进行插入排序的时候，他需要以此跟9,  5, 3进行比较。

能不能有一个算法让他们跳着比较呢？这样在交换的时候一下子就能跳过几个元素做交换，这样就突破了步长只能是1的限制。

希尔排序：

希尔排序正是这样的一种算法。

他的基本思想是这样的：

1. 确定初始步长，一般设定为待排序元素个数 除以 2；

2. 以步长为单位分组，比如步长为4，则假设有10个元素，则：

1， 5 （1+4），9（1+4+4）为一组

2， 6（2+4），10（2+4+4）为一组

3，7 （3+4）为一组

4，8（4+4）为一组。

3. 这样我们得到了4组数字，然后分别对这4组数字做希尔排序，排序后再按照他们原来的索引，组织到一起，还是10个元素。

4. 但此时，这组数据已经基本有序，我们可以保证：\#1 < \#5 < \#9, \#2 < \#6 < \#10,...

5. 接着我们再对这10个元素进行分组，这次步长设置为2。

6. 按照上面的做法进行分组，步长为2，10个元素，我们会得到两组数据：

1， 3， 5， 7， 9

2， 4， 6， 8， 10

7. 再对他们进行排序，向结果更进一步；

8. 最后步长为1时，再进行插入排序的时候，已经是完全有序了。

插图如下：

![SouthEast][]

希尔排序的Java实现。

static void shellSort (int[] arr) {
         // 初始步长
         int step = arr.length / 2;
         
         // 当步长大于等于1 的时候，表示排序工作尚未结束
         while (step >= 1) {
           // 我们是从 step 开始做循环
           // 因为比如当step = 4的时候，首个元素下标为0
           // 则 0 + 4 = 4，那么意味着 #4 元素要跟 #0 元素进行比较
           // 且当i++后，i就等于5，#5 跟 #1 进行比较
           // 比较的工作在内层循环中完成
           for (int i = step; i < arr.length; i++) {
             int tmp = arr[i];
             
             // 这里的 j -= step 实现了分组的功能
             // 因为只会跟step踩到的元素比较
             for (int j = i - step; j >= 0; j -= step) {
                 if (tmp < arr[j]) {
                   arr[j + step] = arr[j];
                   arr[j] = tmp;
                 }
                 else { 
                   break;
                 }
             }
           }
           
           // 逐渐缩短步长以接近目标
           step = step / 2;
         }
      }

忘说这个了：

时间复杂度 小于O(n^2)

空间复杂度 O(1)

接着我会说对冒泡排序的算法和对冒泡改进的快速排序。

[SouthEast]: /images/20220113/3ddf9be50ae24b40ad06da7d145ce33c.png