直接插入排序

直接插入排序

时间： 1ms        内存：128M

描述：

设计一个程序，实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。

输入：

输出：

每个排序过程输出一行，直到排序完成。

示例输入：

示例输出：

9 8 7 6 5 4 3 2 1 0
8 9 7 6 5 4 3 2 1 0
...
...

提示：

参考答案（内存最优[0]）：

#include <iostream>
using namespace std;
void display(int a[],int n)
{
    for(int i=0;i<n;i++)
    {
        cout<<a[i];
        if(i!=n-1)cout<<' ';
    }
    cout<<endl;
}
void InsertSort(int a[],int n)
{
    int i,j,temp;
    for(i=1;i<n;i++)
    {
        temp=a[i];
        j=i-1;
        while(j>=0&&temp<a[j])
        {
            a[j+1]=a[j];
            j-=1;
        }
        a[j+1]=temp;
        display(a,10);
    }
}
int main()
{
    int a[11]={9,8,7,6,5,4,3,2,1,0};
    int n=10;
    display(a,n);
    InsertSort(a,n);
    return 0;
}

参考答案（时间最优[0]）：

#include<iostream>
using namespace std;
int main()
{
    int a[]= {9,8,7,6,5,4,3,2,1,0};
    int k=sizeof(a)/sizeof(a[0]);
    int j;
    for(int f=0; f<k-1; f++)
    {
        cout<<a[f]<<" ";
    }
    cout<<a[k-1]<<endl;
    for(int i=1; i<k; i++) //循环从第2个元素开始
    {
        int temp=a[i];
        j=i-1;
        while(j>=0&&temp<a[j])
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=temp;//此处就是a[j+1]=temp;
        for(int f=0; f<k-1; f++)
        {
            cout<<a[f]<<" ";
        }
        cout<<a[k-1]<<endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。