插入排序

插入排序

平均时间复杂度：O($n^2$)

最好时间复杂度：O(n)

最坏时间复杂度：O($n^2$)

稳定性：稳定

将第一个元素设置为有序区，将后面的每个数插入到前面的有序区之内，形同打扑克牌时摸牌插入到手中牌堆内。

void insertion_sort(int arr[], int len){  //两个重要参数
        int i,j,key;
        for (i=1;i<len;i++){   
                key = arr[i];  //这里的key就是中间变量，意味着待处理元素
                j=i-1;         //前移一位
                while((j>=0) && (arr[j]>key)) {  
                        arr[j+1] = arr[j];   //这三行代码完成了交换
                        j--;                 //j--表示比较的移动，逐渐移动到arr[0]
                }
                arr[j+1] = key;    //如果while不执行，这句相当于什么都不做
        }

针对有序区处理的顺序

使用插入将数组元素从小到大排序，在将待处理元素与有序区比较时，强烈建议从后往前（即从有序区的大数到小数的顺序来比较）排序，因为这样只需要移动比待处理元素大的元素，一旦找到位置就可以直接插入。

比如{1,3,5,7}待处理元素为4，在比较5，7之后移动了2个元素，再把4插入3后面即可。

但如果是反着来，可能会对已经比较过的元素进行多次移动操作，尤其是当待插入元素较小，需要移动的元素较多时，效率相对较低。

然而这也不是绝对的，但从大到小是通常情况下的最优解。