插入排序

将一个元素插入到已排序的数组中,使得插入之后的数组也是有序的。插入排序从左到右插入每个元素,每次插入之后左部的子数组是有序的。


/*
插入过程采用两种实现,一种是反复交换相邻项,另一种是传统的移动插入
理论上采用第二种操作方式应该会快一些,但这种差别也可能被编译器优化掉变得微乎其微
*/

class Insertion
{
public:
    vector<int>& sort(vector<int>& array)
    {
        int len = array.size();
        for (int i = 1; i < len; i++)
        {
            for (int j = i; j>0 && array[j] < array[j-1];)
            {
                int t = array[j];
                array[j] = array[j - 1];
                array[j - 1] = t;
                j--;
            }
        }
        return array;

    }
    vector<int>& sort_1(vector<int>& array)
    {
        int len = array.size();
        for (int i = 1; i < len; i++)
        {
            int temp = array[i];
            int j;
            for (j = i; j>0 && temp < array[j-1];)
            {
                array[j] = array[j - 1];
                j--;
            }
            array[j] = temp;
        }
        return array;
    }
};

插入排序的复杂度取决于数组的初始顺序,如果数组已经部分有序了,那么插入排序会很快。平均情况下插入排序需要 ~N2/4 比较以及 ~N2/4 次交换,最坏的情况下需要 ~N2/2 比较以及 ~N2/2 次交换,最坏的情况是数组是逆序的;而最好的情况下需要 N-1 次比较和 0 次交换,最好的情况就是数组已经有序了。

插入排序对于部分有序数组和小规模数组特别高效。

选择排序和插入排序的比较

对于随机排序的无重复主键的数组,插入排序和选择排序的运行时间是平方级别的,两者之比是一个较小的常数。