首页 | 新闻 | 交流 | 问吧 | 文档 | 手册 | 下载 | 博客

ShellSort(希尔排序)

作者:  时间: 2011-03-17

/*
* 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;
}