索引數組quicksort調試

我瘋了，這個特殊的快速排序算法，我不知道問題在哪裏。我在論壇上找到了一個例子，很好地解釋了我想要做的事情。索引數組quicksort調試

鑑於連續的，有序號碼（表示在數據陣列中的元素）的索引陣列，仍然必須比較的數據值;你只需通過索引訪問它們。您換用的索引值，但不是的數據值。

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);

我不會發布定義，因爲我確信它的工作完美。這個錯誤在於quicksort定義。

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，我不明白爲什麼程序到達THERE，並且它們的值溢出。我查找了一千次錯誤，我找不到錯誤在哪裏。
說明： 1）我完全瞭解C++無符號字符範圍，我不能將它們更改爲int。 2）我實際上並沒有包含實際數據數組的聲明。比較函數可以訪問它，因爲它是它的類的一個屬性。

來源

2011-06-22 Erandros

Uhh無法在無符號字符中存儲大於255或小於0的數字。一個無符號字符可以存儲由一個無符號字節定義的範圍，所以有8個二進制數字。 2^8 = 256，並且因爲我們包含0，所以我們有256-1，給了我們255.（或以十六進制，0xFF）

嘗試使用整數，甚至短褲。（關鍵字short）

來源

2011-06-22 05:11:32 LainIwakura

我完全意識到這一點，我將在問題 – Erandros

中包含該字節C中的一個字節不是8位，它是存儲字符所需的大小 - 可能幾乎大於8位的任何大小（儘管我目前無法查找標準，但可能性較小）。這不值得讚揚，因爲這是你的術語，而不是你的實際答案，但你可能想考慮解決這個問題。 – paxdiablo

@Erandros，你是說你永遠不會排序超過254項的數組？似乎不必要的限制。 –

索引數組quicksort調試

回答

相關問題