我正在为这个特殊的快速排序算法疯狂,我不知道问题出在哪里。我在一个论坛上找到了一个例子,很好地解释了我要做的事情
给定连续的索引数组,有序数字(表示元素在数据数组中)比较所述数据值;你只是通过索引访问它们。你交换但是,索引值不是数据值。
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,我不知道为什么,程序到达那里,它们的值溢出。我找了一千次虫子,都找不到哪里有错
注意事项:1) 我非常清楚C++的无符号字符范围,并且我不能将它们更改为int。2) 实际上,我并没有包含实际数据数组的声明。compare函数可以访问它,因为它是其类的一个矩阵。
Uhh您不能在无符号字符中存储大于255或小于0的数字。无符号字符可以存储由一个无符号字节定义的范围,因此可以存储8个二进制数字。2^8=256,因为我们包括0,所以我们有256-1,等于255。(或十六进制,0xFF)
尝试使用int,甚至短裤。(关键字short
)