数据结构-直接插入排序 （C++代码）

解题思路:





注意事项:





参考代码:

#include <iostream>
#include <iomanip>
// 分类 ------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)
// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
using namespace std;
  void swap(int &x, int &y)
  {
     int temp = x;
      x = y;
       y = temp;
  }
   void insertion(int a[], int sz)
    {
      for(int i=1;i<=sz;i++) {
       int j=i;
        while(j>0&&(a[j]<a[j-1])) {
          swap(a[j],a[j-1]);
           j--;
        }
    }
}
   int main()
     {
       int a[10005],n;
         scanf("%d",&n);
           for(int i=1;i<=n;i++)
             scanf("%d",&a[i]);
               insertion(a,n);
    for(int i=1;i<=n;i++)
     {
        printf("%d ",a[i]);
	 } 
}