Sorted quick sort output given an additional character

我有這個快速排序實現來排序字符。Sorted quick sort output given an additional character

int main(){ 
char val[] = "dcbeaaae"; 
    QuickSort(val, 0, length); 

    for(int i=0;i<length;i++) //Sorted print 
     cout<<val[i]; 
return 0 
} 

void QuickSort(char values[], int first, int last) 
{ 
    if(first<last) 
    { 
     int splitPoint; 
     Split(values, first, last, splitPoint); 
     QuickSort(values, first, splitPoint-1); 
     QuickSort(values, splitPoint+1, last); 
    } 
} 

void Split(char values[], int first, int last, int& splitPoint) 
{ 
    int splitVal = values[first]; 
    int saveFirst = first; 
    bool onCorrectSide; 

    first++; 
    do 
    { 
     onCorrectSide = true; 
     while(onCorrectSide) 
     { 
      if(values[first] > splitVal) 
       onCorrectSide = false; 
      else 
      { 
       first++; 
       onCorrectSide = (first<=last); 
      } 
     } 
     onCorrectSide = (first<=last); 
     while(onCorrectSide) 
      if(values[last] <= splitVal) 
       onCorrectSide = false; 
      else 
      { 
       last--; 
       onCorrectSide = (first<=last); 
      } 

     if(first<last) 
     { 
      Swap(values[first], values[last]); 
      first++; 
      last--; 
     } 
    }while(first<=last); 

    splitPoint = last; 
    Swap(values[saveFirst], values[splitPoint]); 
} 

void Swap(char& item1, char& item2) 
{ 
    char temp = item1; 
    item1 = item2; 
    item2 = temp; 
}

但是，我從這個得到的輸出是有點不對即我得到了這些分類字符的起點額外的空間。在把一個斷點，我看到，在指數0，該元素= 0

輸入：aaabcdee
輸出：aaabcdee

任何建議什麼，我在這裏失去了（一個第一一個前額外的空間）？

來源

2012-06-08 user1240679

這裏'std :: sort'出了問題嗎？ –

問題是關於上述實現中的錯誤。： -/ – user1240679

假設length是字符數組中的字符數（不包括NUL字符）。你需要調用快速排序功能：

QuickSort(val, 0, length-1);

，因爲最後一個參數功能QuickSort的長度length的字符數組該指數是length - 1數組的最後一個元素的索引。

通過將length傳遞給您正在製作的函數，即使NUL角色參與了排序，並且它比其他字符更小，它將移動到排序數組的開始位置，並在打印時將其打印爲空白。

來源

2012-06-08 18:03:14 codaddict

是的。這是一個典型的fencepost錯誤。 –

Sorted quick sort output given an additional character

回答

相關問題