希尔排序的问题，，，，，，，，，，，，
本帖最后由 sdkwjc 于 2013-04-24 10:11:46 编辑
未改进的希尔排序
void shellsort1(int a[], int n)
{
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2) //步长
for (i = 0; i < gap; i++) //按组排序
{
for (j = i + gap; j < n; j += gap)
{
if (a[j] < a[j - gap])
{
int temp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > temp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}
}
}
改进的希尔排序
void shellsort2(int a[], int n)
{
int j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
for (j = gap; j < n; j++) //从数组第gap个元素开始
if (a[j] < a[j - gap]) //每个元素与自己组内的数据进行直接插入排序
{
int temp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > temp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}
}
a[k + gap] = temp;
}
。。。
我的问题是 为什么不直接交换 而又多定义了个k变量 我看不明白这个地方 请大侠解释
[解决办法]
我感觉自己调试一遍弄个测试用例 你就明白了
[解决办法]
多定义一个K变量，就是为了在按某一步长分好的同一组中实现直接插入排序。如果不定义这个K变量，那按某一步长分好的同一组就不能实现有序排列。
[解决办法]
补充说明一下：
在上面的希尔排序中，如果不定义K变量进行直接插入排序，而直接交换，就相当于第1个与第2个比较（互相交换或是不交换），接着第2个与第3个比较（互相交换或是不交换），此时第3个就没有与第1个比较，它们之间谁大谁小就不知道了，自然就不能实现按某一步长分好的同一组有序排列了。
实际上，如你所说直接交换的话，在按某一步长分好的同一组中采用的就不是直接插入排序而是冒泡法排序了，那函数体就得重新编写。
