101北一女中 資訊選手培訓營 快速排序函式qsort() 2012.08. 07 Nan
qsort() 屬於#include<stdlib.h> 採用快速排序 函數格式： ex: qsort(陣列名稱, 元素個數, 單一元素size, 比較函式) ex: int A[N]; qsort(A, N, sizeof(int), comp);
比較函數comp 要自己寫的，只是格式固定採用void指標。 看你的陣列是什麼型態，再在裡面自己轉。 格式: int comp(const void *p, const void *q){ // …比較p跟q所指到位置的值 // 如果p < q，回傳<0的數， // 如果p == q，回傳0 // 如果p > q，回傳>0的數 }
一些飯粒範例 1. int comp(const void *p, const void *q){ int A = *(int *)p; // 把p指向的位置的值解析出來 int B = *(int *)q; // 把q指向的位置的值解析出來 if ( A == B ) return 0; return (A < B) ? -1 : 1; } 2. // 偷懶寫法，要小心overflow int comp(const void *p, const void *q){ return *(int *)p - *(int *q); } 3. // 排字元，一樣要小心overflow int comp(const void *p, const void *q){ return *(char *)p - *(char *)q; } //in main: qsort(A, N, sizeof(char), comp);
一些飯粒範例 4. // double最好這樣寫不然會壞掉 int comp(const void *p, const void *q){ double A = *(double *)p; double B = *(double *)q; if ( A == B ) return 0; return (A < B) ? -1 : 1; } // in main: qsort(nums, N, sizeof(double), comp); 5. // 比字串 #include <string.h> int comp(const void *p, const void *q){ char *strA = *(char **)p; char *strB = *(char **)q; return strcmp(strA, strB); } // in main: qsort(strs, N, sizeof(char *), comp);
一些飯粒範例 6. // 比struct struct edge{ int st, ed, cost; }edges[100]; int comp(const void *p, const void *q){ struct edge A = *(struct edge *)p; struct edge B = *(struct edge *)q; return A.cost – B.cost; //一樣要小心overflow } //in main: qsort(edges, 100, sizeof(struct edge), comp);
使用索引排序 with qsort()
索引排序？ 也就是現在假設要把人的體檢資料按照身高排隊，我給每個人一個編號，接著我把這些編號存起來，然後使用編號去排序，排序時按照編號去存取每個人的身高資料，這樣就不需要把整份體檢資料排序 比起原本的排資料，排索引在資料數很多(像Kruskal有起點、終點、cost)時會非常好用，因為它只需要搬索引陣列就好了
小小範例 int ind[5]; int height[5], weight[5], age[5]; int comp(const void *p, const void *q) int main() { int i; for(i=0; i<5; i++) { scanf(“%d %d %d”, &height[i], &weight[i], &age[i]); ind[i] = i; // 生成“索引”陣列 } qsort(ind, 5, sizeof(int), comp); //讓他去排索引 for(i=0; i<5; i++) { printf(“%d: %d”, ind[i], height[ind[i]]); printf(“ %d”, weight[ind[i]]); printf(“ %d”, age[ind[i]]); } return 0; return height[*(int *)p] – height[*(int *)q]; // 比較時是以索引去找資料比