本文共 827 字，大约阅读时间需要 2 分钟。

目录

1.走读插入排序代码，算法复杂度O(n**2), 空间复杂度O(1)

2.插入排序特性：

排序之后的前N个元素是有序的

3.以下两段代码

代码一：

int sort_insert(int a[], int size){    int i = 0;    int j=0;    int p = 1;    int n = 0;    while(p < size){            for(i=0;i
   
    i;j--){                n++;                a[j] = a[j-1];            }               a[j] = temp;//j=i            printf("temp=%d, moved=%d\n", temp, n);         }           p++;    }       return 0;}
   

代码二：

int sort_insert2(int a[], int size){    int temp;    int j;    for(int p=1; p
   
    0 && a[j-1]>temp; j--)            a[j] = a[j-1];        a[j] = temp;    }       return 0;}
   

4.优缺点比较：

点1:优化空间

代码1和代码2虽然都能实现插入排序，但效率及优化空间就不一样了

代码1:

是从前往后面比较，即是从0到p-1 ，必须依次比较完

代码2:

可以后往前比，即从p-1，p-2比较，直到比较<=temp(待插入的a[p])即可终止，有优化空间

点2:代码行数

代码1 25行

代码2 12行，差一倍

点3:代码复杂度：

代码1明显比代码2要复杂，容易出错，代码1使用了1个while，2个for，而代码2使用了2个for

转载地址：http://popbi.baihongyu.com/