插入排序

对集合{4,2,1,5,9}进行插入排序。

  1. 首先,取第一个元素4作为已排序集合的第一个值{4}。
  2. 接着,用第二个元素2与已排序的集合里的元素进行比较。现在已排序结合只有一个{4},所以只需与 4 判断即可,判断之后得到集合 {2、4}。
  3. 取集合第三个元素1与已排序集合{2、4}进行比较。元素1首先与已排序集合的最后一个元素4比较,若1<4,将1、4交换位置,然后1再与元素2进行比较,如元素1<2,将元素1、2的位置交换,最后得到排序集合{1,2,4}。
  4. 剩下的以此类推。

代码

int set[5] = {4,2,1,5,9};
void insert_sort(){
    int i,j,key;
    for (j = 1; j < 5; j++){
        key = set[j];
        i = j - 1;
        while (i >= 0 && set[i] > key){
            set[i+1] = set[i];
            i--;
        }
        set[i+1] = key;
    }
}

耗时

若集合是顺序排列的,插入排序的工作量近似为0。如果是逆序的,工作量最大。若集合长度为n,集合里元素是顺序的,使用插入排序进行(n-1)次操作即可。若集合里元素是逆序的,那么此时需要进行的比较有n(n-1)/2次:

1+2+3+4+...+(n-1) = n*(n-1)/2

插入排序里赋值操作是比较操作的次数加上 (n-1)次,即:

T0 =  n*(n-1)/2 + (n-1);

所以,平均来说插入排序算法的时间复杂度为Θ(n2):

T = n*(n-1)/2 + T0 
T = n*(n-1)/2 + n*(n-1)/2 + (n-1) 
T = (n+1)*(n-1)
T = Θ(n^2)

总结

如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。

Comments