直接插入排序代码

思想：

两轮遍历：
- 第一轮，从第二个元素开始遍历到最后一个元素，让他们跟他们自己前面的元素比较大小，让他们回到正确的位置。
- 第二轮，实现比较大小功能，如果前面比他小，就交换位置，然后再继续向前遍历，直到已经走到最前面（j==0）或者前面的元素已经比他小了，就停止。

时间复杂度

- 最好时间复杂度：O(n) 序列的前面已经是有序的情况
- 平均时间复杂度：O(n^2) 
- 最差时间复杂度：O(n^2)  倒序

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n,q[N];

void InsertSort()
{
    for(int i = 1; i < n; i++)
    {
       int t = q[i]; int j = i;
       while( j && q[j-1] > t)
       {
           q[j] = q[j-1];
           j--;
       }
       q[j] = t;
    }
}


int main(){
    cin >> n;
    for(int i = 0 ; i < n;i++) cin >> q[i]; //读取

    InsertSort();

    for(int i = 0 ; i < n;i++) cout <<  q[i] <<' ';

    return 0;
}