C++無法使選擇排序正常工作

我想了解排序算法，所以基於谷歌搜索示例/解釋我寫了下面的代碼。代碼80％的時間工作。每過一段時間它都沒有正確排序，我看不出爲什麼。C++無法使選擇排序正常工作

#include <iostream> 
#include <ctime> 
#include <cstdlib> 

using namespace std; 

void setArray(int *, const int &); 
void selectionSorting(int *, const int &); 

int main() 
{ 
    int numOfElem; 
    cout << "Num of array elements: "; 
    cin >> numOfElem; 
    cout << '\n'; 

    int array[numOfElem]; 
    setArray(array, numOfElem); 

    selectionSorting(array, numOfElem); 

    cout << '\n'; 
    return 0; 
} 

void setArray(int *array, const int & numOfElem){ 
    srand(time(0)); 
    cout << "Original array: " << '\n'; 
    for (int i=0; i<numOfElem; i++){ 
     array[i] = rand()%30; 
     cout << array[i] << ' '; 
    } 
    cout << '\n'; 
} 

void selectionSorting(int *array, const int &numOfElem){ 
    int eff_size, swap; 
    int maxpos = 0; 
    for (eff_size = numOfElem; eff_size>1; eff_size--){ 
     // loop searching for a position of largest number in the array 
     for (int i=0; i<eff_size; i++){ 
      maxpos = array[i] > array[maxpos] ? i : maxpos; 
     } 
     swap = array[maxpos]; 
     array[maxpos] = array[eff_size-1]; 
     array[eff_size-1] = swap; 
    } 
    cout << "Selection Sorting: " << '\n'; 
    for (int i=0; i<numOfElem; i++){ 
     cout << array[i] << ' '; 
    } 
}

輸出示例：

Num of array elements: 5 

Original array: 
7 17 1 12 25 
Selection Sorting: 
1 7 17 25 12

我看不到任何模式排序失敗 - 它在不同的地方發生故障，天氣有重複號碼，不管有多少數量我提供等。 ..

來源

2014-09-11 CallMeBob

在外循環的每個迭代（超過eff_size），你應該重新設置maxpos爲0。否則你有maxpos熄滅進行排序（有效部分的機會出現這種情況，如果最大元素是最後一個在有效部分中，即如果maxpos==effsize）。

來源

2014-09-11 12:09:50

實際上，隨着數組在每次迭代中被部分排序，可以將'maxpos'設置爲迭代當前元素的索引，對吧？不是說在這種情況下它會帶來很多性能提升... – streppel 2014-09-11 12:21:04

@Streppel有足夠的線程可以優化選擇排序。我的回答集中在問題 – 2014-09-11 12:22:04

問題中提出的問題......我花了2小時試圖解決這個小問題。現在完美工作 - 非常感謝！（如果我有足夠的代表，我會給+1） – CallMeBob 2014-09-11 12:22:06

C++無法使選擇排序正常工作

回答

相關問題