希尔排序

概念及其介绍

希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。

希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。

它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

适用说明

希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)。希尔排序没有时间复杂度为 O(n(logn)) 的快速排序算法快 ，因此对中等大小规模表现良好，但对规模非常大的数据排序不是最优选择，总之比一般 O(n^2 ) 复杂度的算法快得多。

算法思想

希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

我的理解

将数组按照步长进行分组，每一组用插入排序的方式进行排序；不断减小步长，直到步长为1，然后结束排序

部分概念引用自菜鸟教程

流程图

（1）初始增量第一趟 gap = length/2 = 4

希尔排序1.png

（2）第二趟，增量缩小为 2

希尔排序2.png
（3）第三趟，增量缩小为 1,得到最终排序结果
希尔排序3.png

希尔排序的java实现

/**
* Author: 编程的猫 iCat
* Emil: 15827348069@163.com
* Date: 3/29/21 6:07 PM
* Desc: 希尔排序
*/
public class ShellSort {

   private static final String TAG = "ShellSort====>  ";


   /**
    * 希尔排序: 将数组按照特定的步长分组，每组按照插入排序，直至步长为1
    *
    * @param array <p>
    *            疑问：如何确定数组的最合适步长？
    */
   public static void sort(int[] array) {
       for (int gap = array.length / 2; gap > 0; gap /= 2) {

           for (int i = gap; i < array.length; ++i) {

               for (int j = i; j >= gap && array[j] < array[j - gap]; j -= gap) {
                   // j >= gap && array[j] < array[j - gap] 条件成立，则交换元素的位置
                   swap(array, (j - gap), j);
               }

           }

       }
   }

   /**
    * 交换两个元素的位置
    *
    * @param array 元素的数组
    * @param left  前边元素的索引值
    * @param right 后边元素的索引值
    */
   private static void swap(int[] array, int left, int right) {
       if (array != null && array.length > right) {
           int temp = array[left];

           array[left] = array[right];

           array[right] = temp;
       }
   }

   /**
    * 打印数组的元素
    *
    * @param array 数组
    */
   public static void printArrayElement(int[] array) {
       for (int i : array) {
           Log.d(TAG, "" + i);
       }
   }
}

希尔排序的C++实现

//希尔排序思想
//将数组按照特定步长分组，每一组元素按照插入排序的方式进行排序，直至步长为1
void shellSort(int array[], int len) {
    if (array != nullptr && len > 1) {
        // 递归计算每一轮的步长
        for (int gap = len / 2; gap > 0; gap /= 2) {
            // 每一次步长增加一个跨度
            for (int i = gap; i < len; ++i) {
                // 每一次与步长相邻的元素进行比较大小
                for (int j = i; j >= gap && array[j] < array[j - gap]; j -= gap) {
                    // 如果条件 j >= gap && array[j] < array[j - gap]成立，则交换元素在数组中的位置

                    // 前一个条件 j>= gap: 当gap为最小的1时，那么j最小为1，才能进行array[1]与array[0]的比较
                    std::swap(array[j], array[j - gap]);
                }

            }

        }
    }
}