插入排序的基本思想是每步将一个待排序的记录按其关键字值的大小,插到前面已经排好的文件中的适当位置,直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。
接插入排序的过程为:在插入第i个记录时,R1,R2,..Ri-1已经排好序,将第i个记录的关键字Ki依次和R1,R2,..,Ri-1的关键字逐个进行比较,找到适当的位置。使用直接插入排序,对于具有n个记录的文件,要进行n-1趟排序。直接插入排序是稳定的算法,文章给出用C语言实现的插入排序算法的源代码,在Vc++6.0环境中调试通过,并提供下载源码文本。
源码下载:插入排序VC++6.0源码 insertSort.cpp
代码如下:
// insertSort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
void Dir_Insert(int A[],int N) //直接插入排序
{
int j,t;
for(int i=1;i<N;i++)
{
t=A[i];
j=i-1;
while(A[j]>t)
{
A[j+1]=A[j];
j--;
}
A[j+1]=t;
}
}
int main(int argc, char* argv[])
{
int i,k,n;
n=6;
int array[6];
printf("insert sort algorithom ,array N=6 : ");
for(i=0;i<n;i++)
{
printf("please input array[%d] value: ",i);
scanf("%d",&k);
array[i]=k;
}
//打印排序前内容
printf("current array value: ");
for(i=0;i<n;i++)
{
printf("%d ",array[i]);
}
printf(" ");
//排序
Dir_Insert(array,n) ;
//打印排序后内容
printf("sorted array value: ");
for(i=0;i<n;i++)
{
printf("%d ",array[i]);
}
printf(" ");
return 0;
}
文章参考:http://www.programfan.com/club/showtxt.asp?id=202195