我与插入排序二三事

关于排序的算法有很多。作为初学者。我在掌握了冒泡排序后掌握的第二个排序算法是插入排序。一个多月前看了一些资料，了解了排序的思想，然后自己摸索出了代码的写法。并一直这样写了这么久。直到今天看了《算法导论》的时候，才恍然大悟，原来自己一直写的插入排序并不十分正确。虽然思想是相通的。但是运行的效率却相差很多。

比如一个数列。用数组表示。a[n]。

我写的插入排序是这样

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
for(j=0;j<i;j++)
{
    if(a[i]<a[j])
    { 
      t=a[i];
      a[i]=a[j];
      a[j]=t;
    }
}

 这样写是一种边初始化赋值编排序的写法。如果是处理一段已经序列。则直接写成

for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
    if(a[i]<a[j])
    { 
      t=a[i];
      a[i]=a[j];
      a[j]=t;
    }
}

//以上两种方法第二个for语句也可以改成

for(j-i-1;j>=0;j--)
{
 if(a[i]<a[j])
{
 t=a[i];
 a[i]=a[j];
 a[j]=t;
}
}

看到这里你会发现这里也是用的插入排序的思想。只不过关键是在插入的处理上。我的算法比正统算法差了好多。
大家都知道计算机的数据插入无法直接像加、减、乘、除、赋值那样一步到位。正规的写法是：

for(i=1;i<n;i++)
{
  t=a[i];
for(j=i-1;j>0;j--)
 {
      if(a[j]>t)
      a[j+1]=a[j];
  }
  a[i+1]=t;
}

 

假设一次赋值运算的时间为1，然后在最坏的情况，逆序的时候，我原来的写法需要移动的次数分别为1、2、3……n-1。一共是n*(n-1)/2次。每次移动实际是三次赋值运算，时间为3倍n*(n-1)/2。而正规的的写法移动次数分别是1、2、3、……n-1每次移动做一次赋值运算。最后的“插入”也是一次赋值。所以时间一共是n*(n-1)/2。所以我原来的写法效率与之相差太多啦。

 

怎么样，同样的思想（额，其实是不完全相同），写出来的程序效率还是不同的。【以上内容仓促写就，或有讹误。】

关键点在于两者在于“插入”方法的处理上。我有这样一种设想，就是用链表的方式存储元素。插入的时候直接修改指针。时间效率或许会有提高。我也没验证。不过即使我的设想是正确的，可以肯定的是那将是一种牺牲空间的时间优化法。