---
# System prepended metadata

title: 訓練場_4
tags: [訓練場]

---

---
title: 訓練場_4
tags: 訓練場
---
[👉 程式自由練習區](https://hackmd.io/@futurenest/code_training_stu_4)

## 氣泡排序法

假設由小到大排序五個數字，50、70、80、40 與 60，從頭到尾不斷比較交換相鄰兩數，直到最大數到最後位置，縮小比較的範圍，再找出縮小範圍的最大數字放置於最後，直到剩下一個元素為止。

> **原始陣列**

![](https://i.imgur.com/q1AF4xt.png)

> **第一次排序**

排序第 1 個到第 5 個元素，從前往後每次比較交換相鄰兩數，最後前 5 個元素的最大數 80 就在最後面

![](https://i.imgur.com/tDdSHwq.png)


> **第二次排序**

排序第 1 個到第 4 個元素，從前往後每次比較交換相鄰兩數，最後前 4 個元素的最大數 70 就在最後面

![](https://i.imgur.com/IIvOmGS.png)


> **第三次排序**

排序第 1 個到第 3 個元素，從前往後每次比較交換相鄰兩數，最後前 3 個元素的最大數 60 就在最後面

![](https://i.imgur.com/F5HcifZ.png)


> **第四次排序**

排序第 1 個到第 2 個元素，從前往後每次比較交換相鄰兩數，最後前 2 個元素的最大數 50 就在最後面

![](https://i.imgur.com/2Jtf0gD.png)


```python
A = [50, 70, 80, 40, 60]

# 列印出排序前陣列
print("排序前")
for item in A:
  print(item,' ', end='')
print()

# 列印出排序過程
for i in range(len(A)-1, 0, -1):
  for j in range(i):
    if A[j] > A[j+1]:
      A[j], A[j+1] = A[j+1], A[j] # 簡化過程
      # temp = A[j] 
      # A[j] = A[j+1]
      # A[j+1] = temp

  print("氣泡排序外層迴圈執行第", 5-i ,"次") 
  for item in A:
    print(item,' ', end='')
  print()

# 列印出排序後陣列
print("排序後") 
for item in A:
  print(item,' ', end='')
print()
```

```cpp
#include <iostream>
using namespace std;

// 氣泡排序
void bubbleSort(int nums[], int n) {
  for (int i = 0; i < n-1; i++) {
    for (int j = 0; j < n-i-1; j++) {
      if (nums[j] > nums[j+1]) {
        int temp = nums[j];
        nums[j] = nums[j+1];
        nums[j+1] = temp;
      }
    }
  }
}

// 選擇排序
void chooseSort(int nums[], int n) {
  for(int i = 0; i < n; i++) {
    for(int j = i+1; j < n ; j++) {
        if(nums[i] > nums[j]) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
  }
}

int main() {
    int nums[] = { 14, 33, 27, 35, 10 };

    // n = 5
    int n = sizeof(nums)/sizeof(*nums); 

    cout << "排序前 = ";
    for (int i = 0; i < n; i++) {
      cout << nums[i];
      if (i != n) cout << ", ";
    }

    // 換行："\n"
    cout << endl; 
    
		// 排序
    bubbleSort(nums, n);

    cout << "排序後 = ";
    for (int i = 0; i < n; i++) {
      cout << nums[i];
      if (i != n) cout << ", ";
    }
    
    cout << endl;
    
    return 0;
}
```

## 插入排序法

假設由小到大排序五個數字，80、50、70、40 與 60，先考慮前兩個元素，將第 2 個元素插入到指定的位置，讓第 1 個到第 2 個元素由小到大排序好，再考慮前三個元素，將第 3 個元素插入到指定的位置，讓第 1 個到第 3 個元素由小到大排序好，依此類推，直到考慮前 n 個元素，將第 n 個元素插入到指定的位置，讓第 1 個到第 n 個元素由小到大排序好。

> **原始陣列**

![](https://i.imgur.com/S1VSHsh.png)


> **第一次排序**

先考慮前兩個元素，將第 2 個元素插入到指定的位置，讓第 1 個到第 2 個元素由小到大排序好

![](https://i.imgur.com/9vu4GP0.png)

> **第二次排序**

先考慮前三個元素，將第 3 個元素插入到指定的位置，讓第 1 個到第 3 個元素由小到大排序好

![](https://i.imgur.com/T79mPRg.png)

> **第三次排序**

先考慮前四個元素，將第 4 個元素插入到指定的位置，讓第 1 個到第 4 個元素由小到大排序好

![](https://i.imgur.com/vAyGqpb.png)

> **第四次排序**

先考慮前五個元素，將第 5 個元素插入到指定的位置，讓第 1 個到第 5 個元素由小到大排序好

![](https://i.imgur.com/YYAtECZ.png)

```python
A = [80, 50, 70, 40, 60]

# 列印出排序前陣列
print("排序前")
for item in A:
  print(item,' ', end='')
print()

# 列印出排序過程
for i in range(1, len(A))):
  insert = A[i] # 用來存取暫時的資料
  j = i - 1
  while j >= 0:
    if insert < A[j]:
      A[j+1] = A[j] # 把所有元素往後推一個
    else:
      break
    j = j-1
  A[j+1] = insert # 將最小元素放到第一個
  print("外層迴圈執行", i ,"次結果為") 
  for item in A:
    print(item,' ', end='')
  print()

# 列印出排序後陣列
print("排序後") 
for item in A:
  print(item,' ', end='')
print()
```

### 翻轉陣列
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const std::string WHITESPACE = " \n\r\t\f\v";
 
std::string ltrim(const std::string &s)
{
  size_t start = s.find_first_not_of(WHITESPACE);
  return (start == std::string::npos) ? "" : s.substr(start);
}
 
std::string rtrim(const std::string &s)
{
  size_t end = s.find_last_not_of(WHITESPACE);
  return (end == std::string::npos) ? "" : s.substr(0, end + 1);
}
 
std::string trim(const std::string &s) {
  return rtrim(ltrim(s));
}

int main() {
  string text;
  string delimiter = ",";
  string nums[256];

  // cin >> text; //?? /r/n carrige return
  getline(cin, text);

  int count = 0;
  string num;
  size_t pos = 0;
  // 3, 4 , 5,6 , 7
  // npos is end of string
  while (
    (pos = text.find(delimiter)) != string::npos 
  ) {
    num = text.substr(0, pos);
    nums[count++] = trim(num);
    text.erase(0, pos + delimiter.length());
  }

  nums[count] = trim(text);

  cout << "[";
  
  // Q: i = count, 而不是 count-1
  for (int i = count; i >=0; i--) {
    cout << nums[i];
    if (i != 0) cout << ", ";
  }
  
  cout << "]";
}
```