直接插入排序

直接插入排序

基本思想:假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区。

代码实现:

#include<stdio.h>
#include<iostream>
using namespace std;
int n;
void InsertSort(int a[])
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        if(a[i]<a[i-1])
        {
            a[0]=a[i];    //哨兵
            a[i]=a[i-1];
            for(j=i-2;a[0]<a[j];j--)
                a[j+1]=a[j];        //后移
            a[j+1]=a[0];
        }
    }
}

int main ()
{
    int a[100],i;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    InsertSort(a);
    for(i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}



郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。