0

好的，所以我目前正在为我目前使用的数据结构和算法编写一个 shell 排序函数。我们得到了算法本身，但要求用 C++ 为模板类型编写它。在写下我认为正确的内容后，排序在 7 次迭代后出错，并将排序中的最高数字替换为 -858993460。

template <class T>
void shellSort(T list [], int size)
{
    int gap = size / 2;
    while (gap > 0)
    {
        for (size_t i = 0; i < size - gap; i++)
        {
            if (list[i] > list[i + gap])
            {
                swap(list, list[i], list[i + gap]);
            }
            for (int j = 0; j < size; j++)
            {
                cout << list[j] << " ";
            }
            cout << endl;
        }
        gap /= 2;

    }

    bubbleSort(list, size);

}

在我运行 Shell Sort 之前，我将 Array 的值重置为随机分类，只是为了测试其他分类，使用

void resetArray(int list [])
{
    list[0] = 5;
    list[1] = 2;
    list[2] = 7;
    list[3] = 2;
    list[4] = 3;
    list[5] = 4;
    list[6] = 1;

    cout << "List Reset. List is Now: ";
    for (size_t i = 0; i < 6; i++)
    {
        cout << list[i] << " ";

    }
    cout << endl;
}

我排序的输出是

5 2 4 2 3 7 1
5 2 4 2 3 7 1
5 2 4 2 3 7 1
5 4 2 2 3 7 1
5 4 2 2 7 3 1
5 4 -858993460 2 2 3 1
5 4 -858993460 2 2 3 1
4

1 回答 1

3

没有看到你的swap，我说罪魁祸首是这一行：

swap(list, list[i], list[i + gap]);

您在位置 2 和 3 中传递值，几乎可以肯定在这些位置需要索引。此调用应如下所示：

swap(list, i, i + gap);

否则，swap会将数组的值解释为要交换的索引，读取数组外的内存。

为避免将来出现此类问题，请std::swap改用：

std::swap(list[i], list[i + gap]);
于 2013-09-26T22:50:09.513 回答