插入排序错误解析

今天在看麻神理工学院的《算法导论》的公开课，其中第一课中列举了一个例子就是插入排序，想着好久都没写过了就尝试写一下，其中出了写错误，在此写出来，以防后面再犯错。

程序是用windows下的gcc编译的。

错误代码：

#include "stdio.h"

#define LENG 10

int main()
{
	int a[LENG]={4,1,3,7,6,0,8,2,9,5};
	int i=0;
	for (i=1; i<LENG; i++)
	{
		int j=i-1,temp=a[i];
		while (j>=0 && a[j]>a[i])
		{
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=a[i];
	}
	for (i=0; i<LENG; i++)
	{
		printf("%d\t",a[i]);
	}
	return 0;
}

错误原因：

    在程序中，数组的下标就类似与这个数组所开辟的内存空间中的哪一块地址。由于在while循环中，数组中的内容的顺序是不断变化的，导致a[i]的值是不断变化的（i的值在每一趟循环中式不变的），因此就会判断错误。

正确代码：

#include "stdio.h"

#define LENG 10

int main()
{
	int a[LENG]={4,1,3,7,6,0,8,2,9,5};
	int i=0;
	for (i=1; i<LENG; i++)
	{
		int j=i-1,temp=a[i];
		while (j>=0 && a[j]>temp)
		{
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=temp;
	}
	for (i=0; i<LENG; i++)
	{
		printf("%d\t",a[i]);
	}
	return 0;
}

评论

2 楼 greatghoul 2011-07-28  

引用

麻神理工学院的《算法导论》的公开课

这学校老出名了，不管你信不信，反正我是信了。

1 楼 greatghoul 2011-07-28  

楼主说的在理，顶一个。