Ch13 排序

搭配green judge解題系統
Special thanks to 台中女中sagit老師 <(_ _)>

上一章：副函式與遞迴
下一章：貪婪演算法
回目錄：國立科學園區實驗中學C++程式語言自學講義

什麼是排序

將陣列裡的元素重新安排位置
讓它們從小到大、或是從大到小排好
就是排序

例如原本的陣列為 0、3、16、2、9
從小到大排序後為 0、2、3、9、16
從大到小排序後為 16、9、3、2、0

要達成這樣的效果
有許多的排序演算法可以實現

以下動畫GIF皆取自Wikimedia

氣泡排序法

就像氣泡會從水底浮到水面一樣
每次比對相鄰的兩個，讓大的那個移到後面去
第一輪做完後 會發現最大的數字被移到了最後面
第二輪做完後 會發現第二大的數字被移到了倒數第二個
過了n輪以後就會按照從小到大排好

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]);
    }
}

選擇排序法

像整理手中的撲克牌一樣
每次都揪出最小的放到最前面，再也不去動它
一共要揪n次
就會按照從小到大排好
動畫中黃色的數字是已經排好、不再去動的
每一輪都會在剩下的白色中找最小的
用藍色掃過每一個數字
紅色紀錄目前看到的最小值
總共要進行n輪

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]);
}

插入排序法

這也和整理撲克牌的方法滿像的
每一輪都從尚未整理的牌中拿出一張
然後看它應該要被安插到已經整理好的牌堆的哪個位置
總共要進行n輪

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]);
    }
}

應用：數字排序

要將數字按照順序排好
請想好兩件事

1. 用什麼來決定誰前誰後？
2. 從上述三種排序法裡面選一個自己喜歡的

以下程式將示範

1. 小的數字在前面
2. 用個氣泡排序吧

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]<<" ";
}

【學生練習題】

• Green Judge b019: 富比士富豪榜

應用：字串排序

其實字串也可以直接比大小喔
會先比第一個字，如果一樣再比第二個字…以此類推

以下程式將示範

1. 小的字串在前面
2. 來個插入排序法吧

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

【學生練習題】

• Green Judge b020: 辛德勒的名單

應用：複合欄位排序

如果兩個東西要比大小，
是要先比其中一個特徵，一樣的話再比下一個，再一樣就再比下一個…的話
就不是只用大於小於就可以解決囉
要自己寫一段if else~

【例題】

輸入一個n
接著輸入n個人的名字以及出生年月日
依照年分->月份->日期的順序排序
也就是，先比年分，再比月份，再比日期
輸出排序過後的每個人的名字

既然有姓名和年月日
那我們就開四個陣列來分別存姓名和年月日吧

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.來用個插入排序法吧

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]);
        }
    }
}

最後再依序輸出他們的名字

for(int i=0;i<n;i++){
    cout << name[i] << endl;
}

【學生練習題】

• Green Judge b021: 指考分發

上一章：副函式與遞迴
下一章：貪婪演算法
回目錄：國立科學園區實驗中學C++程式語言自學講義