#include <iostream>

/* 插入排序

 基本思想：将记录插入到已排序好的有序表中

 特点：一种稳定的排序方法，时间复杂度O(n^2)

 */

void InsertSort(int array[],int len){

    int i,j;

    int temp;

    for (i =1; i < len; i++) {        // i：1 ~ <len(i++)

        temp = array[i];

        for (j = i -1; j >=0; j--) { // j：i-1 ~ >=0(j--)

            if (temp < array[j]) {     //如果待插入元素<前面序列，则后移元素

                array[j+1] = array[j];

            }else{

                break;

            }

        }

        array[j+1] = temp;             //空位填上待插入元素即可

    }

}

int main(int argc,constchar * argv[])

{

    int i =0;

    int a[] = {5,4,9,8,7,6,0,1,3,2};

    int len =sizeof(a)/sizeof(a[0]);

    // 插入排序

    InsertSort(a,len);

    for (i =0; i < len; i++) {

        printf("%d ",a[i]);

    }

    printf("\n");

    return0;

}

深入浅出排序算法之－插入排序