# Ch13 排序
> 搭配[green judge解題系統](http://www.tcgs.tc.edu.tw:1218/)
> Special thanks to [台中女中sagit老師](http://www.tcgs.tc.edu.tw/~sagit/index.htm) \<\(\_ \_\)\>
##
> 上一章：[副函式與遞迴](https://hackmd.io/s/r1ewEfGqM)
> 下一章：[貪婪演算法](https://hackmd.io/s/rkhigGlTG)
> 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
## <font color='darkblue'>什麼是排序</font>
將陣列裡的元素重新安排位置
讓它們從小到大、或是從大到小排好
就是排序
例如原本的陣列為 0、3、16、2、9
從小到大排序後為 0、2、3、9、16
從大到小排序後為 16、9、3、2、0
要達成這樣的效果
有許多的排序演算法可以實現
以下動畫GIF皆取自[Wikimedia](https://commons.wikimedia.org/wiki/Main_Page)
## <font color='darkblue'>氣泡排序法</font>
就像氣泡會從水底浮到水面一樣
每次比對相鄰的兩個，讓大的那個移到後面去
第一輪做完後 會發現最大的數字被移到了最後面
第二輪做完後 會發現第二大的數字被移到了倒數第二個
過了n輪以後就會按照從小到大排好
```cpp=
for(int i=0;i<n;i++){
for(int j=0;j<n-1-i;j++){
if(arr[j]>arr[j+1])
swap(arr[j], arr[j+1]);
}
}
```
## <font color='darkblue'>選擇排序法</font>
像整理手中的撲克牌一樣
每次都揪出最小的放到最前面，再也不去動它
一共要揪n次
就會按照從小到大排好
動畫中黃色的數字是已經排好、不再去動的
每一輪都會在剩下的白色中找最小的
用藍色掃過每一個數字
紅色紀錄目前看到的最小值
總共要進行n輪
```cpp=
for(int i=0;i<n;i++){
int idx=i; //先假設第i個位置是最小的，之後找到更小再代換
for(int j=i;j<n;j++){
if(arr[j]<arr[idx]){
idx=j;
}
}
swap(arr[i], arr[idx]);
}
```
## <font color='darkblue'>插入排序法</font>
這也和整理撲克牌的方法滿像的
每一輪都從尚未整理的牌中拿出一張
然後看它應該要被安插到已經整理好的牌堆的哪個位置
總共要進行n輪
```cpp=
for(int i=0;i<n;i++){
for(int j=i;j>=1;j--){
if(arr[j]<arr[j-1])
swap(arr[j], arr[j-1]);
}
}
```
## <font color='darkblue'>應用：數字排序</font>
要將數字按照順序排好
請想好兩件事
1. 用什麼來決定誰前誰後？
2. 從上述三種排序法裡面選一個自己喜歡的
以下程式將示範
1. 小的數字在前面
2. 用個氣泡排序吧
```cpp=
int arr[10]={0,3,1,6,0,2,9,84,12,31}; //一個沒排序過的亂亂陣列
for(int i=0;i<10;i++){
for(int j=0;j<9;j++){
if(arr[j]>arr[j+1])
swap(arr[j], arr[j+1]);
}
}
//印出來看是不是真的從小到大排好了
for(int i=0;i<10;i++){
cout<<arr[i]<<" ";
}
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Green Judge b019: 富比士富豪榜 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b019)
## <font color='darkblue'>應用：字串排序</font>
其實字串也可以直接比大小喔
會先比第一個字，如果一樣再比第二個字...以此類推
以下程式將示範
1. 小的字串在前面
2. 來個插入排序法吧
```cpp=
string arr[5]={"Hello", "Hi", "QQ", "GG", "Bang"};
for(int i=0;i<5;i++){
for(int j=i;j>=1;j--){
if(arr[j]<arr[j-1])
swap(arr[j], arr[j-1]);
}
}
for(int i=0;i<5;i++){
cout<<arr[i]<<endl;
}
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Green Judge b020: 辛德勒的名單 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b020)
## <font color='darkblue'>應用：複合欄位排序</font>
如果兩個東西要比大小，
是要先比其中一個特徵，一樣的話再比下一個，再一樣就再比下一個...的話
就不是只用大於小於就可以解決囉
要自己寫一段if else~
<font color='darkorange'>【例題】</font>
> 輸入一個n
> 接著輸入n個人的名字以及出生年月日
> 依照年分->月份->日期的順序排序
> 也就是，先比年分，再比月份，再比日期
> 輸出排序過後的每個人的名字
既然有姓名和年月日
那我們就開四個陣列來分別存姓名和年月日吧
```cpp=
string name[50];
int year[50];
int month[50];
int date[50];
int n;
cin >> n;
for(int i=0;i<n;i++{
cin >> name[i];
cin >> year[i];
cin >> month[i];
cin >> date[i];
}
```
接下來要排序囉
以下程式將示範
1.年份小的在前面，若一樣則月份小的在前面，若又一樣則日期小的在前面
2.來用個插入排序法吧
```cpp=15
for(int i=0;i<n;i++){
for(int j=i;j>=1;j--){
if(year[j]<year[j-1]){
swap(name[j], name[j-1]);
swap(year[j], year[j-1]);
swap(month[j], month[j-1]);
swap(date[j], date[j-1]);
}
else if(year[j]==year[j-1]&&month[j]<month[j-1]){
swap(name[j], name[j-1]);
swap(year[j], year[j-1]);
swap(month[j], month[j-1]);
swap(date[j], date[j-1]);
}
else if(year[j]==year[j-1]&&month[j]==month[j-1]&&date[j]<date[j-1]){
swap(name[j], name[j-1]);
swap(year[j], year[j-1]);
swap(month[j], month[j-1]);
swap(date[j], date[j-1]);
}
}
}
```
最後再依序輸出他們的名字
```cpp=37
for(int i=0;i<n;i++){
cout << name[i] << endl;
}
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [Green Judge b021: 指考分發 ](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b021)
##
> 上一章：[副函式與遞迴](https://hackmd.io/s/r1ewEfGqM)
> 下一章：[貪婪演算法](https://hackmd.io/s/rkhigGlTG)
> 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
Sign in with Wallet
Connect another wallet