首页 > C语言编程实例 阅读:16,804

C语言直接插入排序算法

插入排序是把一个记录插入到已排序的有序序列中,使整个序列在插入该记录后仍然有序。插入排序中较简单的种方法是直接插入排序,其插入位置的确定方法是将待插入的记录与有序区中的各记录自右向左依次比较其关键字值的大小。本实例要求使用直接插入排序法将数字由小到大进行排序。

实现过程:

(1) 自定义一个函数,实现直接插入排序,在本实例中,我们自定义该函数为 insort()。

(2) main() 函数为程序的入口函数。程序代码如下:
#include <stdio.h>
int insort(int s[], int n)    /* 自定义函数 insort()*/
{
    int i,j;
    for(i=2;i<=n;i++)    //数组下标从2开始,s[0]做监视哨,s[1]一个数据无可比性
    {
        s[0]=s[i];    //给监视哨陚值
        j=i-1;    //确定要比较元素的最右边位黄
        while(s[0]<s[j])
        {
            s[j+1]=s[j];    //数据右移
            j--;    //产移向左边一个未比较的数
        }
        s[j+1]=s[0];    //在确定的位置插入s[i]
    }
    return 0;
}

int main()
{
    int a[11],i;    //定义数组及变量为基木整甩
    printf("请输入10个数据:\n");
    for (i =1;i<=10;i++)
        scanf("%d",&a[i]);    //接收从键盘输入的10个数据到数组a中
    printf("原始顺序:\n");
    for(i=1;i<11;i++)
        printf("%5d",a[i]);    //将未排序前的顺序输出
    insort(a,10);    //调用自定义函数 insort()
    printf("\n 插入数据排序后顺序:\n");
    for(i=1;i<11;i++)
        printf("%5d",a[i]); //将排序后的数组输出
    printf("\n");
    return 0;
}

运行结果:

请输入10个数据:
25 12 36 45 2 9 39 22 98 37
原始顺序:
   25   12   36   45    2    9   39   22   98   37
插入数据排序后顺序:
    2    9   12   22   25   36   37   39   45   98

技术要点:

本实例算法过程如表 1 所示。

原始顺序:25 12 36 45 2 9 39 27 98 37

表1 直接插入排序过程
趟数 监视哨 排序结果
1 25 (12,)25,36,45,2,9,39,22,98,37
2 12 (12,25,)36,45,2,9,39,22,98,37
3 36 (12,25,36,)45,2,9,39,22,98,37
4 45 (12,25,36,45,)2,9,39,22,98,37
5 2 (2,12,25,36,45,)9,39,22,98,37
6 9 (2,9,12,25,36,45,)39,22,98,37
7 39 (2,9,12,25,36,39,45,)22,98,37
8 22 (2,9,12,22,25,36,39,45,)98,37
9 98 (2,9,12,22,25,36,39,45,98,)37
10 37 (2,9,12,22,25,36,37,39,45,98,)

指点迷津:

本算法中使用了监视哨,主要是为了避免数据在后移时丢失。

C语言/C++交流群:664104694(我们会不定期在群内分享编程知识,上传编程资料)

编程帮,一个分享编程知识的公众号。跟着站长一起学习,每天都有进步。

通俗易懂,深入浅出,一篇文章只讲一个知识点。

文章不深奥,不需要钻研,在公交、在地铁、在厕所都可以阅读,随时随地涨姿势。

文章不涉及代码,不烧脑细胞,人人都可以学习。

当你决定关注「编程帮」,你已然超越了90%的程序员!

编程帮二维码
微信扫描二维码关注