1、直接插入排序：
算法思路：

1. 某个序列L[0,1,....,i-1]有序，将L[i]插入到前面序列合适的位置，后面元素以此类推；
   2.初始情况只有L[0]一个元素 ，默认有序；

void insert_sort(int n)
{
    for(int i=1;i<n;i++)
    {
        int tmp = a[i];
        int j = i-1;
        for(;j>=0 && a[j]>tmp;j--)
        {
            a[j+1] = a[j];
        }
        a[j+1] = tmp;
    }

}

2、折半插入排序：

void insert_sort(int n)
{
    for(int i=1;i<n;i++)
    {
        int tmp = a[i];
        int l=0,r=i-1;
        while(l<r)      //注意这个判断，如果是初始情况，即有序部分只有1个元素的时候，不会进入这个循环，所以下面要加一个if特判 
        {
            int mid = l+r>>1;
            if(a[mid] > tmp) r = mid;
            else l = mid+1; 
        }
        if(a[i]<a[i-1])
        {
            int j;
            for(j=i;j>l;j--) a[j] = a[j-1];

            a[l] = tmp;
        }

    }

}

3、冒泡排序：

void bubble_sort(int n)
{
    for(int i=0;i<n;i++)
    {
        bool flag = false;
        for(int j=n-1;j>i;j--)
        {
            if(a[j] < a[j-1]) swap(a[j],a[j-1]),flag = true; 
        }
        if(flag == false) return;       //如果此次冒泡，没有交换，说明以及有序，无需进行下去 
    }
}

4、快速排序：

void quick_sort(int l,int r)
{
    if(l>=r) return;
    int x = a[l+r>>1],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]); 
    }

    quick_sort(l,j);
    quick_sort(j+1,r);
}

5、归并排序：

void merge_sort(int l,int r)
{
    if(l>=r) return;

    int mid = l+r>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);

    int i=l,j=mid+1,k=0;
    while(i<=mid && j<=r)
    {
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }

    while(i<=mid) tmp[k++] = a[i++];
    while(j<=r) tmp[k++] = a[j++];

    for(int i=l,j=0;i<=r;i++,j++) a[i] = tmp[j];
}

6、简单选择排序：

void select_sort(int n)
{
    for(int i=0;i<n;i++)
    {
        int min = i;
        for(int j=i+1;j<n;j++)
        {
            if(a[j] < a[min]) min = j;
        }
        swap(a[i],a[min]);
    }
}

7、希尔排序：
希尔排序代码上，相比于插入排序只多了一个gap循环

void shell_sort(int n)
{
    for(int gap = n/2;gap>=1;gap /= 2)
    {
        for(int i=gap;i<n;i++)
        {
            int j,tmp = a[i];
            for(j=i-gap;j>=0 && a[j]>tmp;j -= gap)
            {
                a[j+gap] = a[j];
            }
            a[j+gap] = tmp;
        }
    }
}