我写了一个希尔排序，然后想插入两个计数器对它的比较次数和移动次数进行记数，不知道该加在哪里？我加后的结果跟预期不一样。请问到底加在哪里啊？谢谢了

public static void shellSort(int[] data, int len)
{
int judgeTime = 0; //比较次数
int moveTime = 0; //移动次数

for (int d = len / 2; d > 0; d /= 2) //增量设置,将数据分组
{
for (int m = 0; m < d; m++) //对每个分组排序
{

for (int i = m + d; i < len; i += d) //每个分组的第i个元素，和前面所有元素进行比较
{

int j = i - d;
while (j >= 0 && data[i] < data[j])
{
data[j + d] = data[j]; //符合条件时，将数据后移一个位置
j -= d;

}
data[j + d] = data[i]; //找到正确的位置，插入

}
}

}
}

请问这2个计数器应该放在哪里啊？再次谢谢了

see the attached c++ code and the comments inside.

[CODE]#include <iostream>
#include "hjns.h"
using namespace std;

/**
This implementation has O(n^2) comparsions and moves.
Sample output:
-100 68 -82 76 -87 -77 93 -30 96 8 15 -94 0 100 -83 100 98 98 26 0
-100 -94 -87 -83 -82 -77 -30 0 0 8 15 26 68 76 93 96 98 98 100 100
number of comparisons is 87
number of moves is 63
Press any key to continue . . .

There exists O(n lg^2 n) shellsort algorithm.
See Pratt, V (1979). Shellsort and sorting networks
(Outstanding dissertations in the computer sciences).
Garland. ISBN 0-824-04406-1. (This was originally presented
as the author's Ph.D. thesis, Stanford University, 1971)
*/
void shellsort(int* a, int size, int& numComparisons, int& numMoves);

int main(int argc, char** argv)
{
const int kSize = 20;
int a[kSize];
int numComparisons;
int numMoves;
hj::number::randoma(a, kSize);
hj::print(a, DIM(a));
shellsort(a, DIM(a), numComparisons, numMoves);
hj::print(a, DIM(a));
cout<<"number of comparisons is "<<numComparisons<<endl;
cout<<"number of moves is "<<numMoves<<endl;
return 0;
}
void shellsort(int* a, int size, int& numComparisons, int& numMoves)
{
int i;
int j;
int key;
int increment = size / 2;
numComparisons = 0;
numMoves = 0;
while (increment>0)
{
for (i=increment; i < size; i+=increment)
{
j = i;
key = a[i];
// search the insertion point
while ( j >= increment && a[j-increment] > key )
{
a[j] = a[j - increment];
j -= increment;
++numMoves; // we moved items
++numComparisons; // we compared items
}
a[j] = key; // insert it
// adjust number of comparsions. This is the case
// in which j >= increment but a[j-increment] <= key.
// In this case, we compare once (and only once) and
// exit the while loop above.
if(j>=increment)
++numComparisons;
}

increment /= 2;
// this is not necessary, but will save one loop
if (increment == 2)
increment = 1;
}
}[/CODE]

[此贴子已经被作者于2007-6-13 7:32:37编辑过]

加两个参数来记录比较和移动次数

public static void shellSort(int[] data, int len)
{
int judgeTime = 0; //比较次数
int moveTime = 0; //移动次数

for (int d = len / 2; d > 0; d /= 2) //增量设置,将数据分组
{
for (int m = 0; m < d; m++) //对每个分组排序
{

for (int i = m + d; i < len; i += d) //每个分组的第i个元素，和前面所有元素进行比较
{
judgeTime++; //比较次数计数
int j = i - d;
while (j >= 0 && data[i] < data[j])
{
moveTime++; //移动次数计数
data[j + d] = data[j]; //符合条件时，将数据后移一个位置
j -= d;

}
data[j + d] = data[i]; //找到正确的位置，插入

}
}

}
}
如果楼主循环判断最好是用数组保留计数值.

我想是在下面加入一个循环
然后再输出就可以了

不错不错