2 csdn susan CSDN_SUSAN 于 2014.11.19 15:17 提问

关于希尔排序算法的程序问题

源程序为
void shellsort3(int a[], int n)

{
int i, j, gap;

for (gap = n / 2; gap > 0; gap /= 2)

for (i = gap; i < n; i++)

for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)

Swap(a[j], a[j + gap]);

}

如果修改为:
void shellsort3(int a[], int n)

{
int i, j, gap;
gap = 1;
for (i = gap; i < n; i++)

for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)

Swap(a[j], a[j + gap]);

}

依然能够实现正确的排序,这是为什么呢

1个回答

caozhy
caozhy   Ds   Rxr 2014.11.19 19:08
已采纳

修改为后者性能会降低。

CSDN_SUSAN
CSDN_SUSAN 回复caozhy: 原程序有三重for循环,而修改过的只有两重。并且修改过的程序只是对gap=1的子序列进行比较就完成排序了,而原程序需要从gap=n/2到gap=1,都要比较交换
大约 3 年之前 回复
caozhy
caozhy 回复CSDN_SUSAN: "很明显原程序循环比较的次数多于修改过的程序",应该你看反了吧。
大约 3 年之前 回复
CSDN_SUSAN
CSDN_SUSAN 首先通过对数组{ 13, 27, 49, 55, 4, 49, 38, 65, 97, 26 }的测试,结果发现原程序swap了10次完成了排序,而修改过的swap了15次。但是很明显原程序循环比较的次数多于修改过的程序,那么这个性能的标准是什么呢?谢谢
大约 3 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!