c++ - 索引数组快速排序调试

Question

我对这种特殊的快速排序算法感到抓狂，但我不知道问题出在哪里。我在论坛上找到了一个示例，它很好地解释了我正在尝试做的事情。

Given an index array of contiguous, ordered numbers (representing elements in the data array), you still have to compare the data values; you just access them via the index. You swap the index values, however, not the data values.

Unsorted data: 09 04 47 05 03 12
Index array:   00 01 02 03 04 05

After sort,
Unsorted data: 09 04 47 05 03 12
Index array:   04 01 03 00 05 02

Print the values indexed by the index array,
from beginning to end of the array:

Index array [0] value [04] data array [04] = 03
            [1]        01             [01]   04
            [2]        03             [03]   05
            [3]        00             [00]   09
            [4]        05             [05]   12
            [5]        02             [02]   47

Output is the data, ordered at the output

我只补充一点。比较器是一个普通的比较器，但如果我们比较两个具有相同值的不同字符，我们会比较每个字符的下一个字符并返回该结果。即比较旋转。

int compare(unsigned char i, unsigned char j);

我不会发布定义，因为我确信它可以完美运行。错误在于快速排序定义。

void quicksort(unsigned char* a, unsigned char left, unsigned char right) {
    unsigned char i = left;
    unsigned char j = right;
    unsigned char half = (left + right) / 2;
    while (i <= j) {
        while ((compare(a[i], a[half]) == -1) && (i < right))
            i++;
        while ((compare(a[j], a[half]) == 1) && (j > left))
            j--;

        if (i <= j) {
            unsigned char aux = a[i];
            a[i] = a[j];
            a[j] = aux;
            i++;       //THERE
            j--;       //THERE
        }

    }

    if (left < j)
        quicksort(a, left, j);
    if (i < right)
        quicksort(a, i, right);

}

有时 i= 255 和 j=0，但我不知道为什么，程序到达那里，它们的值就会溢出。我已经找了 bug 一千次了，我找不到错误在哪里。
笔记:1) 我完全了解 C++ unsigned char 范围，我不能将它们更改为 int。2) 我实际上并没有包含实际数据数组的声明。比较函数可以访问它，因为它是其类的属性。

Answer 1

呃，你不能在 unsigned char 中存储大于 255 或小于 0 的数字。 unsigned char 可以存储由一个无符号字节定义的范围，即 8 个二进制数字。 2^8 = 256，因为我们包括 0，所以我们有 256 - 1，给我们 255。(或十六进制，0xFF)

尝试使用整数，甚至短裤。 (关键字短)