1.直接插入排序
时间复杂度：
最好情况：o(n)
平均情况：o(n^2)
最坏情况：o(n^2)
稳定排序：相等的元素，不会交换顺序。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 100010;

int n;
int q[N];

void insert_sort()
{
    for(int i=1;i<n;i++) //i = 1，从第二个数开始比较
    {
        int t = q[i], j = i;
        while(j && q[j-1]>t)//j >0 如果第1个数大于第2个数
        {
            q[j]= q[j-1];//就将第1个数得值赋给第2个数
            j--;
        }
        q[j] = t;// j--  第二个数的值给第一个数
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 0;i<n;i++)
    scanf("%d",&q[i]);
    insert_sort();
    for(int i = 0;i<n;i++) printf("%d ",q[i]);
    return 0;
}

2 .折半插入排序

void binary_search_insert_sort()
{
    for(int i = 1; i<n ;i ++ )
    {
        if(q[i-1]<q[i]) continue;  //如果是按从小到大排列，直接退出
        int t = q[i];
        int l= 0,r = i-1;
        while(l < r)  //否则找到第一个比当前元素大的元素，二分查找
        {
            int mid = l+r >>1;
            if(q[mid]>t) r= mid;
            else l =mid +1;
        }
        for(int j = i-1;j>=r;j--)
        {
            q[j+1] = q[j]; //从r到 i-1向后移动一位，把当前数据移到r处
        }
        q[r] = t;
    }
}

3.冒泡排序
/时间复杂度：
最好情况：o(n)
平均情况：o(n^2)
最坏情况：o(n^2) //两重循环
空间复杂度：o(1)
稳定性：稳定
/
冒泡排序：第一次将最小的元素冒到开头，第二次第二小的元素到开头，执行n-1次。
每次迭代，判断，第一次操作，如果后一个元素比前一个元素小的话，交换两个元素。将后面的n-个子数组进行排序。
优化：如果没有一次交换的话，说明是按照从从小到到的排序。

void bubble_sort()
{
    for(int i =0;i<n;i++)
    {
        bool has_swap = false;
        for(int j = n-1;j>i;j--)
        {
            if(q[j]<q[j-1])
            {
                swap(q[j],q[j-1]);
                bool has_swap = true;
            }
        }
        if(has_swap) break;
    }
}

4.选择排序
选择排序：第一次找到最小的元素，第二次找到第二小的元素，迭代，类似于冒泡排序

void select_sort() //简单选择排序,最慢的排序。
{
    for(int i = 0;i<n - 1;i++)
    {
        int k = i; //每次的最小元素
        for(int j = i+1;j<n;j++)
        {
            if(q[j]<q[k])
            {
                k = j;
            }
        }
        swap(q[i],q[k]);
    }
}