插入排序及其简单优化

插入排序是稳定的排序方法，时间复杂度是O(n^2)
最坏情况（完全逆序的情况）O(n^2), 最好情况（完全顺序的情况）O(n),平均情况O(n^2),

所以十分适用于基本有序的数组

直接插入排序

    void Insert_Sort(int *a,int n)
    {
        int i,j;
        for(i=1; i<n; i++)
        {
            if(a[i]<a[i-1])
            {
                int t=a[i];
                for(j=i-1; j>=0&&a[j]>t; j--)
                {
                    a[j+1]=a[j];
                }
                a[j+1]=t;
            }
        }
    }

二分优化

二分优化指的是通过二分查找的方式快速找到需要插入的位置，但是插入的方式还是需要一个个的移动元素，所以优化的只是少一些比较元素大小的步骤

    //二分优化
    void Insert_Sort_Binary(int *a,int n)
    {
        for(int i=1; i<n; i++)
        {
            if(a[i]<a[i-1])
            {
                int left=0;
                int right=i-1;
                int t=a[i];
                // 利用二分查找的方法快速找到应该插入的位置，可以少进行一些比较，但是需要进行的移动次数还是一样的，所以优化的效果还是有限的
                while(left<=right)
                {
                    int mid=(left+right) / 2;
                    if(a[mid]>t)
                        right=mid-1;
                    else
                        left=mid+1;
                }
                for(int j=i-1; j>=left; j--)
                {
                    a[j+1]=a[j];
                }
                a[left]=t;
            }
        }
    }

插入排序的另一种优化就是希尔排序