数据结构与算法篇-希尔排序-技术圈

—

希尔排序算法思想

希尔排序也是一种插入排序，是简单插入排序改进后的一个更高效版本，同时也是首批突破O(n^2)算法之一。

希尔排序算法思想：希尔排序是按照下标增量进行分组，对每组使用插入排序算法进行排序，随着增量减少，每组包含的关键字越来越多，增量减到1时，整个序列被分为一组，算法终止。

我们以增序排序为例，希尔排序基本步骤：选择初始增量gap = length / 2，缩小增量继续以gap = gap / 2的方式进行，直到增量gap = 1为止，增量的每次变化都会将原始序列划分为若干组，分别对每一组进行插入排序，每一次通过增量划分组进行插入排序宏观上小的数移到了前面，大的数移到了后面，最后增量gap = 1进行插入排序后就是最终的有序序列。本文会以图解的方式详细介绍希尔排序算法的整个工作过程。

原始序列

增量gap = 4分组图

增量gap = 4排序结果图

增量gap = 2分组图

增量gap = 2排序结果图

增量gap = 1分组图

增量gap = 1排序结果图

—

希尔排序算法实现

希尔排序完整源码如下：

//插入排序
void insert_sort(int *arr, int length, int start, int gap){
    if(arr == NULL || length <= 0 || start < 0 || gap <= 0){
        return;
    }
    int i = 0, j = 0;
    int value = 0;

    for(i = start; i < length - gap; i += gap){
        value = arr[i + gap];
        for(j = i; j >= start; j -= gap){
            if(value < arr[j]){
                arr[j + gap] = arr[j];
            }else{
                break;
            }
        }
        arr[j + gap] = value;
    }
}

//希尔排序
void shell_sort(int *arr, int length){
    if(arr == NULL || length <= 0){
        return;
    }
    int gap = 0, start = 0;
    int count = 0;
    for(gap = length / 2; gap > 0; gap /= 2){
        start = 0;
        for(count = 0; count < length / gap; count++){
            insert_sort(arr, length, start, gap);
            start++;
        }
    }
}

现在写一个小程序验证算法的正确性，代码如下：

#include <stdio.h>
#include "shell_sort.h"

int main() {
    int i = 0;
    printf("希尔排序结果\n");
    int arr[7] = {8, 23, 64, 12, 0, 5, 6};
    shell_sort(arr, 7);
    for(i = 0; i < 7; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

编译运行输出如下：

希尔排序结果
0 5 6 8 12 23 64

算法完全正确！