C語言中qsort函數(shù)的介紹與用法實例
一.qsort函數(shù)是什么
我們可以使用 搜索庫函數(shù)網(wǎng)址或者MSDN軟件進行查找。
qsort()函數(shù)：快速排序的函數(shù) -引用stdlib.h頭文件
參數(shù)說明：
void qsort (
void* base, //要排序的目標(biāo)數(shù)組
size_t num, //待排序的元素個數(shù)
size_t width, //一個元素的大小，單位是字節(jié)
int(*cmp)(const void* e1, const void* e2)
);
其中cmp是函數(shù)指針，cmp指向的是：排序時，用來比較兩個元素的函數(shù)。需要自己編寫。
返回值：
二.使用qsort排序-以升序為例
關(guān)于void*型指針：
void*：無具體類型的指針 能夠接收任意類型的地址
缺點：不能進行運算。不能+-整數(shù)，不能解引用
int a = 0; float f = 5.5f; void* p1 = &a; void* p2 = &f; p1 = p1+1; //err
1.整形數(shù)組排序
注意：
1.比較函數(shù)的參數(shù)類型為void* ，我們要進行強制類型轉(zhuǎn)換！且要解引用才能得到對應(yīng)的值！
2.若我們想排成降序，只需要寫成e2-e1即可
void Print(int* arr, int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%d ", *(arr + i));
}
printf("\n");
}
//比較整形
//注意類型時void* 所以要強制類型轉(zhuǎn)化，還要解引用才是對應(yīng)的值?。?！
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
void test1()
{
int arr[] = { 9,8,7,6,7,5,4,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_int);
Print(arr, sz);
}
2.字符數(shù)組排序
注意使用sizeof()操作符和strlen()函數(shù)的區(qū)別
//注意要要強制類型轉(zhuǎn)換！！ 要解引用?。?！ 本質(zhì)上是比較Ascii值
int cmp_char(const void* e1, const void* e2)
{
return *(char*)e1 - *(char*)e2;
}
void test4()
{
char arr[] ="mango";
//若使用sizeof計算長度：
//int sz = sizeof(arr) / sizeof(arr[0]); //6
//qsort(arr, sz-1, sizeof(arr[0]), cmp_float);
//因為sizeof把\0也算進去了，所以計算出來的值比字符串本身長度多1
int sz = strlen(arr); //5
qsort(arr, sz, sizeof(arr[0]), cmp_char);
printf("%s\n",arr);
}
3.字符指針數(shù)組排序
先看看下面這段程序有沒有問題？
int cmp_chars(const void* e1, const void* e2)
{
return strcmp((char*)e1, *(char*)e2);
}
void test2()
{
char* arr1 = "abc";
char* arr2 = "wcad";
char* arr3 = "cab";
char* p[3] = { arr1,arr2,arr3 };
int sz = sizeof(p) / sizeof(p[0]);
qsort(p, sz, sizeof(p[0]), cmp_chars);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%s\n", p[i]);
}
}
打印出來發(fā)現(xiàn)：結(jié)果是錯誤的！
->調(diào)試后發(fā)現(xiàn)：e2存放的是p的地址（char**類型），e1存放的是p指向的下一個元素的地址（char**類型）
對于這種寫法，傳進去的是p的地址，strcmp()會將p地址對應(yīng)的內(nèi)容轉(zhuǎn)化成字符串，也就是將p中arr1，arr2，arr3的地址轉(zhuǎn)化成字符串
實際上應(yīng)該傳p地址空間中arr1，arr2的地址，這樣strcmp()才能找到arr1和arr2對應(yīng)的字符串，因此得先把e1，e2轉(zhuǎn)化成char**，這樣解引用以后才是一個char*的地址
原因：把p傳給qsort，p是數(shù)組名->首元素地址，元素類型為char*>，所以p的類型為：char**類型。 所以e1 和e2也要強制類型轉(zhuǎn)化為char**，解引用e1，e2才是對應(yīng)字符串的地址！
正解：
int cmp_chars(const void* e1, const void* e2)
{
return strcmp(*(char**)e1, *(char**)e2);
}
void test2()
{
char* arr1 = "abc";
char* arr2 = "wcad";
char* arr3 = "cab";
char* p[3] = { arr1,arr2,arr3 };
int sz = sizeof(p) / sizeof(p[0]);
qsort(p, sz, sizeof(p[0]), cmp_chars);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%s\n", p[i]);
}
4.結(jié)構(gòu)體數(shù)組排序
比較年齡->實際比較的是整形
比較名字->實際比較的是字符串->使用strcmp函數(shù)，不能使用 == 判斷
struct Stu
{
int age;
char name[20];
};
//比較結(jié)構(gòu)體中元素的年齡
int cmp_age(const void* e1, const void* e2)
{
//本質(zhì)是比較整形
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
//比較名字
int cmp_name(const void* e1, const void* e2)
{
//本質(zhì)是字符串比較->使用strcmp函數(shù)
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}
void test2()
{
//創(chuàng)建結(jié)構(gòu)體數(shù)組，用大括號初始化
struct Stu s[3] = { {19,"Mango"},{18,"Lemon"},{20,"Hello"} };
int sz = sizeof(s) / sizeof(s[0]);
//以年齡排
qsort(s, sz, sizeof(s[0]), cmp_age);
printf("%s %d ",s[0].name,s[0].age);
printf("%s %d ", s[1].name, s[1].age);
printf("%s %d ", s[2].name, s[2].age);
printf("\n");
//以姓名排
qsort(s, sz, sizeof(s[0]), cmp_name);
printf("%s %d ", s[0].name, s[0].age);
printf("%s %d ", s[1].name, s[1].age);
printf("%s %d ", s[2].name, s[2].age);
printf("\n");
}
5.浮點型數(shù)組排序
注意：比較函數(shù)中，返回類型是int，最后相減的值要強制類型轉(zhuǎn)化為int ，但這也會造成錯誤，建議使用方法2.
//寫法1：可能會出錯
// 原因： 0.2 -0.1 = 0.1 強制類型轉(zhuǎn)化為int后 結(jié)果為0
//int cmp_float(const void* e1, const void* e2)
//{
// //返回類型是int 所以相減后的結(jié)果要強制類型轉(zhuǎn)化
// return (int)(*(float*)e1 - *(float*)e2);
//}
//寫法2：對應(yīng)上qsort的返回值
int cmp_float(const void* e1, const void* e2)
{
if ((*(float*)e1 - *(float*)e2) > 0.00000)
return 1;
else if ((*(float*)e1 - *(float*)e2) == 0.000000)
return 0;
else
return -1;
}
void test3()
{
float arr[5] = { 5.01f,5.01f,0.02f,0.01f,5.001f };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_float);
int i = 0;
for (i = 0; i < sz; i++)
{
printf("%f ", arr[i]);
}
}
三.使用冒泡排序思想模擬實現(xiàn)qsort函數(shù)
1.什么是冒泡排序：
主要思想：相鄰的兩個元素進行比較
對于冒泡排序： n個元素 共進行n-1趟冒泡排序。一趟可以使一個元素在特定位置上，每趟排序可以少比較一個元素
但是冒泡排序只能排序整形
2.冒泡排序代碼
void BubbleSort(int* arr, int sz)
{
int i = 0;
int j = 0;
int flag = 1;//假設(shè)一開始有序
//共進行sz-1趟
for (i = 0; i < sz-1; i++)
{
// 每一趟
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = 0;
}
}
if (flag == 1)
{
break;
}
}
}
int main()
{
int arr[10] = { 2,3,6,7,9,0,0,3,2,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
BubbleSort(arr, sz);
return 0;
}
3. 使用冒泡排序思想模擬實現(xiàn)qsort函數(shù)
qsort庫函數(shù)使用的是什么參數(shù)，我們設(shè)計的函數(shù)就使用什么參數(shù)！
1.為何將base強制類型轉(zhuǎn)化為char*型指針：
原因：char* 指針+1跳過一個字節(jié)，+width：跳過width個字節(jié)，指向下一個元素。轉(zhuǎn)化為其他類型不合適
2. 交換函數(shù)：還要把寬度（每個元素所占字節(jié)數(shù)）傳過去
因為交換的時候是傳地址，所以要知道元素的寬度，一個字節(jié)一個字節(jié)的交換 ，這樣也證明了使用char*指針的好處！
3.(char*)base + j * width, (char*)base + (j + 1) * width,
當(dāng)j = 0時：比較的是第一個元素和第二個元素
j = 1時，比較的是第二個元素和第三個元素
.... 很妙的寫法
//交換 --一個字節(jié)一個字節(jié)的交換，共交換width次
void Swap(char* buf1, char* buf2, size_t width)
{
size_t i = 0;
for (i = 0; i < width; i++)
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1++;
buf2++;
}
}
void my_BubbleSort(void* base, size_t num,size_t width, int(*cmp)(const void* e1, const void* e2))
{
//冒泡排序
//若要排序n個元素，只需要進行n-1趟
//每一趟可以少比較一個元素，每一趟可以使一個元素在確定的位置上
//num：要排序元素的個數(shù) 類型是size_t
//num是無符號數(shù) 防止產(chǎn)生警告 所以i和j也定義為size_t
// size_t == unsigned int
size_t i = 0;
size_t j = 0;
//共進行num-1趟
for (i = 0; i < num; i++)
{
//每一趟
for (j = 0; j < num - 1 - i; j++)
{
//比較
//傳地址
//相鄰兩個元素比較 width:寬度，每個元素所占字節(jié)
//排成升序
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{
//交換兩數(shù)
Swap( (char*)base + j * width, (char*)base + (j + 1) * width, width );
}
}
}
}
當(dāng)然 ，交換也可以使用庫函數(shù)memcpy
dest：目標(biāo)空間
src：要拷貝到目標(biāo)空間的字符 -因為不作修改，所以可以用const修飾
count：字節(jié)數(shù)
char tmp [30]; //防止結(jié)構(gòu)體類型之類的類型 臨時空間 memcpy(tmp, (char*)base + j * size, size); memcpy( (char*)base + j * size, (char*)base + (j + 1) * size, size); memcpy( (char*)base + (j + 1) * size, tmp, size);
總結(jié)
到此這篇關(guān)于C語言中qsort函數(shù)的介紹與用法的文章就介紹到這了,更多相關(guān)C語言中qsort函數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在C語言中,sizeof()是一個判斷數(shù)據(jù)類型或者表達(dá)式長度的運算符,下面這篇文章主要給大家介紹了關(guān)于C語言中sizeof運算符的一個陷阱的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-11-11
學(xué)習(xí)二維動態(tài)數(shù)組指針做矩陣運算的方法
這片文章介紹了如何利用二維動態(tài)數(shù)組指針做矩陣運算,需要的朋友可以參考下2015-07-07
堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序2022-02-02
這篇文章主要介紹了C語言中將日期和時間以字符串格式輸出的方法,分別是ctime()函數(shù)和asctime()函數(shù),注意參數(shù)區(qū)別,需要的朋友可以參考下2015-08-08
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)騎士飛行棋，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
C++結(jié)構(gòu)體數(shù)組詳細(xì)解析
定義結(jié)構(gòu)體數(shù)組和定義結(jié)構(gòu)體變量類似，定義結(jié)構(gòu)體數(shù)組時只需聲明其為數(shù)組即可2013-10-10
C++標(biāo)準(zhǔn)之(ravalue reference) 右值引用介紹
臨時對象的產(chǎn)生和拷貝所帶來的效率折損，一直是C++所為人詬病的問題,下面簡單地介紹一下Copy Elision、RVO，對此不感興趣的可以直接跳過2012-11-11
這篇文章主要介紹了C語言如何正確的終止正在運行的子線程，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-02-02
這篇文章主要介紹了C++ 流插入和流提取運算符的重載的實現(xiàn),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12
C++11中的智能指針shared_ptr、weak_ptr源碼解析
本文是基于gcc-4.9.0的源代碼進行分析，shared_ptr和weak_ptr是C++11才加入標(biāo)準(zhǔn)的,僅對C++智能指針shared_ptr、weak_ptr源碼進行解析，需要讀者有一定的C++基礎(chǔ)并且對智能指針有所了解2021-09-09