C 語(yǔ)言函數(shù)庫(kù)qsort通過(guò)void *支持多種數(shù)據(jù)類型的數(shù)組献烦，使用起來(lái)也很方便滓窍。
我們這里也一步一步地寫一個(gè)類似qsort的函數(shù)。我們的目的是學(xué)習(xí)void *的用法巩那，并不是學(xué)習(xí)快速排序吏夯，所以我們就實(shí)現(xiàn)簡(jiǎn)單一些的排序算法，用冒泡排序好了即横。
冒泡排序噪生，第一版
很快就寫好了第一版
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void sort(int arr[], int total_elems) {
for (int i = 0; i < total_elems; i++) {
for (int j = i + 1; j < total_elems; j++) {
if (arr[i] > arr[j]) {
swap(&arr[i], &arr[j]);
}
}
}
}
int main() {
int data[] = {3, 55, -4, 12, -73, 127, 6, 19, 1, 8};
sort(data, sizeof(data) / sizeof(int));
for (int i = 0; i < (sizeof(data) / sizeof(int)); i++) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}
我們測(cè)試一下，輸出
-73 -4 1 3 6 8 12 19 55 127
看起來(lái)沒(méi)有問(wèn)題东囚，但是跺嗽，如果我們的數(shù)據(jù)如果是double呢？它就罷工了页藻，必須要修改sort函數(shù)才行桨嫁。
那么庫(kù)函數(shù)qsort又是怎么支持多種數(shù)據(jù)類型的呢？我們看一下qsort函數(shù)簽名：
void qsort (void* base, size_t num, size_t size,
int (*compar)(const void*,const void*));
看來(lái)需要用指針來(lái)搞定份帐，在把sort函數(shù)改成和qsort的參數(shù)之前瞧甩，我們先把sort改成指針形式。
冒泡排序弥鹦，第二版
第二版肚逸，把sort改成指針形式，其它不變彬坏。
void sort(int *pbase, int total_elems) {
int *right_ptr = pbase + total_elems;
for (int *i = pbase; i < right_ptr; i++) {
for (int *j = i + 1; j < right_ptr; j++) {
if (*i > *j) {
swap(i, j);
}
}
}
}
第二版的程序把數(shù)組改成指針朦促，看起來(lái)和第一版沒(méi)有什么區(qū)別，不過(guò)比第一版更容易轉(zhuǎn)化成第三版栓始。
冒泡排序务冕，第三版
#include <stdio.h>
// borrowed from The GNU C Library (glibc)
#define SWAP(a, b, size) \
do { \
int __size = (size); \
char *__a = (a), *__b = (b); \
do { \
char __tmp = *__a; \
*__a++ = *__b; \
*__b++ = __tmp; \
} while (--__size > 0); \
} while (0)
void sort(void *pbase, int total_elems, int size,
int( * cmp)(void *, void *)) {
char *right_ptr = (char *)pbase + total_elems * size;
for (char *i = (char *)pbase; i < right_ptr; i += size) {
for (char *j = i + size; j < right_ptr; j += size) {
if ((*cmp)((void *)i, (void *)j) > 0) {
SWAP(i, j, size);
}
}
}
}
int cmp(void * a, void * b) {
return *((int *)a) - *((int *)b);
}
int main() {
int data[] = {3, 55, -4, 12, -73, 127, 6, 19, 1, 8};
sort(data, sizeof(data) / sizeof(int), sizeof(int), cmp);
for (int i = 0; i < (sizeof(data) / sizeof(int)); i++) {
printf("%d ", data[i]);
}
printf("\n");
return 0;
}
如果我的數(shù)據(jù)類型要改為double呢？sort函數(shù)不用修改幻赚，只需修改cmp函數(shù)即可禀忆。
int cmp(void * a, void * b) {
return (*((double *)a) - * ((double *)b) > 0) ? 1 : -1;
}
這個(gè)比較函數(shù)cmp獨(dú)立出來(lái)還有一個(gè)好處，就是你可以自定義比較的規(guī)則落恼，如果你需要從大到小排列箩退，只需要調(diào)換a和b的位置。
int cmp(void * a, void * b) {
return (*((double *)b) - * ((double *)a) > 0) ? 1 : -1;
}
我們看到sort函數(shù)其實(shí)并不認(rèn)識(shí)數(shù)據(jù)佳谦，只是數(shù)據(jù)的搬運(yùn)工戴涝，通過(guò)cmp函數(shù)，告訴sort如何比較數(shù)據(jù)，通過(guò)元素長(zhǎng)度size啥刻，告訴sort每次移動(dòng)多少個(gè)字節(jié)奸鸯，而內(nèi)部的char *表明按字節(jié)操作，并不是真正的類型可帽。
現(xiàn)在我們sort函數(shù)看起來(lái)和系統(tǒng)函數(shù)qsort一樣娄涩，我們把sort給位qsort并導(dǎo)入頭文件#incude <stdlib.h>，系統(tǒng)會(huì)保警告
sor.c:37:56: warning: incompatible pointer types passing 'int (void *, void *)' to parameter of type 'int
(* _Nonnull)(const void *, const void *)' [-Wincompatible-pointer-types]
qsort(data, sizeof(data) / sizeof(int), sizeof(int), cmp);
^~~
哦映跟，我們應(yīng)該加上const蓄拣，把cmp和sort函數(shù)都加上：
cmp改為：
int cmp(const void * a, const void * b) {
return (*((double *)b) - * ((double *)a) > 0) ? 1 : -1;
}
sort 函數(shù)簽名改為
void sort(void *pbase, int total_elems, int size,
int( * cmp)(const void *, const void *))
警告就消除了。
再回看系統(tǒng)函數(shù)
void qsort (void* base, size_t num, size_t size,
int (*compar)(const void*,const void*));
除了兩個(gè)參數(shù)是用了size_t類型申窘，size_t等同無(wú)符號(hào)長(zhǎng)整型unsigned long弯蚜，不過(guò)一般用int長(zhǎng)度也夠了孔轴，如果你的數(shù)據(jù)很多剃法，還是用系統(tǒng)的qsort吧，當(dāng)然你的數(shù)據(jù)很少路鹰，也應(yīng)該用qsort ：）贷洲，除非你需要穩(wěn)定排序或者你用的單片機(jī)空間吃緊。
