linux內核中的sort函數,其實跟我們所說的qsort函數很像,我們來看看qsort:
qsort 的函數原型是 void qsort(void*base,size_t num,size_t width,int(__cdecl*compare)(const void*,const void*)); 參數: 1 、待排序數組首地址 2 、數組中待排序元素數量 3 、各元素的占用空間大小 4 、指向函數的指針,用於確定排序的順序。 其中compare函數應寫為: 1 2 3 4int
comp(
const
void
*a,
const
void
*b)
{
return
*(
int
*)a-*(
int
*)b;
}
其實qsort是一個典型的快速排序的接口函數。
接下來我們來看看linux內核中的排序接口函數sort:
void sort(void *base, size_t num, size_t size,
int (*cmp_func)(const void *, const void *),
void (*swap_func)(void *, void *, int size)) ;
同樣的:
1、待排序的數組首地址
2、數組中待排序元素的數量
3、各元素的占用空間大小
4、指向函數的指針,用於確定排序的順序。
5、指向函數的指針,用於交換元素的順序(其實這可有可無,一般可以設置為NULL(空)值)。
接下來,我們來看看它的實現:
跟qsort函數的源碼其實大致相似:
void sort(void *base, size_t num, size_t size, int (*cmp_func)(const void *, const void *), void (*swap_func)(void *, void *, int size)) { /* pre-scale counters for performance */ int i = (num/2 - 1) * size, n = num * size, c, r; if (!swap_func) swap_func = (size == 4 ? u32_swap : generic_swap); /* heapify */ for ( ; i >= 0; i -= size) { for (r = i; r * 2 + size < n; r = c) { c = r * 2 + size; if (c < n - size && cmp_func(base + c, base + c + size) < 0) c += size; if (cmp_func(base + r, base + c) >= 0) break; swap_func(base + r, base + c, size); } } /* sort */ for (i = n - size; i > 0; i -= size) { swap_func(base, base + i, size); for (r = 0; r * 2 + size < i; r = c) { c = r * 2 + size; if (c < i - size && cmp_func(base + c, base + c + size) < 0) c += size; if (cmp_func(base + r, base + c) >= 0) break; swap_func(base + r, base + c, size); } } }接下來我們看一個實例程序:
將代碼從linux內核中摳出來,然後編寫程序:
#include#include typedef int u32 ; /* fri : sort array sec : array num thr : array only num size function: function: */ void sort(void *base, size_t num, size_t size, int (*cmp_func)(const void *, const void *), void (*swap_func)(void *, void *, int size)) ; int cmpint(const void *a, const void *b) ; static void u32_swap(void *a, void *b, int size) ; static void generic_swap(void *a, void *b, int size); int main(void) { int array[10] = {0}; int i = 0 ; printf("隨機產生10個100以內的數:\n"); for(i = 0 ; i < 10 ; i++) { array[i] = rand()%100; printf("array[%d]=%d\n",i , array[i]); } sort(array , 10 , sizeof(int) , cmpint , u32_swap) ; putchar('\n'); printf("排序後的數:\n"); for(i = 0 ; i < 10 ; i++) { printf("arr[%d]=%d\n",i , array[i]); } return 0 ; } void sort(void *base, size_t num, size_t size, int (*cmp_func)(const void *, const void *), void (*swap_func)(void *, void *, int size)) { /* pre-scale counters for performance */ int i = (num/2 - 1) * size, n = num * size, c, r; if (!swap_func) swap_func = (size == 4 ? u32_swap : generic_swap); /* heapify */ for ( ; i >= 0; i -= size) { for (r = i; r * 2 + size < n; r = c) { c = r * 2 + size; if (c < n - size && cmp_func(base + c, base + c + size) < 0) c += size; if (cmp_func(base + r, base + c) >= 0) break; swap_func(base + r, base + c, size); } } /* sort */ for (i = n - size; i > 0; i -= size) { swap_func(base, base + i, size); for (r = 0; r * 2 + size < i; r = c) { c = r * 2 + size; if (c < i - size && cmp_func(base + c, base + c + size) < 0) c += size; if (cmp_func(base + r, base + c) >= 0) break; swap_func(base + r, base + c, size); } } } int cmpint(const void *a, const void *b) { return *(int *)a - *(int *)b; } static void u32_swap(void *a, void *b, int size) { u32 t = *(u32 *)a; *(u32 *)a = *(u32 *)b; *(u32 *)b = t; } static void generic_swap(void *a, void *b, int size) { char t; do { t = *(char *)a; *(char *)a++ = *(char *)b; *(char *)b++ = t; } while (--size > 0); }
隨機產生10個100以內的數,通過排序接口sort排序後得到如下結果,驗證成功!