Board logo

標題: 資料結構 302 氣泡排序(易) [打印本頁]
作者: may    時間: 6 天前 12:31     標題: 資料結構 302 氣泡排序(易)

資料結構 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    時間: 6 天前 12:36

  1. #include <bits/stdc++.h>
  2. //#include <iostream>
  3. //#include <vector>
  4. using namespace std;

  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. }

  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. }

  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
這些測資涵蓋了 隨機數列、已排序數列、反向排序數列、含有重複數字的數列、全相同數字的數列，可幫助測試程式在不同情境下的表現。



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2