简单选择排序

#include <iostream>
#include<cstdio>

using namespace std;

int main()
{
    int a[100],n,i,j,k;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=2;i<=n;i++)
    {
        if(a[i]<a[i-1])
        {
            a[0]=a[i];
            for(j=i-1;a[j]>a[0];j--)
            {
                a[j+1]=a[j];
            }
            a[j+1]=a[0];
        }
        for(k=1;k<=n;k++)
            cout<<a[k]<<" ";
        printf("\n");
    }
    return 0;


}

对于这个排序，其实就是从第二个开始比较，自身与前一个比较，如果比前一个小，便进行循环，在前方找位置，通过不断向移动位置，直到找到不比自身小的元素，即停止，这个被比较元素的下一个位置即为该元素的位置。

对于时间复杂度的分析，最好的情况即已经是顺序的情况，无需再移动，那么仅仅需要进行n-1次比较，最坏的情况下，便是逆序的情况，需要进行n*n/2的比较及n*n/2移动，综合来说，时间复杂度便是n*n,空间需要一个额外的空间。