C語(yǔ)言庫(kù)函數(shù)qsort的使用及模擬實(shí)現(xiàn)

第C語(yǔ)言庫(kù)函數(shù)qsort的使用及模擬實(shí)現(xiàn)目錄1.qsort函數(shù)的介紹2.qsort實(shí)現(xiàn)不同類型數(shù)據(jù)排序3.qsort的模擬實(shí)現(xiàn)

1.qsort函數(shù)的介紹

函數(shù)定義：

函數(shù)參數(shù)：

void*base

待排序的數(shù)據(jù)的起始位置

size_tnum

待排序的數(shù)據(jù)元素的個(gè)數(shù)

size_twidth

待排序的數(shù)據(jù)元素的大小，以字節(jié)為單位

int(*compar)(constvoid*,constvoid*)

是一個(gè)函數(shù)指針，函數(shù)功能是比較

因該排序算法要排序的數(shù)據(jù)的類型是不同的，比較方法也是有差異的，因此要給使用者提供一個(gè)自定義一個(gè)比較函數(shù)

2.qsort實(shí)現(xiàn)不同類型數(shù)據(jù)排序

#define_CRT_SECURE_NO_WARNINGS

#includestdio.h

#includestdlib.h

#includestring.h

intcmp_int(constvoid*e1,constvoid*e2)

return(*(int*)e1-*(int*)e2);

voidtest1()

intarr[]={9，8，7，6，5，4，3，2，1，0};

intsz=sizeof(arr)/sizeof(arr[0]);

qsort(arr,sz,sizeof(arr[0]),cmp_int);

inti=0;

for(i=0;ii++)

printf("%d",arr[i]);

structStu

charname[20];

intage;

intcmp_stu_by_name(constvoid*e1,const*e2)

returnstrcmp(((structStu*)e1)-name,((structStu*)e2)-name);

voidtest2()

structStus[]={{"zhangsan",20},{"lisi",21},"wangwu",19};

intsz=sizeof(s)/sizeof(s[0]);

qsort(s,sz,sizeof(s[0]),cmp_stu_by_name);

inti=0;

for(i=0;ii++)

printf("%s%d",s[i].name,s[i].age);

intmain()

test1();

prinf("\n");

test2();

return0;

}

test1和test2兩個(gè)函數(shù)分別對(duì)int類型數(shù)據(jù)和結(jié)構(gòu)體類型數(shù)據(jù)進(jìn)行排序，這里void*值得一提

void*指針的作用:

intmain()

inta=10;

char*pa=

return0;

}

如警告所說(shuō)，他們的類型是不兼容的，但如果用void*定義一個(gè)指針變量來(lái)接收int*數(shù)據(jù)就不會(huì)有警告，這說(shuō)明void*指針是無(wú)具體類型的指針，可以接受任意類型的地址，是泛型的，也正因?yàn)樗鼪](méi)有具體的類型，它不能解引用，也不能加減操作，想要對(duì)它解引用，只需要對(duì)地址強(qiáng)制類型轉(zhuǎn)換即可，qsort的函數(shù)參數(shù)使用void*類型也是因?yàn)椴恢朗褂谜呔唧w會(huì)傳什么類型的數(shù)據(jù)的地址，用void*可以接收任意類型的地址，提高了qsort函數(shù)的實(shí)用性

3.qsort的模擬實(shí)現(xiàn)

分析：

參考qsort函數(shù)的參數(shù)我們知道：在設(shè)計(jì)函數(shù)的時(shí)候我們是不知道使用者要傳什么類型的數(shù)據(jù)，因此會(huì)使用到void*型的指針來(lái)記錄排序數(shù)據(jù)的起始位置，最后提供的一個(gè)比較函數(shù)也會(huì)用到void*；知道了元素個(gè)數(shù)和元素寬度，就能一一找到這些數(shù)據(jù)

如上圖所示，base被強(qiáng)制類型轉(zhuǎn)換為char*型指針后一次可以訪問(wèn)一個(gè)字節(jié)，如果轉(zhuǎn)換為int*后一次跳過(guò)4個(gè)字節(jié)就太多了，轉(zhuǎn)換為char*后結(jié)合width相當(dāng)于通過(guò)起始位置加上偏移量的方法來(lái)比較，比較后通過(guò)Swap函數(shù)進(jìn)行交換，達(dá)到排序的目的

模擬實(shí)現(xiàn)：

//交換

voidSwap(char*buf1,char*buf2,intwidth)

inti=0;

for(i=0;iwidth;i++)

chartmp=*buf1;

*buf1=*buf2;

*buf2=tmp;

buf1++;

buf2++;

voidbubble_sort(void*base,intsz,intwidth,int(*cmp)(constvoid*e1,constvoid*e2))

inti=0;

for(i=0;isz-1;i++)

//一趟排序

intflag=1;

intj=0;

for(j=0;jsz-1;j++)

if(cmp((char*)base+j*width,(char*)base+(j+1)*width)0)

Swap((char*)base+j*width,(char*)base+(j+1)*width,width);

flag=0;

if(flag==1)

break;

}

intcmp_int(constvoid*e1,constvoid*e2)

return(*(int*)e1-*(int*)e2);

voidtest1()

intarr[]={9,8,7,6,5,4,3,2,1,0};

intsz=sizeof(arr)/sizeof(arr[0]);

qsort(arr,sz,sizeof(arr[0]),cmp_int);

inti=0;

for(i=0;ii++)

printf("%d",arr[i]);

structStu

charname[20];

intage;

intcmp_stu_by_name(constvoid*e1,const*e2)

returnstrcmp(((structStu*)e1)-name,((structStu*)e2)-name);

voidtest2()

structStus[]={{"zhangsan",20},{"lisi",21},"wangwu",19};

intsz=sizeof(s)/sizeof(s[0]);

bubble_sort(s,sz,sizeof(s[0]),cmp_stu_b