直接插入排序是一种比较简单的排序方法，它的基本操作是：假设排序的记录存储在数组C[1..n]中，在排序过程的某个时刻，C被划分为两个子区间，C[1..i-1]和C[i..n],其中前一个为已排好的有序区，而后一个为无序区，开始时有序区中只含有一个元素C[1]，无序区中为C[2..n]。排序过程中，只需要每次从无序区中取出第一个元素，把它插入到有序区的适当位置,使之成为新的有序区，依次这样经过n-1次插入后，无序区为空，有序区包含了全部n个元素，至此排序完毕.用一个C示例说明如下

#include <stdio.h>
#include <stdlib.h>

/*直接插入排序练习*/

/*先定义一个无序数组*/

void InsertSort(int * c,int len);
void Show(int * c,int len);

int main(void){
	int zm[8]={2,5,30,6,11,13,16,15};
	int length=sizeof(zm)/sizeof(zm[0]);
//	printf("数组的长度是%d\n",length);
	InsertSort(zm,length);
	Show(zm,length);
	return 0;
}

void InsertSort(int * c,int len){   //插入排序
	int i,j,temp;
	for(i=1;i<len;i++){
		temp = c[i]; //当前记录先保存下
		j=i-1;
		while(temp<c[j] && j>=0){  //找插入位置
			c[j+1]=c[j];   //记录后移
			j--;
		}
		c[j+1]=temp;   //c[i]插入到正确位置

	}	
}

void Show(int * c,int len){
	int i;
	printf("新的数组是:\n");
	for(i=0;i<len;i++){
		printf("%d,",c[i]);
	}
}

程序执行结果如下：

本文出自 “明镜亦非台” 博客，请务必保留此出处http://kk876435928.blog.51cto.com/3530246/1872419

直接插入排序