快速排序算法運行不正常

Question

#include <iostream> 

#include <string> 

using namespace std; 

//Iterates over the string array appNames displaying each application 
//name in a separate line. There are appCount elements in the array 

void displayAllApplicationNames(string appNames[], int appCount); 

//Swaps strings in string array appNames between appIndex1 and appIndex2 

void swapAppNames(int appIndex1, int appIndex2, string appNames[]); 

//Splits string array appNames around a pivot index p (the pivot). 
//Elements below index p are less than elements above index p. 
//The function returns the pivot p 

int pivot(int first, int last, string appNames[]); 

//Implements the QuickSort algorithm to sort string array 
//appNames between indeces first and last 


void quickSort(int first, int last, string appNames[]); 


void main() 

{ 

    string appNames[] = 

    { 

     "4) Pages", "2) Keynote", "3) Numbers", 

     "8) Word", "5) PowerPoint", "1) Excel", 

     "0) Documents", "6) Presentation", "7) Sheets" 

    }; 


    displayAllApplicationNames(appNames, 9); 

    swapAppNames(3, 6, appNames); 

    displayAllApplicationNames(appNames, 9); 

    quickSort(0, 8, appNames); 

    displayAllApplicationNames(appNames, 9); 


    getchar(); 


} 


void displayAllApplicationNames(string appNames[], int appCount) 

{ 

     for(appCount = 0; appCount <= 8; appCount++) 
     { 

     cout << "[" << appCount << "]\t"<< appNames[appCount] << endl; 

     } 

     if(appCount < 0 || appCount > 8) 
     { 

      cout << "_________" <<endl; 
     } 


} 


void swapAppNames(int appIndex1, int appIndex2, string appNames[]) 

{ 
    string temp = appNames[appIndex1]; 
    appNames[appIndex1] = appNames[appIndex2]; 
    appNames[appIndex2] = temp; 

} 


int pivot(int first, int last, string appNames[]) 

{ 
    int pivotIndex, mid = (first + last)/2; 
    swapAppNames(first, mid, appNames); 
    pivotIndex = first; 
    string pivotValue = appNames[first]; 
    for (int i = first + 1; i <= last; i++) 
    { 
     if (appNames[i] < pivotValue) 
     { 
      pivotIndex++; 
      swapAppNames(pivotIndex, i, appNames); 
     } 

     swapAppNames(first, last, appNames); 

     return pivotIndex; 
    } 


} 

void quickSort(int first, int last, string appNames[]) 

{ 
    if (first < last) 
    { 
     int p = pivot(first, last, appNames); 
     quickSort(first, p - 1, appNames); 
     quickSort(p + 1, last, appNames); 

    } 

} 

我的目標是對字符串數組「appNames」中的名稱進行排序。我給名稱添加了數字以顯示它們應該在的順序，但是當我運行該程序時，它似乎沒有正確排序。誰能告訴我我要去哪裏？

我一直在看這幾天都沒有結果。

編輯：這裏的解決方案。非常感謝所有回覆的人。必須交換幾個變量的位置並在快速排序算法中進行讀取。

int pivot(int first, int last, string appNames[]) 

{ 
    int pivotIndex, mid = (first + last)/2; 
    swapAppNames(first, mid, appNames); 
    pivotIndex = first; 
    string pivotValue = appNames[first]; 
    for (int i = first + 1; i <= last; i++) 
    { 
     if (appNames[i] < pivotValue) 
     { 
      pivotIndex++; 
      swapAppNames(pivotIndex, i, appNames); 
     } 


    } 

    swapAppNames(pivotIndex, first, appNames); 

     return pivotIndex; 

}

Answer 1

你的代碼，因爲你的貼吧，仍然是不正確的。這是一個工作版本。我做了一些改變。

我刪除了您樞紐功能mid啓發。這是噪音，除非你的任務明確要求你考慮最壞情況的情況。如果確實如此，那麼有更好的啓發式使用。我也改變了交換方式的效率，但希望更直觀的版本。

其他更改與last的含義相同，因爲它在您的quickSort和pivot接口中使用。如果last意味着「一個超越終點」，那更好。如果last實際上是最後一項，那麼您無法表示空列表。在您的符號（0,0）中，長度爲1，（0,1）長度爲2等，長度計算爲（last - first）+1。如果last是「one of the end」，則空列表爲（0,0），（0,1）爲長度爲1等，長度爲（last - first）。如果你繼續使用C++，你會發現這是STL的工作方式，所以現在學習它很有用。

#include <iostream> 
#include <string> 

using namespace std; 

//Iterates over the string array appNames displaying each application 
//name in a separate line. There are appCount elements in the array 
void displayAllApplicationNames(string appNames[], int appCount); 


//Swaps strings in string array appNames between appIndex1 and appIndex2 
void swapAppNames(int appIndex1, int appIndex2, string appNames[]); 


//Splits string array appNames around a pivot index p (the pivot). 
//Elements below index p are less than elements above index p. 
//The function returns the pivot p 
int pivot(int first, int last, string appNames[]); 


//Implements the QuickSort algorithm to sort string array 
//appNames between indices first and last 
void quickSort(int first, int last, string appNames[]); 


int main() { 
    string appNames[] = { 
    "4) Pages", "2) Keynote", "3) Numbers", 
    "8) Word", "5) PowerPoint", "1) Excel", 
    "0) Documents", "6) Presentation", "7) Sheets" }; 
    displayAllApplicationNames(appNames, 9); 
    swapAppNames(3, 6, appNames); 
    displayAllApplicationNames(appNames, 9); 
    quickSort(0, 9, appNames); 
    displayAllApplicationNames(appNames, 9); 
    return 0; } 


void displayAllApplicationNames(string appNames[], int appCount) { 
    for (int i = 0; i < appCount; ++i) { 
    cout << "[" << i << "]\t" << appNames[i] << endl; } 

    cout << "_________" << endl; } 


void swapAppNames(int appIndex1, int appIndex2, string appNames[]) { 
    string temp = appNames[appIndex1]; 
    appNames[appIndex1] = appNames[appIndex2]; 
    appNames[appIndex2] = temp; } 


int pivot(int p, int n, string a[]) { 
    for (int i = p + 1; i < n; ++i) { 
    if (a[i] < a[p]) { 
     swapAppNames(i, p + 1, a); 
     swapAppNames(p, p + 1, a); 
     ++p; } } 

    return p; } 


void quickSort(int first, int last, string a[]) { 
    if (first < last) { 
    int p = pivot(first, last, a); 
    quickSort(first, p, a); 
    quickSort(p + 1, last, a); } }