排序算法——插入排序

一、算法思想

        参考《算法导论第三版》，插入排序对于少量元素的排序是一个有效的算法。其思想比较简单，就像我们打扑克接牌一样。其大致过程为：从第二个元素开始与其前面的元素进行比较，找到它应该在的位置后把该值插入其中，然后从下一个元素开始重复操作，以此类推，向后遍历一遍便可以得到一组有序数列。

二、代码实现

#include<iostream>
using namespace std;

int a[10000],n;
void insertsort()
{
    for(int j=2;j<=n;j++)
    {
        int key=a[j];
        int i=j-1;
        while(key<a[i]&&i>0)
        {
            a[i+1]=a[i];
            i--;
        }
        a[i+1]=key;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    insertsort();
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }

}

三、算法分析

        算法的时间复杂度最好为n，最坏为n*n，平均为n*n。是一种稳定（相同元素排序后的位置是否与原来保持一致）的排序算法。

四、其他排序算法

        排序算法之快速排序     排序算法之堆排序     排序算法之归并排序