ShellSort(希尔排序)

时间：2011-03-17 来源：SnowBee3012

/*
* ShellSort.c
*
* Author: MagicYun
*
* O(n^1.5) key: f(n) = 3 * f(n - 1) + 1
*
*/

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

void Show(int *list, int n) //show the list
{
int i;
for(i = 0; i < n; i++)
{
printf("%d ",*(list + i));
}
printf("\n");
}

void ShellInsert(int *list, int n, int key) //insert sort base on key
{
int i,j;
for(i = key; i < n; i++)
{
for(j = i; j >= key && *(list + j) < *(list + j - key); j -= key)
{
int tmp = *(list + j);
*(list + j) = *(list + j - key);
*(list + j - key) = tmp;
}
}
}

void ShellSort(int *list, int n)
{
int key = n >> 1;
while(key)
{
ShellInsert(list, n, key);
key >>= 1;
// Show(list, n);
}
}

int main()
{
int a[13] = {5, 4, 3, 2, 1, 32, 43, 56, 99, 34, 8, 54, 76};

Show(a, 13);
ShellSort(a, 13);
Show(a, 13);

return 0;
}

相关阅读更多 +