insertsort.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <iostream.h>
#include <stdlib.h>                    //其中定义随机数函数

void output(int table[],int n)         //输出数组的n个元素
{
    cout<<"  table:  ";
    for(int i=0;i<n;i++)
        cout<<table[i]<<"  ";
    cout<<endl;
}

void insertsort(int table[],int n)     //n个随机数直接插入排序
{                                      //已排序数据存放在table数组
//    randomize();                     //初始化随机数序列
    for(int i=0;i<n;i++)               //n-1趟排序，依次插入n-1个数
    {
        int k=rand() % 20;             //产生一个0~20之间的随机数
        cout<<"k="<<k<<"\t  ";
        int j=0;
        while(j<i && k>=table[j])      //顺序查找k值应在的位置
            j++;
        cout<<"j="<<j;
        for(int h=i-1;h>=j;h--)        //移动元素
            table[h+1]=table[h];       //将元素table[h]向后移
        table[j]=k;                    //k值应放入table[j]
        output(table,n);               //输出数组的n个元素
    }
}

void main()
{
    const int N=8;
    int a[N]={0};
    insertsort(a,N);
}
/*程序运行结果 ：
k=11  j=0  table:  11  0  0  0  0  0  0  0  
k=19  j=1  table:  11  19  0  0  0  0  0  0  
k=9   j=0  table:  9  11  19  0  0  0  0  0  
k=5   j=0  table:  5  9  11  19  0  0  0  0  
k=5   j=1  table:  5  5  9  11  19  0  0  0  
k=1   j=0  table:  1  5  5  9  11  19  0  0  
k=4   j=1  table:  1  4  5  5  9  11  19  0  
k=15  j=6  table:  1  4  5  5  9  11  15  19  
*/