[TOC] ## 概述 插入排序(InsertionSort)，一般也被稱為直接插入排序。 對于少量元素的排序，它是一個有效的算法。插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到已經排好序的有序表中，從而一個新的、記錄數增 1 的有序表。在其實現過程使用雙層循環，外層循環對除了第一個元素之外的所有元素，內層循環對當前元素前面有序表進行待插入位置查找，并進行移動。 * 基本思想：每一步將一個待排序的數據插入到前面已經排好序的有序序列中，直到插完所有元素為止。 * 插入排序的**平均時間復雜度**也是 `O(n^2)`，**空間復雜度**為`常數階 O(1)`，具體時間復雜度和數組的有序性也是有關聯的。 * 插入排序中，當待排序數組是有序時，是最優的情況，只需當前數跟前一個數比較一下就可以了，這時一共需要比較 `N-1 `次，時間復雜度為 `O(N)`。最壞的情況是待排序數組是逆序的，此時需要比較次數最多，最壞的情況是 `O(n^2)`。 ## C++代碼 ```cpp //插入排序 void insertSort(int *a, int len) { for (int i = 1; i < len; i++) { int j; int x = a[i]; //每趟將a[i]插入到前面的排序子序列中 for (j = i-1; j >= 0 && x < a[j]; j--) { a[j+1] = a[j]; //將前面較大的元素向后移動 } a[j+1] = x; //x值到達插入位置 } } int main() { int a[] = {4,1, 2, 3, 5,7, 6}; xzSort(a, 7); insertSort(a, 7); } ```