泡沫排序優化C++

Question

我只是在練習一點點，並嘗試使用冒泡排序算法對數組進行排序。編譯器沒有給我任何警告或錯誤，它運行良好！首先你輸入一個數字10次，然後程序對它們進行排序並打印出來。

代碼：

#include <iostream> 
using namespace std; 

void arr_sort(int* array, const int arr_size){ 

int temp = 0; //Temporary integer to store (if necessary) the current element 
int end = 0; //Run time condition 

while(end++ != arr_size){ // Will loop max. 10 times 

    for(int i = 0; i < arr_size; i++){ 

     if(array[i] > array[i + 1]){ //If the current element 
      temp = array[i]; //is bigger than the next 

      array[i] = array[i + 1];//Change the positions 
      array[i + 1] = temp;  
     } 
    } 
} 

} 

int main(){ 

int arr_input[10]; 

for(int i = 0; i < 10;i++)  //The user has to type 10 numbers 
    cin >> arr_input[i];  //which will be stored in this array 

arr_sort(arr_input, 10);  //sorts the array 

cout << endl << endl; 

for(int i = 0; i < 10; i++)  //Print out the array! 
    cout << arr_input[i] << ", "; 
cout << endl; 

return 0; 
} 

我唯一的問題是while循環在arr_sort功能。我的意思是它排序陣列，直到結束具有相同的值arr_size。但通常不需要那麼長時間。我現在的問題...我如何改進這個功能？我如何測試數組是否完全排序，以便while循環可以停止而不需要運行另一個時間和另一個時間...？

Answer 1

就在for循環之外，放置一個bool並將其設置爲false。在交換塊內，將布爾值設置爲true。在for循環之後，檢查布爾值的值，如果它仍然是false，則不會進行交換，因此數組已排序，因此請跳出while循環。

while(end++ != arr_size){ // Will loop max. 10 times 

    bool swapped = false; 
    for(int i = 0; i < arr_size; i++){ 

     if(array[i] > array[i + 1]){ //If the current element 
      temp = array[i]; //is bigger than the next 

      array[i] = array[i + 1];//Change the positions 
      array[i + 1] = temp; 
      swapped = true;  
     } 
    } 
    if (!swapped) break; 
} 

Answer 2

您for循環之前，假設它的排序：

bool sorted = true; 

在你if statement`，記錄中沒有排序：

sorted = false; 

您for loop`後，返回，如果沒有證據表明它沒有排序：

if (sorted) return;