直接插入

72 阅读 0 评论 48 点赞

我是靠谱客的博主怕黑早晨，最近开发中收集的这篇文章主要介绍直接插入，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思想：对已排好序的数组从头开始扫一遍，以升序为例，若遇到插入的数k大于等于a[i]并且小于等于a[i+1]，跳出扫的循环，
      新一次循环从i+1开始扫起，判定条件修改为要小于n+1(因为相当于数组多了个元素)，循环体里实现数值交换

解题代码：
#include <stdio.h>
#define N 100000
void Input(int a[],int n)
{
    int i;
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
}

void Maopao(int a[],int n)
{
    int i,j,temp;
    for(i=0;i<n-1;i++)
    {
        for(j=1;j<n;j++)
        {
            if(a[i]>a[j])    //升序选择
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
}

void Charu(int a[],int n,int k)    //直接插入
{
    int i,j,temp;
    for(i=0;i<n;i++)
    {
        if(a[i]<=k&&a[i+1]>=k)
        {
            break;
        }
    }
    for(j=i+1;j<n+1;j++)
    {
        temp=a[j];
        a[j]=k;
        k=temp;
    }
}

void Output(int a[],int n)
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
}

int main()
{
    int a[N],n,k;
    printf("请输入数据个数：n");
    scanf("%d",&n);
    Input(a,n);
    Maopao(a,n);
    Output(a,n);
    printf("n请输入插入的数据：n");
    scanf("%d",&k);
    Charu(a,n,k);

    Output(a,n+1);
    return 0;
}