关于插入排序"避免明显地使用交换"的优点(JAVA实现) 好处何在呢？

关于插入排序

问题描述：

void insertionSort(AnyType[] a)
{
int j;

for(int p=1;p {
AnyType tmp=a[p];
for(j=p;j>0&&tmp.compareTo(a[j-1])<0;j--)
a[j]=a[j-1];
a[j]=tmp;
}
}

这里的交换代码实际上和下面这种交换的效果是一样的
for(j=p;j>0&&tmp.compareTo(a[j-1])<0;j--)
{
AnyType tmp=a[p];
a[j]=a[j-1];
a[j]=tmp;
}

为什么"避免明显地使用交换"呢？这样作有什么好处呢？更快吗？？望指导

答

  AnyType tmp=a[p];  //此局部变量只赋值一次
  for(j=p;j>0&&tmp.compareTo(a[j-1])<0;j--) 
      a[j]=a[j-1];  //移动到相应位置
  a[j]=tmp;  //最后一次插入

假设p=6 a[p]=2 a[0]-----a[5] 2,3,7,8,9,10 按照如上算法是
1、tmp=6;
2、a[5]移到a[6] a[4]移到a[5] a[3]移到a[4] a[2]移到a[3]
3、a[2]=tmp

 for(j=p;j>0&&tmp.compareTo(a[j-1])<0;j--)  { 
      AnyType tmp=a[p];  //获取要插入的字符
      a[j]=a[j-1];   //
      a[j]=tmp; 
  }

算法如下：
1、tmp=6; a[5]移到a[6] a[5]=tmp;
2、tmp=6; a[4]移到a[5] a[4]=tmp;
3、tmp=6; a[3]移到a[4] a[3]=tmp;
4、tmp=6; a[2]移到a[3] a[2]=tmp;

可以看到第二种交互次数明显比第一次多即最后一次 a[n]=tmp 只有最后一次才是有效的之前的都是无效的移动浪费时间

改进

  AnyType tmp=a[p];  //此局部变量只赋值一次
  AnyType current=null;
  for(j=p;j>0&&tmp.compareTo((current=a[j-1]))<0;j--) 
      a[j]=current;  //移动到相应位置
  a[j]=tmp;  //最后一次插入

a[j-1] 内部需要多条指令完成：
6: aload_1 //数组压栈
7: iload_2 //压入j
8: iconst_1 //压入常量1
9: isub //j-1
10: iaload //加载数组的第j-1个数据
即a[j-1] 如果重复多次其实很耗时因此current=a[j-1] 可以节约计算。

答

第二种做法每次交换都要申请一个交换值占用的空间，并多消耗两次数值比较的时间

关于插入排序"避免明显地使用交换"的优点(JAVA实现) 好处何在呢？

相关推荐