主题Sorting（排序）.pptVIP

主題: Sorting (排序) 解題技巧 什麼是 sorting？ 基本的 sorting 方法 如何使用 qsort 例題講解: A.299 歷年題目 什麼是 sorting？ 將給定的資料按照特定的順序排列好 由小到大 由大到小 例： 1, 7, 9, 5, 3 由小到大：1, 3, 5, 7, 9 由大到小：9, 7, 5, 3, 1 什麼是 sorting？ 只有數字能比大小嗎？ John ? Bob 小明 ? 小華 只要能定義大小關係，就可以 sort J 在 B 之後 ? John Bob “明”筆畫比“華”少 ? 小明 小華 常見的 sorting 演算法 bubble sort merge sort quick sort heap sort integer sort Bubble sort 原理 就像氣泡會往上浮一樣，小的數字必須要往前進，而大的數字就必須往後退 每次比較相鄰的兩個數字，然後將小的放在前面的位置，而大的放在後面的位置 Example swap 方法 1: 寫一個 swap 的 function，每次需要的時侯就可以 call 來用 注意不能直接傳值進去 swap example: 將兩個整數互換 swap 方法 2: 利用 #define 定義 swap 變數要記得宣告 swap example: 將兩個整數互換 C code for ( i = 0 ; i = n – 1 ; i++ ) for ( j = 0 ; j = n – 2 ; j++) if ( num[ j ] num[ j + 1] ) swap(num[ j ] , num[ j + 1]); Stable sort 若是要 sort 的東西之中有大小相同的，如果 sort 完之後大小相同的排法是依照兩個東西 input 的順序排列的話，稱為 stable sort，如果不保證一定按照 input 的順序排的話，稱為 non-stable sort input: 3 5 2 1 3 4 stable sort: 1 2 3 3 4 5 Parallel array 有時後在寫程式時為了方便起見會開幾個陣列來儲存而不是用 structure，這時如果按其中一個 array 的值來 sort 的話，要記得所有的 array 都要跟著做一樣的動作 例: a[i] 代表身高，b[i] 代表體重，現在想按照身高來做 sort，則 b[i] 也應該做相對應的變動才能夠讓 a[i] 和 b[i] 代表同一個人的身高體重 在 swap(a[i], a[j]) 時也應該做 swap(b[i], b[j])的動作 qsort C 內建的 sort function，一般來說比用 bubble sort 來的快。 需要自己寫一個 compare function Example: qsort Example: qsort Example: qsort #include stdio.h int num[5] = {1, 7, 9, 5, 3 }; int comp_func(const void *a, const void *b){ int c, d; c = *(int *)(a); d = *(int *)(b); return ( c – d ); } int main(void){ qsort(num, sizeof(num)/sizeof(num[0]), sizeof(num[0]), comp_func); /* qsort(num, 5, sizeof(num[0]), comp_func); */ return 0; } qsort and bubble sort bubble sort 執行速度較慢 程式好寫好記，不容易忘 qsort 執行速度較快 需要自己寫 compare function 不熟的話容易忘記格式 例題講解: A.299(http://acm.uva.es/p/v2/299.html) 有一列火車總共有 L 節車廂，每節車廂都有個編號(從 1 ~ L)。現在車廂的順序亂掉了，而站長希望能把車廂的順序由 1 到 L 排好。唯一能做的方法是把相鄰的兩個車廂順序對調，請問，最少需要做幾次的車廂順序對調工作，而能讓車廂的順序由 1 到 L 排好。 L 最大到 50 Sample input/output Sample input: 3 3 1 3 2 4 4 3 2 1 2 2 1 Sample output: Optimal train swapping takes 1