C++?qsort函數(shù)排序與冒泡模擬實(shí)現(xiàn)流程詳解
本章重點(diǎn)：
1.能夠正確的理解qsort函數(shù)各個(gè)參數(shù)的含義，并能夠正確的使用qsort函數(shù)進(jìn)行各類型排序。
2.重點(diǎn)掌握qsort函數(shù)中的參數(shù)cmpar——自定義比較函數(shù)的地址。借此進(jìn)一步理解回調(diào)函數(shù)。 3.學(xué)習(xí)以冒泡排序思想模擬實(shí)現(xiàn)qsort函數(shù)。
一、qsort排序函數(shù)
1、函數(shù)功能特點(diǎn)
//頭文件:#include<stdlib.h> void qsort(void* base, size_t num, size_t size,int (*compar)(const void*, const void*));
注：因?yàn)閝sort可以對(duì)任意類型數(shù)據(jù)排序，所以待排數(shù)據(jù)的起始類型可以是任意類型，C語言中可以用void*接收任意類型的地址。
2、函數(shù)參數(shù)
3、比較函數(shù)
qsort之所以可以對(duì)任意類型的數(shù)據(jù)排序正是因?yàn)閭魅氲谋容^函數(shù)是相對(duì)自定義的：
對(duì)于比較函數(shù) int compar(const void *p1,const void *p2)
（1）比較整數(shù)：
int compareMyType(const void* p1, const void* p2)
{
return *(MyType*)p1 - *(MyType*)p2;
}
1、如果compar返回值小于0（< 0），即*(MyType*)p1 < *(MyType*)p2那么p1所指向元素會(huì)被排在p2所指向元素的前面,也就是升序 。
2、如果compar返回值等于0（= 0），即*(MyType*)p1 = *(MyType*)p2那么p1所指向元素與p2所指向元素的順序不確定。
3、如果compar返回值大于0（> 0），即*(MyType*)p1 > *(MyType*)p2那么p1所指向元素會(huì)被排在p2所指向元素的后面,也是升序。
所以為了方便理解我們可以簡(jiǎn)單這樣認(rèn)為：對(duì)于qsort函數(shù)如果compar函數(shù)的返回值<0(不進(jìn)行置換)，>0(進(jìn)行置換)，0(不進(jìn)行置換)。
即：
return *(MyType*)p1 - *(MyType*)p2;——qsort升序排序
return *(MyType*)p2 - *(MyType*)p1;——qsort降序排序
對(duì)于具體qsort函數(shù)內(nèi)部具體是怎么進(jìn)行置換或排序的我們不必關(guān)心。（內(nèi)部實(shí)現(xiàn)為快排思想）
（2）比較字符串：
int compareMyType(const void* p1, const void* p2)
{
return strcmp((MyType *) p1, (MyType *) p2);
}
同理：
return strcmp((MyType*)p1,(MyType*)p2);——qsort升序排序
return strcmp((MyType*)p2,(MyType*)p1);——qsort降序排序
（3）比較結(jié)構(gòu)體
與上述思想類似，比較結(jié)構(gòu)體時(shí)需要具體情況具體分析。
4、測(cè)試qsort排序
（1）測(cè)試qsort函數(shù)排序整形
#include<stdio.h>
#include<stdlib.h>
//輸出函數(shù)
void print(int arr[], int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
}
//比較函數(shù)
int compar(const void* e1, const void* e2)
{
return *((int*)e1) - *((int*)e2);//升序
//return *((int*)e2) - *((int*)e1);//降序
}
int main()
{
int arr[] = { 3,5,2,6,8,1,9,0,4,7 };
int sz = sizeof(arr) / sizeof(arr[0]);
//arr-數(shù)據(jù)起始地址
//sz-數(shù)據(jù)元素個(gè)數(shù)
//sizeof(arr[0])-數(shù)據(jù)元素的大小
//compar-比較函數(shù)指針
qsort(arr, sz, sizeof(arr[0]), compar);
print(arr, sz);
return 0;
}
（2）測(cè)試qsort函數(shù)排序結(jié)構(gòu)體
??按年齡排序
#include<stdio.h>
#include<stdlib.h>
//結(jié)構(gòu)體
struct stu
{
char name[20];
int age;
};
//(1)按年齡排序
int compar_struct_age(const void* e1, const void* e2)
{
return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
int main()
{
struct stu s[] = { {"zhangsan",20},{"lisi",55},{"wangwu",40} };
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), compar_struct_age);
return 0;
}
??按名字排序
#include<stdio.h>
#include<stdlib.h>
//結(jié)構(gòu)體
struct stu
{
char name[20];
int age;
};
//(2)按名字排序
int compar_struct_name(const void* e1, const void* e2)
{
//使用strcmp比較字符串
return strcmp(((struct stu*)e1)->name,((struct stu*)e2)->name);
}
int main()
{
struct stu s[] = { {"zhangsan",20},{"lisi",55},{"wangwu",40} };
int sz = sizeof(s) / sizeof(s[0]);
qsort(s, sz, sizeof(s[0]), compar_struct_name);
return 0;
}
二、冒泡模擬qusort函數(shù)實(shí)現(xiàn)
1、實(shí)現(xiàn)思路
理解了庫函數(shù)qsort()的使用后，下面我們來用冒泡排序的思想實(shí)現(xiàn)一下qsort函數(shù)，首先我們先回憶一下冒泡排序：
void bubble_sort(int arr[], int sz)
{
int i = 0;
for (i = 0; i < sz - 1; i++)//冒泡排序趟數(shù)
{
int j = 0;
for (j = 0; j < sz - i - 1; j++)//每趟冒泡排序
{
//判斷和交換
if (arr[j] > arr[j + 1])//升序
//if (arr[j] < arr[j + 1])降序
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
通過冒泡排序的參數(shù)部分我們就可以看出void bubble_sort(int arr[], int sz)冒泡排序僅支持單一類型的數(shù)據(jù)排序。想要用冒泡排序模擬實(shí)現(xiàn)qsort函數(shù)排任意類型數(shù)據(jù)，我們可以仿照qsort函數(shù)參數(shù)對(duì)冒泡排序進(jìn)行改進(jìn)：
void bubble_sort(void* base, int sz, int width, int (*cmp)(const void*e1, const void*e2))
下面我們只需要將冒泡排序中的判斷和交換部分以qsort思想實(shí)現(xiàn)即可。
2、模擬實(shí)現(xiàn)
（1）判斷部分
判斷部分我們需要使用傳入的比較函數(shù)指針，利用回調(diào)函數(shù)的機(jī)制進(jìn)行判斷，同時(shí)仿照qsort函數(shù)內(nèi)部交換思想即：比較函數(shù)cmp返回值大于零（>0）進(jìn)行交換：
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//交換
}
注釋：已知base的類型為void*，這里將void*類型轉(zhuǎn)換為char*類型是一步非常巧妙的過程，因?yàn)檗D(zhuǎn)換之后我們只需分別加上j*width 和（j+1）*width即可找到相鄰數(shù)據(jù)的起始地址，之后在利用回調(diào)函數(shù)的機(jī)制，調(diào)用外部定義的cmp比較函數(shù)，此時(shí)cmp實(shí)參為（char*)base+ j * width, (char*)base + (j + 1) * width分別為兩相鄰數(shù)據(jù)的起始位置地址，我們已知cmp函數(shù)的形參類型為void*，將得到的起始數(shù)據(jù)位置的指針轉(zhuǎn)換為相應(yīng)類型的指針再進(jìn)行比較，即可得到返回值。
（2）交換部分
交換部分我們可以獨(dú)立出一個(gè)交換函數(shù)-swap()
void swap(char* buf1, char* buf2,int width)
{
int i = 0;
for (i = 0; i < width;i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
判斷交換部分
--------------------------------------------------------------------------
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//交換
swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
}
--------------------------------------------------------------------------注釋：對(duì)于swap函數(shù)傳入實(shí)參，為兩相鄰數(shù)據(jù)的起始地址 與
待排數(shù)據(jù)元素的大小。我們回到qsort函數(shù)的定義：qsort函數(shù)是對(duì)數(shù)組元素進(jìn)行排序。數(shù)組的特點(diǎn)即是，連續(xù)存放的相同類型數(shù)據(jù)。對(duì)于相同類型的連續(xù)數(shù)據(jù)也就意味著每個(gè)數(shù)據(jù)的大小是相同的，即每個(gè)元素占用的字節(jié)大小相同。所以根據(jù)這樣一個(gè)特點(diǎn)，我們就可以通過交換相鄰數(shù)據(jù)的每個(gè)字節(jié)，以達(dá)到交換相鄰數(shù)據(jù)的目的。這樣我們就有了遍歷元素字節(jié)排序的思想：for (i = 0; i < width;i++)
（3）完整代碼與測(cè)試
//以冒泡模擬實(shí)現(xiàn)qsort
#include<stdio.h>
#include<stdlib.h>
//交換函數(shù)
void swap(char* buf1, char* buf2,int width)
{
int i = 0;
for (i = 0; i < width;i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
//冒泡實(shí)現(xiàn)
void bubble_qsort_sort(void* base, int sz, int width, int (*cmp)(const void*e1, const void*e2))
{
int i = 0;
for (i = 0; i < sz - 1; i++)//趟數(shù)
{
int j = 0;
for (j = 0; j < sz - i - 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);
}
}
}
}這樣我們就完全實(shí)現(xiàn)了用冒泡思想模擬實(shí)現(xiàn)qsort函數(shù)，并且使用規(guī)則相同，下面我們可以測(cè)試一下：
測(cè)試整數(shù)
//打印函數(shù)
void print(int arr[], int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
}
//比較函數(shù)
int compar(const void* e1, const void* e2)
{
return *((int*)e1) - *((int*)e2);
}
int main()
{
int arr[] = { 3,5,2,6,8,1,9,0,4,7 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_qsort_sort(arr, sz, sizeof(arr[0]), compar);
print(arr, sz);
return 0;
}
同樣測(cè)試結(jié)構(gòu)體也與庫函數(shù)qsort結(jié)果相同，這里就不在過多測(cè)試。
總結(jié)
以上就是對(duì)qsort函數(shù)的理解、應(yīng)用以及模擬實(shí)現(xiàn)。相信通過本章對(duì)qsort函數(shù)的解剖，你已經(jīng)對(duì)qsort函數(shù)有了更深的理解。
到此這篇關(guān)于C++ qsort函數(shù)排序與冒泡模擬實(shí)現(xiàn)流程詳解的文章就介紹到這了,更多相關(guān)C++ qsort函數(shù)排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C語言通訊錄管理系統(tǒng)的完整版本，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02
這篇文章主要介紹了C語言關(guān)鍵字union的定義和使用詳解,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-02-02
C++用指針變量作為函數(shù)的參數(shù)接受數(shù)組的值的問題詳細(xì)總結(jié)
以下是對(duì)C++中用指針變量作為函數(shù)的參數(shù)接受數(shù)組的值的問題進(jìn)行了詳細(xì)的總結(jié)介紹，需要的朋友可以過來參考下，希望對(duì)大家有所幫助2013-10-10
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)通訊錄小項(xiàng)目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-05-05
C語言統(tǒng)計(jì)輸入字符各個(gè)字母出現(xiàn)頻率的解題思路
這篇文章主要介紹了C語言統(tǒng)計(jì)輸入字符各個(gè)字母出現(xiàn)頻率的解題思路，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2015-08-08
這篇文章主要介紹了VC中刪除類的兩種操作方法,較為詳細(xì)的描述了在VC中實(shí)現(xiàn)刪除類的具體步驟,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-05-05
本篇文章是對(duì)用C語言去除字符串兩邊空字符的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++ 基礎(chǔ)編程之十進(jìn)制轉(zhuǎn)換為任意進(jìn)制及操作符重載
這篇文章主要介紹了C++ 基礎(chǔ)編程之十進(jìn)制轉(zhuǎn)換為任意進(jìn)制及操作符重載的相關(guān)資料,需要的朋友可以參考下2017-02-02
C++實(shí)現(xiàn)LeetCode(138.拷貝帶有隨機(jī)指針的鏈表)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(138.拷貝帶有隨機(jī)指針的鏈表),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
本篇文章是基礎(chǔ)篇，適合c語言剛?cè)腴T的朋友，本文對(duì)初識(shí)c語言的指針和指針變量做了簡(jiǎn)單的分析，幫助大家快速入門c語言的世界，更好的理解c語言2021-08-08