插入排序

思想

直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

设数组为a[0…n-1]。

1. 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1

2. 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。

3. i++并重复第二步直到i==n-1。排序完成。

在查找某元素应该插入到前面有序序列的位置时，我们可以采用边交换边插入的方式，直到无需交换

代码

void InsertSort(int a[],int len) {
    for (int i = 1; i < len; i++) {
        //查找应该插入的位置
        for (int j = i; j > 0; j--){
            if (a[j - 1] > a[j]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
            else
                break;
        }
    }
}

其中交换元素部分可以调用STL中的swap函数实现

//插入排序
void InsertSort(int a[],int len) {
    for (int i = 1; i < len; i++) {
        //查找应该插入的位置
        for (int j = i; j > 0; j--){
            if (a[j - 1] > a[j]) {
                swap(a[j], a[j - 1]);
            }
            else
                break;
        }
    }
}

时间复杂度

$O(n^2)$