# 排序法(2021/4/16社課)

## 本日重點:

* 了解選擇排序法、木桶排序法原理
* 了解排序函式(sort)
* 實作APCS2016/03/05第1題-成績指標

## 排序法
利用程式演算法將數字按由小到大或大到小排序完成。

## 選擇排序法
### C++程式碼:

#include <iostream>
using namespace std;
int main(){
    int n;
    int num[n+1]; //不建議這樣寫
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> num[i];
    }
	//選擇排序法 
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
    	    if(num[i]>num[j]){
    		    int t = num[j];
    		    num[j] = num[i];
    		    num[i] = t;
    	    	    //swap(num[i],num[j])
    	    }    
        }
    }
    for(int i=0;i<n;i++){
	cout << num[i] << " ";
    }
return 0;
}

### 程式解說:
雙重迴圈中，外層迴圈的變數 ${i}$ 代表跑完一次內層迴圈時 ${num[i]}$ 已放置正確的數字，
也就是把第 ${i+1}$ 小的數字已放到${num[i]}$，${0\leq i\leq n-1}$。

### 範例輸入:
5
8 9 2 7 3

### 範例:

0 1 2 3 4 陣列索引
(i) (j)
8 9 2 7 3 陣列內的值

0 1 2 3 4
(i) (j)
8 9 2 7 3 --- 第i個數字大於第j個數字，兩數字位置交換

0 1 2 3 4
(i) (j)
2 9 8 7 3

0 1 2 3 4
(i) (j)
2 9 8 7 3

0 1 2 3 4
(i) (j)
2 9 8 7 3 --- 第i個數字大於第j個數字，兩數字位置交換

0 1 2 3 4
(i) (j)
2 8 9 7 3 --- 第i個數字大於第j個數字，兩數字位置交換

0 1 2 3 4
(i) (j)
2 7 9 8 3 --- 第i個數字大於第j個數字，兩數字位置交換

0 1 2 3 4
(i) (j)
2 3 9 8 7 --- 第i個數字大於第j個數字，兩數字位置交換

0 1 2 3 4
(i) (j)
2 3 8 9 7 --- 第i個數字大於第j個數字，兩數字位置交換

0 1 2 3 4
(i) (j)
2 3 7 9 8 --- 第i個數字大於第j個數字，兩數字位置交換

0 1 2 3 4
(i)
2 3 7 8 9 ---排序完成
### 分析:
選擇排序法一共執行 ${n-1+n-2+n-3+n-4...+n-(n-1)} = \frac{n^2-n}{2}$ 次

## 木桶排序法
### C++程式碼:

#include <iostream>
using namespace std;
int main(){
    int bkt[101]={0};
    int n;
    cin >> n;
    int num[n+1]; //不建議這樣寫
    for(int i=0;i<n;i++){
    	cin >> num[i];
    	bkt[num[i]]++;
    }
    int k=0;
    for(int i=0;i<=100;i++){
    	while(bkt[i]!=0){
    	    num[k] = i;
    	    k++;
    	    bkt[i]--;
    	}
     }
    for(int i=0;i<n;i++){
    	cout << num[i] << " ";
    }
return 0;
}

### 範例輸入:
5
8 9 7 7 3
### 程式解說:
bkt[3] = 1 , bkt[7] = 2 , bkt[8] = 1 , bkt[9] = 1
使用for迴圈由i=0跑到i=100，當bkt[i]裡面有數字時就輸出
### 分析:
只適用於大於等於0的整數排序，且整數不能太大。
## 排序函式
* 要先#include <algorithm>
* sort(陣列名稱,陣列名稱+陣列內數字個數)
### C++程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int num[1000];
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> num[i];
	}
	sort(num,num+n);
	for(int i=0;i<n;i++){
		cout << num[i] << " ";
	}
return 0;
}

## 題目 APCS2016/03/05第1題-成績指標

### 題目網址:
https://zerojudge.tw/ShowProblem?problemid=b964

### 解答:

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int num[10000];
	int n;
	cin >> n;
	int f=0,f2=0;
	int i;
	for(i=0;i<n;i++){
		cin >> num[i];
		if(num[i]>=60){
			f++;
		}
		else if(num[i]<60){
			f2++;
		}
	}
	sort(num,num+n);
	for(i=0;i<n;i++){
		cout << num[i];
	}
	cout << endl;
	if(f==n)
		cout << "best case";
	else{
		for(i=n-1;num[i]>=60;i--){
		;
		}
		cout << num[i];
	}
	cout << endl;
	if(f2==n)
		cout << "worst case";
	else{
		for(i=0;num[i]<60;i++){
		;
		}
		cout << num[i];
	}
}