我有这个关于在 C++ 中实现 Shell Sort 的任务。我已经设法在 Shell Sort 中获得数组中元素之间的比较次数。但是,我无法弄清楚在比较发生后如何识别元素的移动次数。这是我的 Shell Sort 代码(我从 Internet 获得此代码)
int shellSort(int arr[], int n) {
int compr = 0; //indicate num of comparison
cout << endl << "Sorting using Shell Sort..." << endl << endl;
// Start with a big gap, then reduce the gap
for (int gap = n/2; gap > 0; gap /= 2) {
compr++; //the gap>0 comparison
for (int i = gap; i < n; i += 1) {
compr++; // the i<size comparison
// add a[i] to the elements that have been gap sorted
// save a[i] in temp and make a hole at position i
int temp = arr[i];
// shift earlier gap-sorted elements up until the correct
// location for a[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
compr++; // the j>=gap comparison
compr++; // the temp<arr[j-gap] comparison
}
// put temp (the original a[i]) in its correct location
arr[j] = temp;
}
}
cout << "Number of Comparison in Array of " << n << " Elements : " << compr << endl;}
希望有人能帮我弄清楚。提前致谢。