希尔排序

#include <stdio.h>

void myPrint(int *A, int len);
void mySwap(int *A, int *B);
void shellPass(int *A, int d, int len);
void shellSort(int *A, int len);

int
main(void)
{
        int a[] = {1,3,5,7,9,0,2,4,6,8,0};
        int len = sizeof(a)/sizeof(a[0]);

        myPrint(a, len);
        shellSort(a, len);
        myPrint(a, len);

        return (0);
}

void
myPrint(int *A, int len)
{
        printf("Enter: ");
        int i = 0;
        for (i = 0; i < len; i++) {
                printf("%d,",*(A+i));
        }
        printf("\n");
}

void
mySwap(int *A, int *B)
{
        int tmp;
        tmp = *A;
        *A = *B;
        *B = tmp;
}

void
shellPass(int *A, int d, int len)
{
        int i, j, k;
        int tmp;
        for (i = 0; i < d; i++) {
                for (j = d*(i+1); j < len; j += d) {
                        tmp = *(A+j);
                        k = j-d;
                        while (k >= i && *(A+k) > tmp) {
                                *(A+k+d) = *(A+k);
                                k -= d;
                        }
                        *(A+k+d) = tmp;
                }
        }
}

void
shellSort(int *A, int len)
{
        if (len <= 1)
                return ;

        int inc = len;
        do {
                inc = inc/3 + 1;
                shellPass(A, inc, len);
        } while (inc > 1);
}

稳定性：非稳定
T(n): O(n^l.25,1.6n^1.25)
S(n): O(1)