c++ - 无条件排序数组

Question

我需要一个不使用条件语句对整数数组进行排序的程序。数字在 0 到 100 之间，不重复。

#include <iostream>
using namespace std;

int main() {
    int arr[] = { 34, 12, 24, 65, 63, 22 };
    int arraySize = (sizeof(arr) / sizeof(*arr));
    unsigned char buf[101] = { 0 };

    for (int k = 0; k < arraySize; k++) {
        buf[arr[k]]++;
    }

    unsigned char i = 0;
    for (int k = 0; k <= 100; k++) {
        arr[i] = k;
        i += buf[k];
    }

    for (int a : arr) {
        cout << a << endl;
    }
    system("pause");
    return 0;
}

这个程序可以运行，但在关闭命令提示符后出现错误:

Run-Time Check Failure #2 - Stack around the variable 'arr' was corrupted.

有办法解决吗？

Answer 1

问题是您的代码写入了数组末尾。它发生在您遇到计数序列中的最后一个元素之后，但在数组 buf 耗尽之前，即

for (int k = 0; k <= 100; k++) {
    arr[i] = k;
    i += buf[k];
}

当您将最高元素(即 65)添加到结果时，i 达到 6，因此分配 a[i] 变得非法。通过向您的数组添加一个额外的元素，将其设置为 -1，然后观察它发生了什么(它被设置为 100；demo 1)，看看发生了什么。

您可以通过添加提前退出条件来修复它，以便在您填满数组后立即停止，即

for (int k = 0; i < arraySize && k <= 100; k++) {
    arr[i] = k;
    i += buf[k];
}

现在，数组“事件”部分末尾的 -1 仍然是 -1 (demo)。