希尔排序

发布于 2021-08-31  42 次阅读


希尔排序是直接插入排序的优化,通过预处理先将目标数组进行简单的排序,使目标数组进行一定的规则化,以达到简化直接插入排序次数的目的

例如我们现在有数组a[8]{5,8,6,3,9,2,1,7}现将其以数组长度的一半为跨度分组,也就是每隔4个元素一组,在a数组中5与9一组,8与2一组,6与1一组3与7一组,进行直接插入排序,然后我们得到新的数组 a{5,2,1,3,9,8,6,7} ,继续分组,这次以2为跨度分组即,5,1,9,6一组,2,3,8,7一组分别对两组进行直接插入排序于是得到a{1,2,5,3,6,7,9,8},最后以1为跨度进行分组,也就是直接进行直接插入排序
也有更加高效的其他分组方法,其中最具代表性的是Hibbard增量和Sedgewick增量。

Hibbard的增量序列如下:

1,3,7,15……

通项公式 2^k-1

利用此种增量方式的希尔排序,最坏时间复杂度是O(n^(3/2))

Sedgewick的增量序列如下:

1, 5, 19, 41, 109……

通项公式
$$
94^k - 92^k + 1 或者 4^k - 3*2^k + 1
$$
利用此种增量方式的希尔排序,最坏时间复杂度是O(n^(4/3))

#include<stdio.h>
#include<stdlib.h>
void Shell_Sort(int *pArr,int size){
    int i = 0;
    int key = 0;
    int end = 0;
    int gap = 3;
    while (gap > 0)
    {
        for (i = gap; i < size; i++)
        {
            key = pArr[i];
            end = i - gap;
            while (end >= 0 && key<pArr[end])
            {
                pArr[end + gap] = pArr[end];
                end=end-gap;
            }
            pArr[end + gap] = key;
        }
        gap--;
    }
}
int main(){
    int i = 0;
    int array[9] = { 2, 6, 4, 9, 5, 8, 7, 0, 1 };
    int size = sizeof(array) / sizeof(array[0]);
    Shell_Sort(array, size);
    for (i = 0; i < size; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    system("pause");
    return 0;
}