希爾排序

一，概念：希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經過改進之後的一個更高效的版本，也稱為縮小增量排序，同時該算法是沖破O(n2）的第一批算法之一

二，複雜度：希爾排序時間複雜度是 O(n^(1.3-2))，空間複雜度為常數階 O(1)。希爾排序沒有時間複雜度為 O(n(logn)) 的快速排序算法快 ，是以對中等大小規模表現良好，但對規模非常大的資料排序不是最優選擇，總之比一般 O(n^2 ) 複雜度的算法快得多

三：代碼

#include<stdio.h>
#include<stdlib.h>
//堆排序用于查找最大值 或者 最小值
void show(int *p, int n)
{
    for (int i = 0; i < n;i++)
    {
        printf("%4d", p[i]);
    }
    printf("\n");
}
void shellsort(int *p, int length)
{
    int d = length / 2;//增量
    while (d >= 1)//增量終止條件
    {
        for (int i = d; d < length && i < length; i++)//最後的位置
        {
            int x = p[i];//備份資料
            int j = i - d;//與其對于的前面的元素
            while (j >= 0 && p[j]>x)//在數組範圍内  找到擦入的位置
            {
                p[j + d] = p[j];
                j = j - d;//每次變化
            }
            p[j + d] = x;//交換
        }
        //d = d / 2;
        d--;//增量自由設定
    }
}
void main()
{
    int a[8] = { 1, 8, 2, 7, 3, 6, 4, 5 };
    show(a, 8);
    shellsort(a, 8);
    show(a, 8);
}