插入排序

插入排序

思想

每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

基本信息

1.分类:直接插入排序、二分插入排序
2.特点: 稳定的排序方法(相等数不交换位置)
3.时间复杂度:   
    a.直接插入排序:O(n^2)
    b.二分插入排序:O(n*log2(n) )

具体实现

1
//可在gcc8.2.0版本中通过编译
2
#include<stdio.h>
3
int main()
4
{
5
    const int length = 10;
6
    int a[length] = {9,2,1,5,6,7,8,10,20,3};
7
    for(int i = 1;i < length;i++)
8
    {
9
        int key = a[i];
10
        int j =i-1;
11
        while(a[j] > key && j > 0)
12
        {
13
            a[j+1] = a[j];
14
            j--;
15
        }
16
        a[j+1] = key;
17
    }
18
    for(int i = 0;i < length;i++)printf("%d\t",a[i]);
19
    return 0;
20
}

循环不变式的证明

初始

在第一次迭代之前,即当i=1且没有开始迭代时.对于已经排序好的数组A[0到i-1]即只有一个元素的A[0],当然已经是有序的,故而在初始阶段循环不变式成立。

保持

即当1< i< length 时,此时被排序的数key为a[i],若i的前面一个数大于key( i 前方有序)则将A[0,1,2,…,i-1]即i前方所有比key大的元素往右移动一个位置,直到为key找到合适的位置。此时子数组A[0,…,i]有序。推断出每次迭代将保持循环不变式

终止

for的终止条件为i = length,但是数组下标从0开始,所以a中所有元素的下标其实为0,1,…,length-1. 当i=length时,子数组A[0,…,i]已经由a[0,1,…,length-1]中的元素有序组成。注意到A已经为整个数组,所以判断整个数组有序。

PS

循环不变式的证明只在有必要时(不懒的时候)给出