无条件排序数组

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

第二个循环的逻辑是错误的。你在arr中有六个数字，没有双倍，这意味着buf中总共有六个元素将被设置为1。

这意味着一段时间后，i 的值将是 6，然后您将其用作 arr 的索引，但索引 6 是数组中的第七个元素，导致你写越界。

Answer 2

问题是您的代码写入了数组末尾。它发生在您遇到计数序列中的最后一个元素之后，但在数组 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];
}

现在，数组 "active" 部分末尾的 -1 仍然是 -1 (demo)。

无条件排序数组

sort array without conditional

c++

arrays

sorting

counting-sort