插入排序

算法

• 将整个数组a分为有序的部分和无序的部分。前者在左边，后者在右边
• 开始有序的部分只有 a[0] ，其余都属于无序的部分
• 每次取出无序部分的第一个（最左边）元素，把它加入到有序部分。假设插入到合适位置p，则原p位置及其后面的有序部分元素，都向后移动一个位子。有序的部分即增加了一个元素。
• 直到无序部分没有元素

代码实现

xxxxxxxxxx
void InsertionSort(int a[], int size)
{
    // a[i] 是最左的无序元素，每次循环将a[i]放入到合适位置
    for (int i = 1; i < size; i++) {
        // 在有序部分找插入位置
        for (int j = 0; j < i; j++) {
            if (a[j] > a[i]) {
                // 要把a[i] 放到位置j，原下标j到i-1的元素都要往后移一个位置
                int tmp = a[i];
                for (int k = i; k > j; k--) {
                    a[k] = a[k-1];
                }
                a[j] = tmp;
                break;
            }
        }
    }
}

效率

$O(n^2)$