資料結構 302 氣泡排序(易)

may

資料結構 302 氣泡排序
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
請撰寫一程式，首先要求使用者輸入正整數 N（1 ≤ N ≤ 20），代表有 N 個排序資料，接著依序輸入 N 個整數，每個數字之間以半形空白間隔，請將這些資料採「氣泡排序（Bubble Sort）演算法」由小到大排序，並輸出原始數列與每次循環排序的結果。

3. 輸入輸出：
輸入說明
第 1 列：輸入正整數 N（1 ≤ N ≤ 20）為排序個數。
第 2 列：依序輸入 N 個整數，整數間以半形空白間隔。

輸出說明
先輸出原始數列，接著依序換列輸出每次循環排序的結果，整數間以半形空白間隔。

（排序完成即停止，若輸入之數列已經是排序結果（沒有發生交換），輸出僅顯示「原始數列」）

範例輸入1
5
2 52 65 4 3
範例輸出1
2 52 65 4 3
2 52 4 3 65
2 4 3 52 65
2 3 4 52 65
範例輸入2
7
1 2 3 4 5 6 7
範例輸出2
1 2 3 4 5 6 7

may

1. #include <bits/stdc++.h>
   
2. //#include <iostream>
   
3. //#include <vector>
   
4. using namespace std;
   
5. 
   
6. void printArray(const vector<int>& arr) {
   
7.     for (size_t i = 0; i < arr.size(); i++) {
   
8.         cout << arr[i] << (i == arr.size() - 1 ? "\n" : " ");
   
9.     }
   
10. }
    
11. 
    
12. void bubbleSort(vector<int>& arr) {
    
13.     int n = arr.size();
    
14.     bool swapped;
    
15.    
    
16.     for (int i = 0; i < n - 1; i++) {
    
17.         swapped = false;
    
18.         for (int j = 0; j < n - 1 - i; j++) {
    
19.             if (arr[j] > arr[j + 1]) {
    
20.                 swap(arr[j], arr[j + 1]);
    
21.                 swapped = true;
    
22.             }
    
23.         }
    
24.         if (!swapped) break; // 若無交換則提前結束
    
25.         printArray(arr); // 每次排序後輸出
    
26.     }
    
27. }
    
28. 
    
29. int main() {
    
30.     int N;
    
31.     cin >> N;
    
32.     vector<int> arr(N);
    
33.    
    
34.     for (int i = 0; i < N; i++) {
    
35.         cin >> arr[i];
    
36.     }
    
37.    
    
38.     printArray(arr); // 輸出原始數列
    
39.     bubbleSort(arr);
    
40.    
    
41.     return 0;
    
42. }

複製代碼

回復 1# may
-----------------------------------------------------------------------------

程式碼說明
輸入處理

讀取一個正整數 N（代表數列長度）。

讀取 N 個整數，存入 vector<int> 容器 arr 中。

氣泡排序（Bubble Sort）

外層迴圈控制 n-1 次排序。

內層迴圈比較相鄰兩數，若前者大於後者則交換。

若某次迴圈沒有發生交換，代表數列已排序完成，提前結束排序。

輸出

先輸出原始數列。

每次排序後輸出當前數列狀態。

若數列已經排序，則只輸出原始數列。
-----------------------------------------------
測資:
測資00：隨機數列
輸入
5
8 3 7 1 5
輸出
8 3 7 1 5
3 7 1 5 8
3 1 5 7 8
1 3 5 7 8

測資01：完全遞增（最佳情況，不需排序）
輸入
6
2 4 6 8 10 12
輸出
2 4 6 8 10 12
測資 02：完全遞減（最差情況，需要完整排序）
輸入
4
9 7 5 3
輸出
9 7 5 3
7 5 3 9
5 3 7 9
3 5 7 9
測資 03：含有重複數字
輸入
7
4 2 6 2 8 4 1
輸出
4 2 6 2 8 4 1
2 4 2 6 4 1 8
2 2 4 4 1 6 8
2 2 4 1 4 6 8
2 2 1 4 4 6 8
2 1 2 4 4 6 8
1 2 2 4 4 6 8
測資04：所有數字相同
輸入
5
5 5 5 5 5
輸出
5 5 5 5 5
這些測資涵蓋了 隨機數列、已排序數列、反向排序數列、含有重複數字的數列、全相同數字的數列，可幫助測試程式在不同情境下的表現。