執(zhí)行效果
插入排序的執(zhí)行效果是這樣的：

呃……看不懂嗎？沒關(guān)系，接著往下看介紹?

算法介紹
插入排序（Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用原地排序（即只需用到 O(1) 的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。
如果對(duì)插入排序的效率不是很滿意，還可以看下它的改進(jìn)版：希爾排序。

算法檔案
時(shí)間復(fù)雜度：O(n2)
最優(yōu)時(shí)間復(fù)雜度：O(n)
平均時(shí)間復(fù)雜度：O(n2)
空間復(fù)雜度：總共 O(n)，需要輔助空間 O(1)
穩(wěn)定性：穩(wěn)定

算法步驟
從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序

• 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
• 如果該元素（已排序）大于新元素，將該元素移到下一位置
• 重復(fù)步驟 3，直到找到已排序的元素小于或者等于新元素的位置
• 將新元素插入到該位置后
• 重復(fù)步驟 2~5，直到所有元素排序完畢

算法實(shí)現(xiàn)

#include <stdio.h>void insertion_sort(int array[], int length);void insertion_sort(int array[], int length){int i, j, temp;for (i = 1; i < length; i++){temp = array[zxsq-anti-bbcode-i];j = i - 1;for ( ; j >= 0 && array[zxsq-anti-bbcode-j] > temp; j--){array[j+1] = array[zxsq-anti-bbcode-j];}array[j+1] = temp;}
}int main(void)
{int array[] = {73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109};int i, length;length = sizeof(array) / sizeof(array[zxsq-anti-bbcode-0]);insertion_sort(array, length);printf("排序后的結(jié)果是：");for (i = 0; i < length; i++){printf("%d ", array[zxsq-anti-bbcode-i]);}putchar('\n');return 0;
}

程序?qū)崿F(xiàn)如下：