技术笔试面试

直接插入排序-最简单的排序算法

直接插入排序(Straight Insertion Sort)是最简单的一种排序方法,它的基本操作是:将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。

一般情况下,第 i 趟直接插入排序的操作是:在含有 i-1 个记录的有序子序列 r[1..i-1]中插入一个记录r[i]后,变成含有 i 个记录的有序子序列 r[1..i]。

整个排序过程为进行n-1趟插入,即,先将序列中的第1个记录看成是一个有序的子序列,然后从第2个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止。

为了在查找插入位置的过程中避免数组下标出界,在r[0]处设置监视哨。

直接插入排序的源代码如下:

[rocrocket@wupengchong Sort_Method]$ cat Straight_Insertion_Sort.c
#include
#include
#include

void si_sort(int arr[],int arrnum)
{
int i,j;
for(i=2;i<=arrnum;i++){
if(arr[i] < arr[i-1]){
arr[0]=arr[i];
arr[i]=arr[i-1];
for(j=i-2;arr[j]>arr[0];j--){
arr[j+1]=arr[j];
}
arr[j+1]=arr[0];
}
}
}

void print_arr(int arr[],int arrnum){
int i=1;
printf("Sorted:");
for(;i<=arrnum;i++){
printf("%d ",arr[i]);
}
}

int main()
{
int index=1,arrnum;
char s[100],*sp;
int num[10]={0};
printf("Please input(ex:3 5 6 1 7 14):");
fgets(s,sizeof(s),stdin);
sp=strtok(s," ");
while(sp!=NULL){
printf("%s",sp);
num[index++]=atoi(sp);
sp=strtok(NULL," ");
}
arrnum=index-1;
printf("%d\n",arrnum);
si_sort(num,arrnum);
print_arr(num,arrnum);
return 0;
}

over~

发表您的评论

请您放心,您的信息会被严格保密。必填项已标识 *