先#include <stdlib.h>
worst case : O(n^2)
average case : O(n lgn) 一般來說已經夠用了
需要自己做一個 compare function
怎麼呼叫qsort?
parameter 1 : table address
parameter 2 : table裡elements的數量
parameter 3 : size of elements , e.g 如果element型態是int, 則是sizeof(int)
parameter 4 : 呼叫compare function
1
| qsort(table, sizeof(table), sizeof(table[0]), comp_func); |
1. 一個基本的compare function
因為傳進來的是const void type，所以還要轉換成原本型態
另，有人會直接寫 return c-d，此方法可能會產生overflow，較不建議
1
2
3
4
5
6
7
| int comp_func(const void *a, const void *b){ int c = *(int*)a; int d = *(int*)b; if (c>d) return 1; else if (c<d) return -1; else return 0;} |
note:
傳回1的話，代表前面的比後面大，順序會調換 ab -> ba
傳回-1 或 0，則順序不變
2. 若是一個字串陣列需要qsort，每sort一次就要再創一個新陣列太過麻煩，用index_tb代為紀錄
1
2
3
4
5
6
7
8
9
10
11
12
13
| char* tb[10] = {"Hello", "I", "am", "Celine", "Chiu"};int tb_size = 5;int index_tb[] = {0, 1, 2, 3, 4};int comp_func(const void *a, const void *b){ int c = tb[*(int*)a]; int d = tb[*(int*)b]; int x = strcmp(c, d); if (x!=0) return x; else return *(int*)a-*(int*)b; //由index決定}qsort(index_tb, tb_size, sizeof(int), comp_func); |
3.for struct (參考UVa 11321)
//以sum值做排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| struct a_plus_b(){ int a, b, sum;};struct a_plus_b x[1000];int comp_func(const void *a, const void *b){ int c = x[*(int*)a].sum; int d = x[*(int*)b].sum; if (c>d) return 1; if (c< d) return -1; return 0;}qsort(index_tb, tb_size, sizeof(int), comp_func); |
