在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]; 
    ...