Insertion Sort

插入排序，将被排序序列分为两个序列，一个是已经排序好的有序序列, 一个是未经排序的无序序列, 在排序的过程中，每次取一个无序序列元素到插入到有序序列中适当位置，直到所有无序序列元素插入到有序序列中去。

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "dbg.h"
using namespace std;

void insertSort(int R[], int len)
{
    int temp;
    // 初始将index = 0的值默认为有序序列
    for (int i = 1; i < len; i++)
    {
        temp = R[i];
        int j = i - 1; // 有序序列最后一个元素
        while (j >= 0 && temp < R[j])
        {
            R[j + 1] = R[j]; // 后移
            j--;
        }
        R[j + 1] = temp;
    }
}

int main(int argc, char *argv[])
{
    int R[] = {1, 3, 2, 18, 3, 28, 23, 38, 7, 8};
    cout << "Before sorting: " << endl;
    dbg(R);
    int len = sizeof(R) / sizeof(R[0]);
    cout << "After sorting : " << endl;
    insertSort(R, len);
    dbg(R);
    return 0;
}

运行结果:

最坏情况：整个序列为逆序

• 内层循环temp < R[j]始终成立
• 时间复杂度: O(n²)

最好情况：整个序列为有序

• 内层循环temp < R[j]始终不成立,退化为单层循环
• 时间复杂度: O(n)