算法分析

题目

对于数组A[0…n-1]，用插入法实现非降序排序

实验原理

首先新建一个空列表，用于保存已经排序的有序序列，再从原序列中取出一个数，将其插入有序的列表中，重复操作，直至原数列为空

实验代码

#include <stdio.h>
#include <stdlib.h>

int main()
{
    void InsertSort(int[],int);
    int a[7]={5,9,4,7,3,1,2};
    int i;
    InsertSort(a,7);
    for(i=0;i<7;i++)
        printf("%3d",a[i]);
    getch();
}
void InsertSort(int a[],int count)
{
    int i,j,temp;
    for(i=1;i<count;i++)
    {
        temp=a[i];
        j=i-1;
        while(a[j]>temp&&j>=0)
        {
            a[j+1]=a[j];
            j--;
        }
        if(j!=(i-1))
            a[j+1]=temp;
    }
}

实验截图

算法分析

时间复杂度为平方级，效率不高，但很容易实现

总结

插入法算法简单，很容易做出，后续发出冒泡法和快速排序法，自行对比 ——小明同学