qsort 函數的使用

? ? ? ?首先qsort函數是使用快速排序算法來進行排序的，下面我們打開官網來查看qsort是如何使用的。

這里有四個參數，首先base 是至待排序的數組的首元素的地址，num 是值這個數組的元素個數，size 是指每個元素的大小，最后是一個函數指針（用來比較兩個元素的不同，其中這個函數需要有返回值，當返回值小于0時p1需要放在p2前面，等于0時p1和p2不用改變位置，當返回值大于0時，p1需要放在p2的后面）由此可見，這個函數需要我們自己去編寫，然后通過函數指針來調用。

下面我們來看看qsort的實踐效果：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>typedef struct Stu
{char name[20];int age;
}Stu;int cmp_array(const void* p1,const void* p2)
{return *(int*)p1 - *(int*)p2;
}int cmp_stu_name(const void* p1, const void* p2)
{return strcmp(((Stu*)p1)->name, ((Stu*)p2)->name);
}int cmp_stu_age(const void* p1, const void* p2)
{return ((Stu*)p1)->age - ((Stu*)p2)->age;
}void PrintArray(int arr[], int sz)
{for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}void PrintStu(Stu* s, int sz)
{for (int i = 0; i < sz; i++){printf("%s %d", s[i].name, s[i].age);printf("\n");}
}int main()
{Stu s[3] = { {"zhangsan",18},{"lisi",19},{"sunwu",15} };int sz = sizeof(s) / sizeof(s[0]);int arr[10] = { 4,8,5,7,9,6,2,0,1,3 };int sz2 = sizeof(arr) / sizeof(arr[0]);qsort(s, sz, sizeof(s[0]), cmp_stu_name);PrintStu(s, sz);printf("\n");qsort(s, sz, sizeof(s[0]), cmp_stu_age);PrintStu(s, sz);printf("\n");qsort(arr, sz2, sizeof(arr[0]), cmp_array);PrintArray(arr, sz2);printf("\n");return 0;
}

使用C語言模擬qsort

? ? ? ?這里我們使用冒泡排序算法進行排序，使用C語言來模擬qsort函數。
? ? ? ?首先我們來回顧冒泡排序算法，有兩個要點一個是排序的趟數，另一個是每一趟排序的次數。這里以升序為例：

void bubble_sort(int arr[], int sz)
{for (int i = 0; i < sz - 1; i++){for (int 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;}}}
}

然后來模擬qsort函數呢？首先qsort函數幾乎對任何數據都可以排序，所以我們的bubble_sort函數要做出相應調整，然后設計形參呢？對任何數據進行排序，也就是說數據的類型和大小都是不確定的，這樣的話，我們可以使用size_t來作為數據類型，用void來接收不同類型的指針，實在不會的，我們可以參考qsort 函數來設計的。

void base 接收待排序的首元素的地址，size_t num 和 size_t size 來接收元素個數和元素大小，最后就是最重要的函數設計了。

void bubble_sort(void* base, size_t num, size_t size, int (*compar) (const void* p1, const void* p2))

設計好形參，我們來考慮一下函數的主體部分，首先趟數是不改變的，每趟的次數也不用改變，畢竟我們還是使用冒泡排序算法，這樣的話，還有最后一個就是if這個判斷語句，應為我們無法直接通過像上面一樣對兩個數進行直接比較，我們需要調用函數來進行比較，也就是compar函數。

那有個問題，我們如何來寫compar 函數的指針呢？這個指針不能大也不能小，否則就無法準確比較或者會產生越界行為，這樣我們可以使用char* 為什么呢？首先我們需要兩個兩個數據來進行一一比較，這樣我們需要知道準確的地址，必須是恰好指向每個元素的地址，而char 剛好就是一個字節，只要準確地進行指針加法運算就能得到這個元素地地址。

if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0)

還有個問題，我們怎么交換數據呢？其實和上面的理由差不多由于數據的類型不同，他們的大小也不同。這時我們可以使用char 因為char 是最小的數據類型了，也就是一個字節，無論數據是幾個字節，都是char 的倍數也就是說都可以用一個字節的倍數來表示，這樣的話，我們只需要知道數據類型的大小（size) 就可以來通過循環遍歷來一個字節一個字節來進行進行交換就可以了,我們可以封裝一個函數swap。

void swap(char* p1, char* p2, size_t size)
{int i = 0;while (i < size){char tmp = *(p1 + i);*(p1 + i) = *(p2 + i);*(p2 + i) = tmp;i++;}
}

那么我們最后得到的bubble_sort函數如下：

void bubble_sort(void* base, size_t num, size_t size, int (*compar) (const void* p1, const void* p2))
{for (int i = 0; i < num - 1; i++){for (int j = 0; j < num - 1 - i; j++){if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0){swap((char*)base + j * size, (char*)base + (j + 1) * size);}}}
}

我們來演練一下，看看效果是不是和qsort有著一樣的效果：

代碼如下：

#include <stdio.h>
#include <string.h>typedef struct Stu
{char name[20];int age;
}Stu;int cmp_array(const void* p1,const void* p2)
{return *(int*)p1 - *(int*)p2;
}int cmp_stu_name(const void* p1, const void* p2)
{return strcmp(((Stu*)p1)->name, ((Stu*)p2)->name);
}int cmp_stu_age(const void* p1, const void* p2)
{return ((Stu*)p1)->age - ((Stu*)p2)->age;
}void PrintArray(int arr[], int sz)
{for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}void PrintStu(Stu* s, int sz)
{for (int i = 0; i < sz; i++){printf("%s %d", s[i].name, s[i].age);printf("\n");}
}void swap(char* p1, char* p2, size_t size)
{int i = 0;while (i < size){char tmp = *(p1 + i);*(p1 + i) = *(p2 + i);*(p2 + i) = tmp;i++;}
}void bubble_sort(void* base, size_t num, size_t size, int (*compar) (const void* p1, const void* p2))
{for (int i = 0; i < num - 1; i++){for (int j = 0; j < num - 1 - i; j++){if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0){swap((char*)base + j * size, (char*)base + (j + 1) * size, size);}}}
}int main()
{Stu s[3] = { {"zhangsan",18},{"lisi",19},{"sunwu",15} };int sz = sizeof(s) / sizeof(s[0]);int arr[10] = { 4,8,5,7,9,6,2,0,1,3 };int sz2 = sizeof(arr) / sizeof(arr[0]);bubble_sort(s, sz, sizeof(s[0]), cmp_stu_name);PrintStu(s, sz);printf("\n");bubble_sort(s, sz, sizeof(s[0]), cmp_stu_age);PrintStu(s, sz);printf("\n");bubble_sort(arr, sz2, sizeof(arr[0]), cmp_array);PrintArray(arr, sz2);printf("\n");return 0;
}