插入排序
插入排序是一種簡單直觀的排序算法腊满。它的工作原理是通過構建有序序列，對于未排序數(shù)據(jù)捂贿，在已排序序列中從后向前掃描泛释，找到相應位置并插入。插入排序在實現(xiàn)上甚带，通常采用in-place排序（即只需用到O(1)的額外空間的排序）她肯，因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位鹰贵，為最新元素提供插入空間晴氨。
插入排序都采用in-place在數(shù)組上實現(xiàn)，其運作如下：
- 從第一個元素開始碉输，該元素可以認為已經被排序
- 取出下一個元素籽前，在已經排序的元素序列中從中向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復步驟3敷钾，直到找到已排序的元素小于或等于新元素的位置
- 將新元素插入到該位置后
- 重復步驟2~5
使用插入排序為一列數(shù)字進行排序的過程
Insertion-sort-example-300px.gif
#include <stdio.h>
// 插入排序算法
void insertion_sort(int arr[], int len){
int i, j;
int temp;
for (i = 1; i < len; i++) {
temp = arr[i];
// 與已排序的數(shù)逐一比較聚假，當已排序的數(shù)大于temp時，該數(shù)向后移動
for (j = i - 1; j >= 0 && arr[j] > temp; j-- ) { // j循環(huán)到-1時闰非，由于短路求值不會運算array[-1]
arr[j + 1] = arr[j];
arr[j] = temp; // 被排序數(shù)放到正確的位置
}
}
}
int main(int argc, const char * argv[]) {
// 聲明一個int類型的數(shù)組
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
// 計算數(shù)組的長度
int len = (int) sizeof(arr) / sizeof(*arr);
// 插入排序
insertion_sort(arr, len);
// 打印排序后的數(shù)組元素
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
小結
插入排序不適合對于數(shù)據(jù)量比較大的排序應用，適用于少量元素的排序峭范。
