希尔排序

[bosthhe1]

希尔排序是将需要排序的序列，先预排序，预排序后这个数列就接近排序完成的数列(预排序就是，首先设置一个跨度(一般跨度为Span=(N-1)/2)，然后每次按照跨度来比较，插入排序就是跨度为1，当前个和后一个比较。再第一遍把每个数据交预排序后，然后进行第二次预排序,将第二次预排序的跨度设置为Span=Span/2,然后进行排序,再跨度不断地缩小,如此往复，当跨度来到1时，就是插入排序)，然后再进行插入排序，这样的平均时间复杂度为O(N^1.3) Span越小越接近完成的数组

[bosthhe1]

#include<stdio.h>
#include<stdlib.h>

void Swap(int *a, int* b)
{
    int tem = *a;
    *a = *b;
    *b = tem;
}
void ShellSort(int *a, int n)
{
    int Span = n - 1;
    while (Span>1)
    {
        int end = 0;
        Span = Span / 2;
        for (int i = 0; i < n - Span; i++)
        {
            end = i;
            while (end >= 0)
            {
                if (a[end] > a[end + Span])
                {
                    Swap(&a[end], &a[end + Span]);
                    end -= Span;
                }
                else
                {
                    break;
                }
            }
        }

    }
}

void TestShell()
{
    int a[10] = { 7, 4, 1, 8, 5, 2, 9, 6, 3, 0 };
    int n = sizeof(a) / sizeof(a[0]);
    ShellSort(a,n);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
}

int main()
{
    TestShell();
    return 0;
}