原文地址 http://www.cnblogs.com/liukemng/p/3716164.html

本次介紹排序算法中的插入排序。

1.直接插入排序：

基本思想：

直接插入排序也需要對待排序的序列在外層進行n-1次遍歷，每次遍歷時只把本次遍歷次數處的元素和該元素之前的元素進行比較，來決定插入位置，并把從插入位置開始到該元素之前的所有元素后移，使從序列開始到該元素為止序列中的元素有序，直至遍歷完成序列整體有序，插入排序算法的時間復雜度為O(n2)；

如下表格所示為待排序的序列：

當進行第一次遍歷時把元素e[1]和e[0]作比較，e[1]<e[0]，所以e[1]插入e[0]的位置e[0]元素后移，第一次遍歷后序列中元素排列順序如下：

當進行第二次遍歷時把元素e[2]和e[0]、e[1]作比較，e[2]<e[0]，所以e[2]插入e[0]的位置e[0]、e[1]元素后移，第二次便利后序列中元素排列順序如下：

然后繼續進行遍歷，直至序列遍歷完成…

代碼實現：

/// <summary>/// 直接插入排序/// </summary>/// <param name="intArray"></param>/// <param name="length"></param>public static void InsertSort(int[] intArray, int length){    int i, j, k, temp, insertIndex;    for (i = 1; i < length; i++)    {        insertIndex=0;        temp = intArray[i];        for (j = i - 1; j >= 0; j--)        {            if (temp > intArray[j])            {                insertIndex = j+1;                break;            }        }        if (insertIndex != i)        {            for (k = i; k > insertIndex; k--)            {                intArray[k] = intArray[k - 1];            }            intArray[insertIndex] = temp;        }    }}
2.改進的插入排序算法：
在上面的插入排序算法中，我們先對本次排序中的元素進行循環比較找出插入位置，然后找出插入位置并把從插入位置處的元素進行后移，如果插入的位置不是元素本身的位置就多了元素后移操作，我們可以把元素比較和元素后移操作放在同一個循環中提高效率；
代碼實現：
/// <summary>/// 直接插入排序優化1/// 在比較的同時移動元素/// </summary>/// <param name="intArray"></param>/// <param name="length"></param>public static void InsertSort1(int[] intArray, int length){    int i, j, temp, insertIndex;    for (i = 1; i < length; i++)    {        if (intArray[i] < intArray[i - 1])        {            temp = intArray[i];            insertIndex = i;            for (j = i - 1; j >= 0 && temp < intArray[j]; j--)            {                intArray[j + 1] = intArray[j];                insertIndex = j;            }            intArray[insertIndex] = temp;        }    }}
3.折半插入排序：
基本思想:
折半插入排序外層遍歷與直接插入排序外層遍歷相同，不同的是每次遍歷時把本次遍歷次數處的元素與之前排序好的元素序列中間的元素作比較，如果小于中間的元素則把中間元素的前一個元素作為新的比較序列的末尾元素，待插入元素重新與新序列中間元素比較，如果大于中間元素則把中間元素的后一個元素作為新的比較序列的起始元素，待插入元素重新與新序列中間元素比較，直至新序列開始元素的位置大于結束元素的位置搜索結束，找出插入位置并移動元素，折半插入排序算法的時間復雜度仍為O(n2)，但效率依然比直接插入排序高；
代碼實現：
/// <summary>/// 折半插入算法/// </summary>/// <param name="intArray"></param>/// <param name="length"></param>public static void BinaryInsertSort(int[] intArray, int length){    int i, j, low, high, temp, middle;    for (i = 1; i < length; i++)    {        temp = intArray[i];        low = 0;        high = i - 1;        while (low <= high)        {            middle = (low + high) / 2;            if (temp < intArray[middle])                high = middle - 1;            else                low = middle + 1;        }        if (low != i)        {            for (j = i; j > low; j--)            {                intArray[j] = intArray[j - 1];            }            intArray[low] = temp;        }    }}
以上就是插入排序算法的內容。