Insertion Sort 插入排序

来一个直观的图解释插入排序（图来自 Insertion Sort）：

也就是整个序列元素递归，每个元素都从当前位置递归到第二个元素，递归过程中每个当前位置都和前一位置比较，然后决定是否调换处理，以下都是升序处理。

伪代码（Pesudocode）如下，来自 Insertion Sort：

for i ← 1 to length(A) - 1
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

C 版本如下：

#include <stdio.h>

void swap(int* a, int* b);
void insertionSort(int arr[], int length);

int main(void)
{
    int arr[3] = {3, 1, 2};
    insertionSort(arr, 3);

    int i;
    for (i = 0; i < 3; i++)
        printf("%d ", arr[i]);

    return 0;
}

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void insertionSort(int arr[], int length)
{
    int i, j;
    for (i = 1; i < length + 1; i++)
            for (j = i; j > 0 &amp;&amp; arr[j] < arr[j - 1]; j--)
            swap(&amp;arr[j], &amp;arr[j - 1]);
}

---

一个关于部分排序算法的 Gist: