插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應(yīng)該是最容易理解的了，因為只要打過撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

插入排序和冒泡排序一樣，也有一種優(yōu)化算法，叫做拆半插入。

（1）步驟

1. 將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當(dāng)成是未排序序列。

2. 從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。）

（2）動圖演示

（3）直接插入排序的特性總結(jié)：

1. 元素集合越接近有序，直接插入排序算法的時間效率越高

2. 時間復(fù)雜度：O(N^2)

3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法

4. 穩(wěn)定性：穩(wěn)定

（4）C語言代碼實現(xiàn)如下：

#include <stdio.h>
#include <stdlib.h>
void InsertSort(int num[],int n)
{
    int i,j,k;
    for(i=1;i<n;i++)//默認(rèn)第一個是有序的
    {
        k=num[i];//獲取無序的元素
        for(j=i-1;j>=0;j--) //在有序隊列中從后往前一個個的比
        {
            if(k>=num[j])//如果k比這個數(shù)大，就放在這個數(shù)的后面
            {
                num[j+1]=k;
                break;
            }
            num[j+1]=num[j];//如果k比這個數(shù)小，那就把這個數(shù)后移
            if(j==0)
                num[0]=k;
        }
    }
}

int main()
{
    int num[5]= {2,3,1,5,4};
    InsertSort(num,5);
    for(int i=0; i<5; i++)
    {
        printf("%d\n",num[i]);
    }
    return 0;
}

如果我們編譯并運行上述程序，那么它應(yīng)該產(chǎn)生以下結(jié)果：

1
2
3
4
5