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

算法导论 之 插入排序[C语言]

 
阅读更多

1、 算法实现

插入排序的时间复杂度为O(n^2),其排序过程就如同打牌时抓牌的过程。其实现算法如下:

int insert_sort(int *array, int num)
{
	int i=0, j=0;

	for(j=2; j<num-1; j++)
	{
		i = j-1;
		array[0] = array[j]; /* array[0]为哨兵 */

		while(array[i] < array[0])
		{
			array[i+1] = array[i];
			i--;
		}
		array[i+1] = array[0];
	}

	return 0;
}

2、 算法调用

#define ARRAY_NUM (10)

int main(int argc, void *argc)
{
	int idx = 0;
	int array[ARRAY_NUM] = {0, 9, 8, 7, 6, 5, 4, 3, 2, 1};

	insert_sort(array, ARRAY_NUM);

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

	return 0;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics