0 
# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

foreach (gap in gaps)
    # Do an insertion sort for each gap size.
    for (i = gap; i < n; i += 1)
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
            a[j] = a[j - gap]
        a[j] = temp

这是维基百科页面中的伪代码。我不确定我的 c++ 代码是否正确。这是我的代码：

void shellSort(int *array, int array_size)
{
  int e, i, j, temp;
  for(e = 0; e < array_size; e++)
  {
      for( i = e; i < array_size; i++)
      {
          temp = array[i];
          for( j = i; j >= e && array[j - e] > temp; j -= e)
          {
             array[j] = array[j-e];
          }
          array[j] = array[temp];
      }

  }
}

这是我的测试代码：

int main()
{
    int sizes[9] = {9,3,5,7,1,0,6,2,4};
    int size = 0;
    shellSort(sizes,size);

    for(int i=0;i<size;i++)
    {
        cout << sizes[i] << endl;
    }

return 0;

}

但它在屏幕上什么也没显示。

4

2 回答 2

2

好的，让我们从顶部开始

void shellSort(int *array, int array_size)
{

您的代码完全省略了所需的 gaps 数组

  const int gaps[] = {701, 301, 132, 57, 23, 10, 4, 1};
  int e, i, j, temp;

外循环需要跨越间隙而不是 0 到 array_size

  for(e = 0; e < sizeof(gaps)/sizeof(int); ++e)
  {
      int gap = gaps[e];

您需要使用内部循环中的间隙数组中的间隙

      for( i = gap; i < array_size; ++i)
      {
          temp = array[i];
          for( j = i; j >= gap && array[j - gap] > temp; j -= gap)
          {
             array[j] = array[j-gap];
          }

您需要将 temp 存储回数组中

          array[j] = temp;
      }

  }
}

注意：我现在手头没有编译器，所以我没有检查过，但我认为它是正确的。

此外，还有一些小问题，这个：

  int e, i, j, temp;

是不好的做法，而是在使用时声明每个变量，即改为：

      for( int i = gap; i < array_size; ++i)
      {
          int temp = array[i];
于 2013-03-05T13:30:09.047 回答
1

出于某种原因（没有给出评论），我的第一个答案被删除了（错别字 - 您将大小设置为 0，而不是 9）。这个问题想知道为什么“它在屏幕上什么也没有显示”。如果将 size 设置为 0，当 for 循环从 0 迭代到 < size 时，你期望它做什么？？？

在查看算法之前，您的参数必须正确。从那里开始。如果现在有些东西被转储到屏幕上，现在您可以开始调试算法（如果输出错误）。如果输出正确，那么您的算法可能没问题。

如果我对此有误，请在我的答案中发表评论。不要只是“删除”它！？！

于 2013-03-15T13:05:39.933 回答