主题Sorting排序.ppt
《主题Sorting排序.ppt》由会员分享,可在线阅读,更多相关《主题Sorting排序.ppt(30页珍藏版)》请在三一文库上搜索。
1、1,主題: Sorting (排序),解題技巧 什麼是 sorting? 基本的 sorting 方法 如何使用 qsort 例題講解: A.299 歷年題目,2,什麼是 sorting?,將給定的資料按照特定的順序排列好 由小到大 由大到小 例: 1, 7, 9, 5, 3 由小到大:1, 3, 5, 7, 9 由大到小:9, 7, 5, 3, 1,3,什麼是 sorting?,只有數字能比大小嗎? John Bob 小明 小華 只要能定義大小關係,就可以 sort J 在 B 之後 John Bob “明”筆畫比“華”少 小明 小華,4,常見的 sorting 演算法,bubble sor
2、t merge sort quick sort heap sort integer sort,5,Bubble sort,原理 就像氣泡會往上浮一樣,小的數字必須要往前進,而大的數字就必須往後退 每次比較相鄰的兩個數字,然後將小的放在前面的位置,而大的放在後面的位置,6,Example,1,7,9,5,3,1,7,9,5,3,1,7,5,9,3,1,7,5,3,9,1,7,5,3,9,1,5,7,3,9,1,5,3,7,9,1,5,3,7,9,1,3,5,7,9,1,3,5,7,9,stage 1,stage 2,stage 3,stage 4,7,swap,方法 1: 寫一個 swap 的
3、function,每次需要的時侯就可以 call 來用 注意不能直接傳值進去,8,swap,example: 將兩個整數互換,void swap( int *a, int *b) int tmp; tmp = *a; *a = *b; *b = tmp; ,int x, y; swap( ,9,swap,方法 2: 利用 #define 定義 swap 變數要記得宣告,10,swap,example: 將兩個整數互換,#define swap( x, y) ( t) = ( x), ( x) = ( y), ( y) = ( t),int t; swap( x, y);,11,for ( i
4、= 0 ; i num j + 1 ) swap(,C code,代n i 2會更快,12,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,13,Parallel array,有時後在寫程式時為了方便起見會開幾個陣列來儲存而不是用 structure,這時如果按其中一個 array 的值來 sort
5、 的話,要記得所有的 array 都要跟著做一樣的動作 例: ai 代表身高,bi 代表體重,現在想按照身高來做 sort,則 bi 也應該做相對應的變動才能夠讓 ai 和 bi 代表同一個人的身高體重 在 swap(ai, aj) 時也應該做 swap(bi, bj)的動作,14,qsort,C 內建的 sort function,一般來說比用 bubble sort 來的快。 需要自己寫一個 compare function,15,Example: qsort,int tbl = 5, 6, 12, 3, 20, 8; int comp_func( const void *a, const
6、 void *b) int c, d; c = *(int *)(a); d = *(int *)(b); if (c d) return (1); else if (c = d) return (0); else return (-1); qsort(tbl, sizeof(tbl) / sizeof(tbl0), sizeof(tbl0), comp_func);,陣列指標,要 sort 的個數,每個要 sort 的 element 的大小,compare function,16,Example: qsort,char tbl10 = “Hello”, “OK”, “Test”, “BBS
7、”, “Book”, “C”; int comp_func( const void *a, const void *b) char *c, *d; c = (char *)(a); d = (char *)(b); return (strcmp(c, d); qsort(tbl, sizeof(tbl) / sizeof(tbl0), sizeof(tbl0), comp_func);,17,Example: qsort,#include int num5 = 1, 7, 9, 5, 3 ; int comp_func(const void *a, const void *b) int c,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 主题 Sorting 排序
链接地址:https://www.31doc.com/p-2714443.html