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]);
}依然能够实现正确的排序,这是为什么呢
-
-
caozhy
2014.11.19 19:08
- 已采纳
修改为后者性能会降低。
-
- CSDN_SUSAN 回复caozhy: 原程序有三重for循环,而修改过的只有两重。并且修改过的程序只是对gap=1的子序列进行比较就完成排序了,而原程序需要从gap=n/2到gap=1,都要比较交换
- 3 年多之前 回复
-
- CSDN_SUSAN 首先通过对数组{ 13, 27, 49, 55, 4, 49, 38, 65, 97, 26 }的测试,结果发现原程序swap了10次完成了排序,而修改过的swap了15次。但是很明显原程序循环比较的次数多于修改过的程序,那么这个性能的标准是什么呢?谢谢
- 3 年多之前 回复
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!