在C++中使用Ciura间隙序列进行shell排序

Question

我有一个应用程序到期，因为我有一个代码让我打开，但我不确定我是否正确执行了此操作，并且希望知道这个问题的任何人的一些输入。
他在这里为我们分配了“典型的”shell排序文件。

#include <iostream> 
#include <vector> 
#include <cstdlib> 
#include <ctime> 

using namespace std; 


template <typename Comparable> 
unsigned long shellsort(vector<Comparable> & a) 
{ 
    unsigned long counter = 0; 

    for(unsigned int gap = a.size()/2; gap > 0; gap /= 2) 
    for(unsigned int i = gap; i < a.size(); i++) 
    { 
     Comparable tmp = a[ i ]; 
     unsigned int j = i; 

     for(; j >= gap ; j -= gap) 
     { 
     counter++; 
     if (!(tmp < a[ j - gap ])) break; 
     a[ j ] = a[ j - gap ]; 
     } 

     a[ j ] = tmp; 
    } 

    return counter; 
} 

const int N = 10000; 

int main() 
{ 
    vector<int> rnumbers; 
    clock_t start, finish; 
    double duration; 

    srand(42); 
    start = clock(); 

    cout << "Sorting " << N << " numbers." << endl; 

    for (int i=0; i<N; i++) 
    rnumbers.push_back (rand()); 

    finish = clock(); 
    duration = (double)(finish - start)/CLOCKS_PER_SEC; 

    cout << "Initializing vector: " << duration << " seconds." << endl; 

    start = clock(); 

    unsigned long comp = shellsort (rnumbers); 

    finish = clock(); 
    duration = (double)(finish - start)/CLOCKS_PER_SEC; 

    cout << "Sorting vector: " << duration << " seconds." << endl; 
    cout << "Number of comparisons: " << comp << endl; 

    return 0; 
} 

和我们未来不得不使用修改代码来适应其是Ciura最佳间隙的序列不同的间隙的序列，然后使用下式计算得更远但不到100万的数字。

int c[] = {510774, 227011, 100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1}; 

他声称修改代码，所以我只修改了这部分。

unsigned long counter = 0; 
    int x=0; 
    int c[16] = {510774, 227011, 100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1}; 
    for(unsigned int gap = c[x]; gap > 0; gap /= 2) 
    { 
     x++; 
    for(unsigned int i = gap; i < a.size(); i++) 
    { 

我仍然排序，并没有错误，但我不能帮助，但认为通过修改代码像我一样，我真的没有什么成果，它已经在做了。

如果有人可以帮助我，我将不胜感激。

在此先感谢。

Answer 1

不要通过做gap /= 2来计算下一个间隙值，您应该迭代Ciura序列并将每个值依次用作gap。因此，而不是这样做的：

for(unsigned int gap = c[x]; gap > 0; gap /= 2) 

试着这么做：

for(int x = 0; x < 16; ++x) 
{ 
    unsigned int gap = c[x]; 
    ...