[数据结构与算法]插入排序(Insertion Sort)

插入排序

排序过程如上，其实这种排序就是我们打扑克牌时使用的排序方式

代码Implement

写一个插入排序的函数，即输入一个数组，完成排序

#include<stdio.h>
#define N 10//数组的长度
void insert_sort(int a[],int n);

int main()
{
    //输入数组
    int array[LENGTH]={0};
    printf("请连续输入10个整数：");
    for(int i=0;i<LENGTH;i++)
    {
        scanf("%d",&array[i]);
    }

    //插入排序
    insert_sort(array,LENGTH);

    //排序后的display
    printf("排序后：");
    for(int i=0;i<LENGTH;i++)
    {
        printf("%d ",array[i]);
    }
    printf("\n");
}
void insert_sort(int a[],int len)
{
    int i,j,temp,key;
    for(i=1;i<len;i++)
    {
        key=a[i];//保留要插入的目标的数值到key中
        for(j=i-1;j>=0;j--)
        {
            if(key<a[j])
            {
                a[j+1]=a[j];
            }
            else break;
        }
        a[j+1]=key;
    }
}

一开始的错误做法：

void insert_sort(int a[],int n)
{
    int i,j,temp;
    for(i=1;i<n;i++)
    {
        //key=a[i]; //真正要插入的目标值的位置是不断在变化的，不是永远都是i，所以用a[i]比对一定是错误的
        for(j=i-1;j>=0;j--)
        {
            if(a[i]<a[j])//用保存下来的key值进行比对才是真正的做法
            {
                temp=a[i];a[i]=a[j];a[j]=temp;
            }
            else break;
        }
    }
}