直接插入排序

    插入排序是比较直观的排序方法，它是在前面已排序好的i-1个元素中插入第i个元素，它是一种原位排序，即只需要使用O（1）的额外空间，最坏的情况下（数组是逆序的）时间复杂度为O（N^2）,最好的情况下（数组已经排好序），时间复杂度为O（N），插入排序是一种的稳定的排序。插入排序算法的工作过程如下：（1）第一个元素可以认为已经排好序，从下一个元素开始，在已经排序的元素中从后向前遍历（2）遍历到大于tmp的元素，则将该元素后移一个位置（3）重复步骤（2）直到把所有较大元素后移（4）tmp插入到适当位置（5）重复以上步骤。比如数组a[10]={ 23,6,7,61,83,54,43,31,9,7},排序的过程是：

第一趟：tmp=6    6,23,7,61,83,54,43,31,9,7

第二趟：tmp=7    6,7,23,61,83,54,43,31,9,7

第三趟：tmp=61   6,7,23,61,83,54,43,31,9,7

第四趟：tmp=83   6,7,23,61,83,54,43,31,9,7

第五趟：tmp=54    6,7,23,54,61,83,43,31,9,7

第六趟：tmp=43     6,7,23,43,54,61,83,31,9,7

第七趟：tmp=31     6,7,23,31,43,54,61,83,9,7

第八趟：tmp=9      6,7,9,23,31,43,54,61,83,7

第九趟：tmp=7      6,7,7,9,23,31,43,54,61,83

直接插入排序的程序为：

# include <stdio.h>
# include <stdlib.h>
# define N 10
int main()
{   
	int i;
	void insertsort(int a[]);
	int a[N]={23,6,7,61,83,54,43,31,9,7};
	insertsort(a);
	for(i=0;i<N;i++)
		printf("%d\t",a[i]);
system("pause");
return 0;
}

void insertsort(int a[])  //插入排序
{
int i,j,tmp;
for (i=1;i<N;i++)        
{
	tmp=a[i];
	for(j=i;j>0&&a[j-1]>tmp;j--)
		a[j]=a[j-1];   //较大元素后移
	a[j]=tmp;
}
}

直接插入排序,布布扣,bubuko.com

直接插入排序

原文：http://blog.csdn.net/u011608357/article/details/20841477