算 法：插入排序算法
時間復雜度：
- 插入排序算法描述
- 插入排序偽代碼
- 插入排序?qū)崿F(xiàn)
插入排序算法概述
插入排序的原理是構建有序序列，對于給定的一個無序序列，從前往后遍歷，在該元素之前的序列中從后往前掃描，尋找正確位置，這樣對于每一個正在排序的元素，前面的序列總是有序的，當遍歷完整個序列，即完成排序。《算法導論》給了一個更通俗更容易理解的形象的描述。我們都玩過撲克牌，大多數(shù)人拿撲克牌的時候都有這么個習慣，那就是將撲克牌按照一定的順序排列好，而插入排序就好比你不斷從桌上一堆無序排中拿起最上面的那張，然后放入自己手中已有的牌中，而每一次放的過程你都會按照某個順序?qū)⑦@張新拿到的牌插入正確的位置，這樣你手中的牌一直是有序的，而你抽取牌所在的牌堆是無序的。
算法描述
下面以非降序排序為例：
- 從第一個元素開始，該元素視為已經(jīng)被排序；
- 取出下一個元素記為
key，在前面已排序的有序序列中從后往前掃描； - 如果掃描過程中的元素大于
key，將該元素移至下一個位置； - 重復3，直至找到已排序的元素小于或等于
key的位置； - 將
key插入到該位置； - 重復2-5，直到整個序列遍歷完即得到一個原地排序好的序列。
執(zhí)行過程圖解
以斜體數(shù)字如 1表示key，以粗體數(shù)字如 ‘1’ 表示已排序序列，為了更直觀，用中括號括起來，普通數(shù)字如‘1’表示未排序亂序序列，簡要表示排序流程如下：
- 5 2 4 6 1 3
- [5] 2 4 6 1 3
- [2 5] 4 6 1 3
- [2 4 5] 6 1 3
- [2 4 5 6] 1 3
- [1 2 4 5 6] 3
- [1 2 3 4 5 6]
插入排序偽代碼
（偽代碼引用《算法導論》給出的例子）
INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
// Insert A[j] into the sorted sequence A[1..j - 1].
i = j - 1
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key
插入排序?qū)崿F(xiàn)
為了更直觀，我們將所有元素從1號元素開始計數(shù)，將0號元素視為無窮小，即數(shù)組長度為arrLength + 1，序列存儲于arr[1..arrLength]。
C
void insertionSort(arrType* arr, int arrLength)
{
int i, j;
arrType key;
for (j = 2; j <= arrLength; j++) {
key = arr[j];
i = j - 1;
while (i > 0 && arr[i] > key) {
arr[i + 1] = arr[i];
i--;
}
arr[i + 1] = key;
}
}
Pascal
procedure insertsort;
var
i,j,key:integer;
begin
arr[0] := -maxint;
for j := 2 to n do
begin
i := j - 1;
key := arr[j];
while arr[i] > key do
begin
arr[i + 1] := arr[i];
i := i - 1;
end;
arr[i + 1] := key;
end;
end;
參考資料
- 《算法導論》（原書第3版)
- 《Free Pascal 語言與基礎算法》
- 插入排序-維基百科，自由的百科全書
本文首發(fā)于個人博客算法 - 插入排序 | 不存在的貓， 轉(zhuǎn)載請注明出處
