直接插入排序(InsertSort)
每次插入一個新的待排序數(shù)到已排序序列中轿腺，注意此時從后往前比較锦聊，更節(jié)省時間梗劫。
舉例
原始序列： 49, 38, 65, 13, 27
- 一開始只看49,則單個數(shù)字肯定是有序的
{49} / 38, 65, 13, 27
- 此時插入38享甸， 由于38<45， 故45向后移動梳侨， 38插入到49原來的位置
{38, 49} / 65, 13, 27
- 此時插入65, 從后向前進行比較蛉威，49<65， 故65直接插入到49之后
{38, 49, 65} / 13, 27
- 此時插入13走哺，從后向前進行比較蚯嫌，一直到38>13，這趟排序后的結(jié)果為：
{13, 38, 49, 65} / 27
- 此時插入27丙躏，從后向前進行比較择示，發(fā)現(xiàn)該插入到13之后，38之前
{13, 27, 38, 49, 65}
代碼：
#include <iostream>
using namespace std;
void InsertSort(int array[], int n) {
int i, j, temp;
for (i = 1; i < n; ++i) {
temp = array[i];
j = i - 1;
while (j >= 0 && temp < array[j]) {
array[j+1] = array[j];
--j;
}
array[j+1] = temp;
}
}
void print_array(int array[], int n) {
for (int i = 0; i < n; ++i)
cout<<array[i]<<" ";
cout<<endl;
}
int main() {
int array[] = {49, 38, 65, 13, 27};
print_array(array, 5);
InsertSort(array, 5);
print_array(array, 5);
return 0;
}
復(fù)雜度分析
1. 時間復(fù)雜度：
最壞情況晒旅，整個原始序列是逆序的栅盲，則內(nèi)層循環(huán)temp<array[i]每次都成立，則時間復(fù)雜度為O(n^2).
最好情況废恋，整個原始序列原本就是按序排列的谈秫，則內(nèi)存循環(huán)條件不滿足扒寄，時間復(fù)雜度為O(n).
綜合來看，時間復(fù)雜度為O(N^2).
2. 空間復(fù)雜度：
只需要一個temp拟烫，并不隨著待排序列的規(guī)模而變化该编，因此空間復(fù)雜度為O(1).
