0

我对编码还很陌生，我一直在努力处理这段代码，它允许我随机生成大量整数数组，选择特定的 shell 排序，然后测试数组是否正确排序。

#include <iostream>
#include <stdlib.h>
#include <time.h>
#define LISTLEN 100000
using namespace std;

void shellSort(int[], int, int[], int);
void testIfSorted(int[], int);

void main()
{
   {
    int list[LISTLEN];
    int seq1[] = {LISTLEN/2};
    int seq2[] = {2-1};
    int seq3[] = { 4 + 3 * (2 ^ 0) + 1 };
    int choice;

    for (int i = 1; i < LISTLEN; i++)
    {
        list[i] = rand() % LISTLEN + 1;

        cout << list[i] << endl;
    }
    cout << "\nEnter the Number for Which Sequence-Type You Wish to Use: \n"
        "1) Shell Sequence\n"
        "2) Hibbard Sequence\n"
        "3) Sedgewick Sequence\n";
        cin >> choice;

        if (choice == 1)
        {
            shellSort(list, LISTLEN, seq1, LISTLEN / 2);
        }
        else if (choice == 2)
        {
            shellSort(list, LISTLEN, seq2, (2 - 1));
        }
        else if (choice == 3)
        {
            shellSort(list, LISTLEN, seq3, (4 + 3 * (2 ^ 0) + 1));
        }

        cout << "\nVerifying List was Sorted\n";
            testIfSorted;
    }
}

    void shellSort(int arr[], int arrsize, int seq[], int seqsize)
    {
        clock_t t;
        t = clock();
        {
            int j, temp;
            for (int i = seqsize; i < arrsize; i += 1)
            {
                temp = seq[i];
                for (j = i; j >= seqsize && seq[j - seqsize] > temp; j -= seqsize)
                {
                    seq[j] = seq[j - seqsize];
                }
                seq[j] = temp;
                cout << temp << endl << endl;
            }
            t = clock() - t; 
            printf("It took me %d clicks (%f seconds).\n", t, ((float)t) / CLOCKS_PER_SEC);
        }
    }

    void testIfSorted(int list[], int length)
    {
        for (int i = 0; i < length - 1; i++)
        {
            if (list[i] < list[i + 1])
            {
                cout << "List Isn't Sorted Correctly\n";
            }
            else (list[i] > list[i + 1]);
            {
                cout << "List Sorted Correctly\n";
            }
        }
    }

我不知道我做错了什么，shell排序实际上并没有对数组进行排序，或者至少它没有进行降序排序，如果程序确实检查以确保数组正确排序，它会赢'不显示我希望它显示的消息。

4

2 回答 2

1

我没有具体的答案，但这些是一些快速调试技巧：

1 - 通过运行代码clang-format。如果您不能/不能在您的计算机上安装它，可以使用在线格式化程序，例如http://format.krzaq.cc/

2 -clang在打开所有警告的情况下使用编译器编译您的代码。同样，如果您不/无法clang在您的计算机上安装，则可以使用一些在线沙盒。为什么是 Clang？他们付出了很大的努力来提供非常好的警告/错误消息。

我都做了，这就是clang该程序必须说的（链接在这里）

prog.cc:10:1: error: 'main' must return 'int'
void main()
^~~~
int

prog.cc:41:9: warning: expression result unused [-Wunused-value]
        testIfSorted;
        ^~~~~~~~~~~~

prog.cc:61:56: warning: format specifies type 'int' but the argument has type 'clock_t' (aka 'long') [-Wformat]
        printf("It took me %d clicks (%f seconds).\n", t, ((float)t) / CLOCKS_PER_SEC);
                           ~~                          ^
                           %ld

prog.cc:45:20: warning: unused parameter 'arr' [-Wunused-parameter]
void shellSort(int arr[], int arrsize, int seq[], int seqsize)
                   ^

prog.cc:72:22: warning: expression result unused [-Wunused-value]
            (list[i] > list[i + 1]);
             ~~~~~~~ ^ ~~~~~~~~~~~

4 warnings and 1 error generated.

这些可能会有所帮助——尤其是最后一个！

于 2016-12-07T04:43:59.063 回答
0

shellsort 坏了。当它应该对值序列进行排序时，它似乎正在尝试对间隙序列进行排序。此外，间隙序列应该是一系列值。例如：seq[]arr[]

static void hsort(int a[], size_t n, size_t h)
{
    for ( size_t i, j = h; j < n; j++ ) {
        int temp = a[j];
        // @note the comparison is setup for descending.
        for ( i = j; i >= h && temp > a[i-h]; i -= h )
            a[i] = a[i-h];
        a[i] = temp;
    }
}

外壳顺序：

void shellsort1(int a[], size_t n)
{
    for ( size_t h = n/2; h > 0; h /= 2 )
        hsort(a, n, h);
}

克努斯序列：

void shellsort2(int a[], size_t n)
{
    size_t i, h = 0;
    while ( 2*(i = h*3+1) <= n )
        h = i;
    for ( ; h > 0; h /= 3 )
        hsort(a, n, h);
}

h每次调用的值共同hsort是您的间隙序列。或者，这些可以预先计算和存储。

可以通过以下方式测试降序（或更准确地说是非升序）的序列：

bool is_descending(int a[], size_t n)
{
    for ( size_t i = 1; i < n; i++ )
        if (a[i-1] < a[i])
            return false;
    return true;
}

但是，该测试不足以验证算法的正确性。考虑一个简单地将所有元素设置为单个值的函数。生成的序列将通过此测试。目视检查——虽然在调试过程中有些用处——但对于大型集合来说很容易出错并且不可能。

更好的解决方案是分配一个重复数组并使用已知的良好算法对其进行排序，然后比较每个元素是否相等。

于 2016-12-07T11:14:55.363 回答