| 原写作时间 | 2013-03-27 |
|---|
关于排序的算法有很多。作为初学者。我在掌握了冒泡排序后掌握的第二个排序算法是插入排序。一个多月前看了一些资料，了解了排序的思想，然后自己摸索出了代码的写法。并一直这样写了这么久。直到今天看了《算法导论》的时候，才恍然大悟，原来自己一直写的插入排序并不十分正确。虽然思想是相通的。但是运行的效率却相差很多。
比如一个数列。用数组表示。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。所以我原来的写法效率与之相差太多啦。
怎么样，同样的思想（额，其实是不完全相同），写出来的程序效率还是不同的。【以上内容仓促写就，或有讹误。】
关键点在于两者在于“插入”方法的处理上。我有这样一种设想，就是用链表的方式存储元素。插入的时候直接修改指针。时间效率或许会有提高。我也没验证。不过即使我的设想是正确的，可以肯定的是那将是一种牺牲空间的时间优化法。
| 后记 | 2017-09-13 |
|---|
现在看来当时写的分析比较拙劣。实际时间复杂度中的常数系数的大小是基本可以忽略的。
