【C語言】qsort的秘密

一，本文目標?

qsort函數可以對任意類型數據甚至是結構體內部的數據按照你想要的規則排序，它的功能很強大，可是為什么呢？

我將通過模擬實現qsort函數來讓你對這整個過程有一個清晰的深刻的理解。

二，qsort函數原型

void qsort (void* base,//要排序的對象的第一個元素的首地址size_t num, //對象的個數size_t size,//每一個對象的大小 Size in bytesint (*compar)(const void*,const void*));//Pointer to a function that compares two elements.（并且這個函數要自己寫）

????????qsort函數底層通過快速排序進行，但是這并不是我們感興趣的點，我想要知道qsort為什么可以對任意類型數據進行排序，與它用什么排序算法排序沒有關系，所以，我們用相對簡單的冒泡排序來代替快速排序的算法，把冒泡排序賦予可以對任意類型數據進行排序的強大功能。

三，冒泡排序——大數沉底，小數上浮

?對于冒泡排序，其基本思想是大數沉底，小數上浮；

這里直接給出源碼：

void Bubble_sort(int arr[], int size)
{int j,i;for (i = 0; i < size-1;i++)//排序趟數等于元素個數-1{int f = 0;for (j = 0; j < size - 1 - i; j++)//每一趟都有一個元素復位，需要排序的次數每次-1{if ( arr[j] > arr[j+1] ){int tem = arr[j];arr[j] = arr[j+1];arr[j+1] = tem;f = 1;}}if (f == 0)	{break;}}

3.1相對于qsort，冒泡排序的局限性

????????只能排序整形數據?

四，兩個問題：

4.1不定類型比較問題

? ? ? ? 1.對于if內部的判斷，雖然字符型可以用 >,<,= 比較，但是對于字符串類型，無法通過常規方法比較；

4.2不定類型交換問題

? ? ? ? 2.對于交換部分，由于不同元素的類型不同，占用的內存空間也不同，如何判斷傳入數據的類型，并實現兩個數據的交換呢？

五，改造冒泡排序

我們將自己模擬實現的qsort函數稱my_qsort，實現如下：


void my_qsort(void* base,size_t sz,size_t width,int (*cmp)(const void* p1,const void* p2))//cmp 是函數指針，在my_sort中被多次調用
{//它指向的函數是int_cmp，int_cmp就是回調函數int i = 0;for(i = 0;i < sz - 1;i++)//趟數不變{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);}}}
}

5.1不同類型比較

我們定義一個cmp函數來實現比較：

5.1.1cmp實參

我們傳入排序的數組的首元素地址base，將base強制類型轉化為 char* 類型，這樣base與整數的運算就只會跨過這個整數個字節；

如果再知道每個元素的大小（長度），那么我們就可以精確的訪問到每個元素了；

怎么理解呢？?

?e.g.1:對于int

?圖中的base指針的位置是?j == 1的位置

?e.g.2:對于char

?圖中的base指針的位置是 j?== 5 的位置?

5.1.2cmp形參

int int_cmp(const void* p1,const void* p2)
{return *(int*)p1 - *(int*)p2;
}

由于比較的對象是整型，所以定義一個比較整形的函數，void* 類型不能直接解引用，所以將p1，p2強制類型轉化，將兩數相減返回。

5.2不定類型交換問題

定義交換函數Swap?

void Swap(char* buf1,char* buf2,int width)//按字節逐個交換
{for(int i = 0;i < width;i++){char tem = *buf1;*buf1 = *buf2;*buf2 = tem;buf1++;//如果是整型，則要遍歷四個字節buf2++;}
}

這時候，我們就知道定義width的意義了，對于一個數據類型，我們雖然不知道它的類型，但是我們可以根據它的長度，一個一個字節地交換數據。

整體代碼運行

對于所有類型，我們的冒泡排序都可以排序了，它的作用與庫函數qsort一致，仍然需要我們自己寫cmp函數：；

對int型數據的排序：

#include<stdio.h>
#include<string.h>
int int_cmp(const void* p1,const void* p2)
{return *(int*)p1 - *(int*)p2;
}
void Swap(char* buf1,char* buf2,int width)//按字節逐個交換
{for(int i = 0;i < width;i++){char tem = *buf1;*buf1 = *buf2;*buf2 = tem;buf1++;//如果是整型，則要遍歷四個字節buf2++;}
}void my_qsort(void* base,size_t sz,size_t width,int (*cmp)(const void* p1,const void* p2))//cmp 是函數指針，在my_sort中被多次調用
{//它指向的函數是int_cmp，int_cmp就是回調函數int i = 0;for(i = 0;i < sz - 1;i++)//趟數不變{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);}}}
}void test1(void)
{int arr[] = {2,5,8,9,6,3,1,4,7,0};int sz = sizeof(arr)/sizeof(arr[0]);my_qsort(arr,sz,sizeof(arr[0]),int_cmp);for(int i = 0;i < sz;i++){printf("%d ",arr[i]);}
}int main()
{test1();return 0;
}

對于結構體類型，也可根據結構體內部某一元素的特征排序：

結構體類型

對結構體內的int型數據排序：


struct stu
{char name[20];int age;
};int struct_cmp_by_age(const void* p1,const void* p2)
{return ((struct stu*)p1)->age - ((struct stu*)p2)->age;
}void test2(void)
{struct stu arr[] = {{"zhangsan",18},{"lisi",25},{"wangwu",30},{"xiaoming",40}};int sz = sizeof(arr)/sizeof(arr[0]);my_qsort(arr,sz,sizeof(arr[0]),struct_cmp_by_age);for(int i = 0;i < sz;i++){printf("%s %d\n",arr[i].name,arr[i].age);}
}int main()
{test2();return 0;
}

對結構體內的char型數據排序：


struct stu
{char name[20];int age;
};int struct_cmp_by_name(const void* p1,const void* p2)
{return strcmp(((struct stu*)p1)->name,((struct stu*)p2)->name);
}void test3(void)
{struct stu arr[] = {{"zhangsan",18},{"lisi",25},{"wangwu",30},{"xiaoming",40}};int sz = sizeof(arr)/sizeof(arr[0]);my_qsort(arr,sz,sizeof(arr[0]),struct_cmp_by_name);for(int i = 0;i < sz;i++){printf("%s %d\n",arr[i].name,arr[i].age);}
}int main()
{//test1();//test2();test3();return 0;
}

1.對字符串的比較用到<string.h>中的strcmp函數，而它的返回值正好符合qsort函數第四個參數：函數的要求?

第一個字符串大于第二個，strcmp返回大于0的數，對應qsort函數要求第四個函數的返回值大于0，表示第一個參數大一第二個。?

本文回顧?