c - 将 C 数组拆分为 n 个相等的部分

Question

我试图通过计算开始和结束索引将一个数组分成 n 个相等的部分。开始和结束元素的地址将被传递给对这些数组进行排序的函数。例如，如果 arraySize = 1000，并且 n=2，则索引将为 0、499、999。到目前为止，我有以下代码，但对于奇数 n，它将其拆分为多个数组。我想到的另一种方法是通过循环运行 n 次，但我不确定从哪里开始。

  int chunkSize = arraySize / numThreads;
  for (int start = 0; start < arraySize; start += chunkSize) {
      int end = start + chunkSize - 1;
      if (end > arraySize - 1) {
          end = arraySize - 1;
      }

      InsertionSort(&array[start], end - start + 1);
  }

编辑:这是我想出的其他东西。它似乎有效，但我需要做一些更彻底的测试。我已经画了很多次并用手追踪了它。希望没有任何边缘情况会失败。我已经在限制 n >= arraySize。

int chunkSize = arraySize / numThreads;
for (int i = 0; i < numThreads; i++) {
    int start = i * chunkSize;
    int end = start + chunkSize - 1;
    if (i == numThreads - 1) {
        end = arraySize - 1;
    }

    for (int i = start; i <= end; i++) {
        printf("%d ", array[i]);
    }
        printf("\n");
}

Answer 1

使用截断除法计算最小块大小。然后计算余数。通过将 1 加到一些 block 上来分配这个余数:

伪代码:

chunk_size = array_size / N
bonus = array_size - chunk_size * N  // i.e. remainder

for (start = 0, end = chunk_size;
     start < array_size;
     start = end, end = start + chunk_size)
{
  if (bonus) {
    end++;
    bonus--;
  }

  /* do something with array slice over [start, end) interval */
}

例如，如果 array_size 为 11 且 N == 4，则 11/N 产生 2。余数(“奖金”)为 3:11 - 2*3 .因此，循环的前三个迭代将大小加 1:3 3 3。然后奖金达到零，最后一个 block 大小将仅为 2。

我们在这里所做的只不过是以某种令人满意的方式在离散量化中分配一个误差项。这正是使用 Bresenham 算法在光栅显示器上绘制线段时发生的情况，或者当使用 Floyd-Steinberg 抖动等方法将图像减少为较少数量的颜色时会发生这种情况。