前言

一種將無(wú)序數(shù)組進(jìn)行排序的方法。

希爾排序是插入排序的一個(gè)變種。
wiki 參考：https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

對(duì)于普通的插入排序，數(shù)組無(wú)論是物理上還是邏輯上都是當(dāng)作一維數(shù)組來(lái)對(duì)待。
希爾排序則將一維數(shù)組轉(zhuǎn)化為邏輯上的多維數(shù)組（類似于矩陣，雖然不嚴(yán)謹(jǐn)），對(duì)矩陣的每一列進(jìn)行獨(dú)立的普通插入排序。通過(guò)不斷的減少列的數(shù)量，最后變?yōu)橹挥幸涣械木仃囋龠M(jìn)行獨(dú)立的普通插入排序。

遞歸，主要思想：將任務(wù)轉(zhuǎn)換為單一目的的循環(huán)，可以找到退出條件。

遞歸希爾排序， 主要思想：每次遞歸改變矩陣的列，直到矩陣列為1，插入排序結(jié)束后即退出。

環(huán)境

編輯器：vs2019
文件：.c類型

正文

代碼參考：

#include <stdio.h>




// 希爾排序，從小到大
// wiki源碼
// 對(duì)于學(xué)習(xí)來(lái)說(shuō)，這種算法的源碼，已經(jīng)做出各種優(yōu)化，并不能很直觀的反映出邏輯。
void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp;
    for (gap = len >> 1; gap > 0; gap >>= 1)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}


// 希爾排序，從小到大
void shell_sort_normal(int source_array[], int source_array_length)
{
    // 參考wiki
    // 希爾排序的核心，將一維數(shù)組邏輯劃分為矩陣形式，依次減少矩陣的列，最后形成只有一列的數(shù)組。在每一次劃分邏輯矩陣時(shí)，均對(duì)每一列進(jìn)行插入操作，讓每一列變得更加有序。
    // 在代碼中定義一個(gè)跨度--gap，從而生成邏輯上的矩陣。
    // gap 一般可以通過(guò)列表反復(fù)除2得出，直到為0終止(整型除法特點(diǎn))
    for (int gap = source_array_length / 2; gap > 0; gap = gap / 2)
    {
        // 按列插入排序
        // 插入排序有個(gè)特點(diǎn)：已插入排序的數(shù)組都是有序的，因此后面的元素可以直接單向往前比較即可找到合適的位置。
        // 從插入排序得出的經(jīng)驗(yàn)，從第二個(gè)元素開(kāi)始插入，在這里就是第二行。因此 i=gap 開(kāi)始。
        // 這里的插入方法借鑒于wiki，當(dāng)然可以使用自己的邏輯進(jìn)行插入。上一篇的【插入排序】使用的就是自己最原始直觀的邏輯。
        int j;
        int tmp;
        for (int i = gap; i < source_array_length; i++)
        {
            tmp = source_array[i];
            // 開(kāi)始插入，其它元素移位。按已排序數(shù)組的后端開(kāi)始移位
            for (j = i - gap; j >=0; j -= gap)
            {
                // 如果當(dāng)前元素 tmp 小于該位置元素，則該位置元素向后移動(dòng)
                // wiki 中退出循環(huán)邏輯，通過(guò)for中的條件控制，這里為了方便思考，顧單獨(dú)拿出來(lái)。
                if (tmp < source_array[j])
                {
                    // 前一個(gè)元素后移
                    source_array[j + gap] = source_array[j];
                }
                else
                {
                    // 若當(dāng)前元素 tmp 不小于該位置元素，證明找到了合適的位置。接下來(lái)就是將當(dāng)前位置賦值為tmp
                    // 不在else中直接賦值，是因?yàn)榇嬖?tmp是整列最小的情況，不會(huì)進(jìn)入else，直接退出了循環(huán)。因此在循環(huán)外對(duì)合適的位置賦值更加好。當(dāng)然，在這里進(jìn)行賦值也是可以實(shí)現(xiàn)的。
                    break;
                }
            }
            source_array[j + gap] = tmp;
        }
    }
}


// 遞歸希爾排序，從小到大
// 這里的loop_num 初始值設(shè)為 source_array_length / 2, 參考普通希爾排序的 gap，控制矩陣的列
void shell_sort_recursive(int source_array[], int source_array_length, int gap)
{
    int j;
    int tmp;
    for (int i = gap; i < source_array_length; i++)
    {
        tmp = source_array[i];
        for (j = i - gap; j >= 0; j -= gap)
        {
            if (tmp < source_array[j])
            {
                source_array[j + gap] = source_array[j];
            }
            else
            {
                break;
            }
        }
        source_array[j + gap] = tmp;
    }
    gap = gap / 2;
    if (gap <= 0)
    {
        return 0;
    }
    shell_sort_recursive(source_array, source_array_length, gap);
}


int* upset_array(int source_list[], int source_list_length)
{
    for (int i = 0; i < source_list_length; i++)
    {
        int rand_index = rand() % source_list_length;
        int tmp_value = source_list[i];
        source_list[i] = source_list[rand_index];
        source_list[rand_index] = tmp_value;
    }
    return source_list;
}


int main()
{
    // 生成隨機(jī)測(cè)試列表
    int test_list[10];
    int test_list_length = sizeof(test_list) / sizeof(int);
    printf("測(cè)試列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        test_list[i] = rand() % 100;
        printf("%d ", test_list[i]);
    }
    printf("\n");


    // 希爾排序
    shell_sort_normal(test_list, test_list_length);
    printf("普通希爾排序結(jié)果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 打亂數(shù)組
    upset_array(test_list, test_list_length);
    printf("打亂測(cè)試列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 遞歸希爾排序
    shell_sort_recursive(test_list, test_list_length, test_list_length / 2);
    printf("遞歸希爾排序結(jié)果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");
}

執(zhí)行結(jié)果參考：

image.png