希爾排序(Shell Sort)演算法，改良的插入排序法

希爾排序(Shell Sort)演算法是插入排序(Insertion Sort)演算法的改良版。它解決了插入排序法一次只能把元素移動一個索引距離的問題，加入間距(gap)的概念來分批並分組完成插入排序法，有效提升原本插入排序法的速度。

希爾排序法(Shell Sort)

希爾排序法的概念

希爾排序法是基於插入排序法的演算法，如果您還不了解插入排序法的話，請先參考這篇文章：

希爾排序法在插入排序法的基礎上添加了間距(gap)的概念，使得插入排序法可以分組執行，並且元素的移動距離可以大於一。希爾排序法會對序列由大至小，小則至1，來選擇應用在插入排序法上的間距，這樣一來就可以讓序列後端比較小的元素，在被使用前面幾次的大間距插入排序法排序之後，就先被移動到較前端的位置，使它們在最後的快速排序法中，不需要大老遠的從後端以一次一個索引距離的方式來移動到前端。

希爾排序法的過程

假設現在有個陣列資料，內容如下：

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢？

如果在一開始我們選擇使用的間距是3的話，希爾排序法則會以以下的分組方式來執行快速排序法：

索引    0   1   2   3   4   5   6   7   8   9
數值   69          38          47          79
           81           9          61
               30           2          32

所以經過排序後，陣列內的元素分佈如下：

索引    0   1   2   3   4   5   6   7   8   9
數值   38          47          69          79
            9          61          81
                2         30          32

索引    0   1   2   3   4   5   6   7   8   9
數值   38   9   2  47  61  30  69  81  32  79

如果在下一次我們選擇使用的間距是2的話，希爾排序法則會以以下的分組方式來執行快速排序法：

索引    0   1   2   3   4   5   6   7   8   9
數值   38       2      61      69      32
            9      47      30      81      79

經過排序後，陣列內的元素分佈如下：

索引    0   1   2   3   4   5   6   7   8   9
數值    2      32      38      61      69
            9      30      47      79      81

索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  32  30  38  47  61  79  69  81

最後使用間距1，來完成排序：

索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81

希爾排序法的程式實作

/// 希爾排序法(遞增)。
pub fn shell_sort(array: &mut [i32], gaps: &[usize]) {
    let length = array.len();

    for gap in gaps.iter().copied() {
        'outer: for i in gap..length {
            let temp = array[i];

            let mut j = i - gap;

            while temp < array[j] {
                array[j + gap] = array[j];

                if j < gap {
                    array[j] = temp;
                    continue 'outer;
                }

                j -= gap;
            }

            array[j + gap] = temp;
        }
    }
}

/// 希爾排序法(遞減)。
pub fn shell_sort_desc(array: &mut [i32], gaps: &[usize]) {
    let length = array.len();

    for gap in gaps.iter().copied() {
        'outer: for i in gap..length {
            let temp = array[i];

            let mut j = i - gap;

            while temp > array[j] {
                array[j + gap] = array[j];

                if j < gap {
                    array[j] = temp;
                    continue 'outer;
                }

                j -= gap;
            }

            array[j + gap] = temp;
        }
    }
}

至於間距到底要怎麼設定才會是最快的，就得看要排序什麼樣的資料啦！目前已知的間距最佳通用值，是Marcin Ciura找出來的，如下：

pub const CIURA_GAPS: [usize; 9] = [1750, 701, 301, 132, 57, 23, 10, 4, 1];

/**
 * 希爾排序法(遞增)。
 */
public static void shellSort(final int[] array, final int[] gaps) {
    for (final int gap : gaps) {
        for (int i = gap; i < array.length; ++i) {
            final int temp = array[i];

            int j = i - gap;

            while (j >= 0 && temp < array[j]) {
                array[j + gap] = array[j];

                j -= gap;
            }

            array[j + gap] = temp;
        }
    }
}

/**
 * 希爾排序法(遞減)。
 */
public static void shellSortDesc(final int[] array, final int[] gaps) {
    for (final int gap : gaps) {
        for (int i = gap; i < array.length; ++i) {
            final int temp = array[i];

            int j = i - gap;

            while (j >= 0 && temp > array[j]) {
                array[j + gap] = array[j];

                j -= gap;
            }

            array[j + gap] = temp;
        }
    }
}

至於間距到底要怎麼設定才會是最快的，就得看要排序什麼樣的資料啦！目前已知的間距最佳通用值，是Marcin Ciura找出來的，如下：

public static int[] CIURA_GAPS = new int[]{1750, 701, 301, 132, 57, 23, 10, 4, 1};

/**
 * 希爾排序法(遞增)。
 */
function shellSort(array: number[], gaps: number[]) {
    for (const gap of gaps) {
        for (let i = gap;i < array.length;++i) {
            const temp = array[i];

            let j = i - gap;

            while (j >= 0 && temp < array[j]) {
                array[j + gap] = array[j];
                j -= gap;
            }

            array[j + gap] = temp;
        }
    }
}

/**
 * 希爾排序法(遞減)。
 */
function shellSortDesc(array: number[], gaps: number[]) {
    for (const gap of gaps) {
        for (let i = gap;i < array.length;++i) {
            const temp = array[i];

            let j = i - gap;

            while (j >= 0 && temp > array[j]) {
                array[j + gap] = array[j];
                j -= gap;
            }

            array[j + gap] = temp;
        }
    }
}

至於間距到底要怎麼設定才會是最快的，就得看要排序什麼樣的資料啦！目前已知的間距最佳通用值，是Marcin Ciura找出來的，如下：

const CIURA_GAPS = [1750, 701, 301, 132, 57, 23, 10, 4, 1];

// 希爾排序法(遞增)。
func ShellSort(array []int, gaps []int) {
	length := len(array)

	for _, gap := range gaps {
		for i := gap; i < length; i += 1 {
			temp := array[i]

			j := i - gap

			for j >= 0 && temp < array[j] {
				array[j+gap] = array[j]
				j -= gap
			}

			array[j+gap] = temp
		}
	}
}

// 希爾排序法(遞減)。
func ShellSortDesc(array []int, gaps []int) {
	length := len(array)

	for _, gap := range gaps {
		for i := gap; i < length; i += 1 {
			temp := array[i]

			j := i - gap

			for j >= 0 && temp > array[j] {
				array[j+gap] = array[j]
				j -= gap
			}

			array[j+gap] = temp
		}
	}
}

至於間距到底要怎麼設定才會是最快的，就得看要排序什麼樣的資料啦！目前已知的間距最佳通用值，是Marcin Ciura找出來的，如下：

var CIURA_GAPS = []int{1750, 701, 301, 132, 57, 23, 10, 4, 1}

希爾排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。

項目	值	備註
最差時間複雜度	#{{O(n^2)}}# #{{O(n \log^2 n)}}#	使用最差的間距。使用Marcin Ciura的間距值。
最佳時間複雜度	#{{O(n \log n)}}# #{{O(n \log^2 n)}}#	使用最佳的間距。使用Marcin Ciura的間距值。
平均時間複雜度	? #{{O(n \log^2 n)}}#	根據間距值來決定。使用Marcin Ciura的間距值。
最差空間複雜度	#{{O(1)}}#
是否穩定	否	如果是普通的插入排序法則是穩定的。