C++程式：按升序排列陣列元素

為了有效解決一些問題，對資料項進行正確的排序非常重要。最常見的排序問題之一就是元素排序問題。本文將演示如何在C++中按升序（根據數值遞增）排列陣列成員。

為了按特定順序排列數字或非數字元素，此領域提供了各種各樣的排序演算法。本文只介紹兩種簡單的排序方法：選擇排序和氣泡排序。讓我們分別使用適當的技術和C++實現程式碼來研究每一種方法。

使用氣泡排序法按升序排序陣列

氣泡排序法是排序陣列元素最流行且最直接的方法之一。此方法依次檢查兩個元素是否按正確順序排列。如果不是，則該方法交換元素，直到它們按正確順序排列。然後，向右移動並對另一組值重複此過程。在氣泡排序方法的幾個階段結束時，單個元素將被放置在正確的預期位置。讓我們看一下氣泡排序演算法。

演算法

  • 讀取陣列A及其大小n作為輸入
  • 對於i從0到n-1，執行
    • 對於j從0到n-2，執行
      • 如果A[j] > A[j + 1]，則
        • 交換A[j]和A[j + 1]
      • 結束if
    • 結束for
  • 結束for

示例

#include <iostream>
using namespace std;
void display( int arr[], int n ){
   for ( int i = 0; i < n; i++ ) {
      cout << arr[i] << ", ";
   }
}
void swap ( int &a, int &b ){
   int temp = a;
   a = b;
   b = temp;
}
void solve( int arr[], int n ){
   int i, j;
   for ( i = 0; i < n; i++ ) {
      for ( j = 0; j < n-1; j++ ) {
         if ( arr[j] > arr[ j+1 ] ) {
            swap( arr[j], arr[ j + 1 ] );
         }
      }
   }
}
int main(){
   int arr[] = {8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84};
   int n = sizeof( arr ) / sizeof( arr[0] );
   cout << "Array before sorting: ";
   display(arr, n);
   solve( arr, n );
   cout << "\nArray After sorting: ";
   display(arr, n);
}

輸出

Array before sorting: 8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84, 
Array After sorting: 2, 5, 8, 10, 12, 12, 25, 36, 44, 45, 58, 63, 74, 78, 84, 89, 95, 96,

使用選擇排序法按升序排序陣列

使用選擇排序策略時，我們從索引I開始，一直遍歷到給定陣列的末尾，找到最小或最大元素。假設我們正在發現每個元素。它在每個階段從索引I到末尾找到最小元素，將元素放置在適當的位置，然後重複此過程以從索引I+1等找到下一個最大元素。這些步驟完成後，整個陣列將被正確排序。

演算法

  • 讀取陣列A及其大小n作為輸入
  • 對於i從0到n-1，執行
    • ind := 從i到n的A的最小元素的索引
    • 如果A[i] > A[ind]，則
      • 交換A[i]和A[ind]
    • 結束if
  • 結束for

示例

#include <iostream>
using namespace std;
void display( int arr[], int n ){
   for ( int i = 0; i < n; i++ ) {
      cout << arr[i] << ", ";
   }
}
void swap ( int &a, int &b ){
   int temp = a;
   a = b;
   b = temp;
}
int min_index( int arr[], int n, int s, int e ){
   int min = 99999, min_ind = -1;
   for ( int i = s; i < e; i++ ) {
      if ( arr[i] < min ) {
         min = arr[i];
         min_ind = i;
      }
   }
   return min_ind;
}
void solve( int arr[], int n ){
   int i, j, ind;
   for ( i = 0; i < n; i++ ) {
      ind = min_index( arr, n, i, n );
      if ( arr[i] > arr[ ind ] ) {
         swap( arr[i], arr[ ind ] );
      }
   }
}
int main(){
   int arr[] = {8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84};
   int n = sizeof( arr ) / sizeof( arr[0] );
   cout << "Array before sorting: ";
   display(arr, n);
   solve( arr, n );
   cout << "\nArray After sorting: ";
   display(arr, n);
}

輸出

Array before sorting: 8, 45, 74, 12, 10, 36, 58, 96, 5, 2, 78, 44, 25, 12, 89, 95, 63, 84, 
Array After sorting: 2, 5, 8, 10, 12, 12, 25, 36, 44, 45, 58, 63, 74, 78, 84, 89, 95, 96,

結論

排序是一個基本問題，它涉及根據預定的佈局邏輯排列數字或其他專案。此領域還有許多其他排序方法，但在這篇文章中，我們將重點介紹兩種易於使用和理解的方法。這兩種方法是選擇排序法和氣泡排序法。我們已經使用這兩種方法將資料集按升序（非遞減）排列。雖然效率不高，但這兩種排序方法都很簡單。這兩種方法都需要O(n2)的時間複雜度，其中n是輸入的大小。如果任何階段沒有交換，則只需透過確定下一階段是否不會發生變化，就可以加快氣泡排序的速度。

更新於：2022年12月14日

11K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告