`
xitonga
  • 浏览: 579566 次
文章分类
社区版块
存档分类
最新评论

算法导论 之 希尔排序[C语言]

 
阅读更多

一、优缺点

希尔排序的时间复杂度与其增量序列有关,这涉及到数学上尚未解决的难题。迄今为止,还没有人找到最好的增量序列。其时间复杂度为O(n^s){s, 1<s<2},其没有快速排序O(nlgn)快,因此对于中等大小规模表现良好,对于规模非常大的数据排序不是最优选择,但是比O(n^2)复杂度的算法快得多。提倡:几乎任何排序工作在开始时都可以使用希尔排序,若在运行中证明其不够快,可改成快序排序这样的高级的排序算法。

二、算法实现

其代码实现如下:

int shell_sort(int *array, int max)
{
	int d = 0;

	d = max>>1;
	while(d > 0)
	{
		shell_insert(array, d, max);
		inc >>= 1;
	}

	return 0;
}
void shell_insert(int *array, int d, int max)
{
	int i=0, j=0, k=0;

	for(i=1; i<=d; i++)
	{
		for(j=i+d; j<=max; j+=d)
		{
			k = j-d;
			if(array[k] > array[k+d])
			{
				array[0] = array[k+d];
				do
				{
					array[k+d] = array[k];
					k -= d;
				}while(k>0 && array[k]>array[0]);

				array[k+d] = array[0];
			}
		}
	}
}
三、函数调用
void print(int *array, int max)
{
	int idx = 0;

	for(idx=1; idx<=max; idx++)
	{
		fprintf(stdout, "array[%d] = %d\n", idx, array[idx]);
	}
}

int main(int argc, const char *argv[])
{
	int max = ARRAY_NUM - 1;
	int array[ARRAY_NUM] = {-1, -21, 25, -72, 20, -29, 4, 13, 2, 1, -30};

	shell_sort(array, max);

	print(array, max);

	return 0;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics