1. 概念
將當(dāng)前元素插入到已經(jīng)有序的數(shù)組中適當(dāng)?shù)奈恢谩?/p>
2. 實(shí)現(xiàn)流程
- 從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個元素萎河，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素荔泳，將該元素移到下一位置
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟2~5
3.算法圖解
插入排序
插入排序
4.代碼實(shí)現(xiàn)
void insertion_sort(int arr[],int len) {
int i,j;
int temp;
for (i = 0 ; i < len ; i ++) {
temp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = temp;
}
}
5.時間復(fù)雜度
最差時間復(fù)雜度 O( n^2 )
最優(yōu)時間復(fù)雜度 O( n )
平均時間復(fù)雜度 O( n^2 )
最差空間復(fù)雜度 O( n ),需要輔助空間O(1)
如果原始序列是I的虐杯，插入排序的效果是非常好的玛歌。
