概念及其介紹

希爾排序(Shell Sort)是插入排序的一種，它是針對(duì)直接插入排序算法的改進(jìn)。

希爾排序又稱縮小增量排序，因 DL.Shell 于 1959 年提出而得名。

它通過(guò)比較相距一定間隔的元素來(lái)進(jìn)行，各趟比較所用的距離隨著算法的進(jìn)行而減小，直到只比較相鄰元素的最后一趟排序?yàn)橹埂?/p>

適用說(shuō)明

希爾排序時(shí)間復(fù)雜度是 O(n^(1.3-2))，空間復(fù)雜度為常數(shù)階 O(1)。希爾排序沒(méi)有時(shí)間復(fù)雜度為 O(n(logn)) 的快速排序算法快 ，因此對(duì)中等大小規(guī)模表現(xiàn)良好，但對(duì)規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇，總之比一般 O(n^2 ) 復(fù)雜度的算法快得多。

算法思想

希爾排序目的為了加快速度改進(jìn)了插入排序，交換不相鄰的元素對(duì)數(shù)組的局部進(jìn)行排序，并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。

我的理解

將數(shù)組按照步長(zhǎng)進(jìn)行分組，每一組用插入排序的方式進(jìn)行排序；不斷減小步長(zhǎng)，直到步長(zhǎng)為1，然后結(jié)束排序

部分概念引用自菜鳥(niǎo)教程

流程圖

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

希爾排序1.png

（2）第二趟，增量縮小為 2

希爾排序2.png

希爾排序3.png

希爾排序的java實(shí)現(xiàn)

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

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


   /**
    * 希爾排序: 將數(shù)組按照特定的步長(zhǎng)分組，每組按照插入排序，直至步長(zhǎng)為1
    *
    * @param array <p>
    *            疑問(wèn)：如何確定數(shù)組的最合適步長(zhǎng)？
    */
   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);
               }

           }

       }
   }

   /**
    * 交換兩個(gè)元素的位置
    *
    * @param array 元素的數(shù)組
    * @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;
       }
   }

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

希爾排序的C++實(shí)現(xiàn)

//希爾排序思想
//將數(shù)組按照特定步長(zhǎng)分組，每一組元素按照插入排序的方式進(jìn)行排序，直至步長(zhǎng)為1
void shellSort(int array[], int len) {
    if (array != nullptr && len > 1) {
        // 遞歸計(jì)算每一輪的步長(zhǎng)
        for (int gap = len / 2; gap > 0; gap /= 2) {
            // 每一次步長(zhǎng)增加一個(gè)跨度
            for (int i = gap; i < len; ++i) {
                // 每一次與步長(zhǎng)相鄰的元素進(jìn)行比較大小
                for (int j = i; j >= gap && array[j] < array[j - gap]; j -= gap) {
                    // 如果條件 j >= gap && array[j] < array[j - gap]成立，則交換元素在數(shù)組中的位置

                    // 前一個(gè)條件 j>= gap: 當(dāng)gap為最小的1時(shí)，那么j最小為1，才能進(jìn)行array[1]與array[0]的比較
                    std::swap(array[j], array[j - gap]);
                }

            }

        }
    }
}