引入

我們在學習排序的時候，第一個接觸到的應該都是冒泡排序，我們先來復習一下冒泡排序的代碼，來作為一個鋪墊和引入。

代碼如下：

#include<stdio.h>void bubble_sort(int *arr, int sz)
{int i = 0;for (i = 0; i < sz - 1; i++){int j = 0;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;}}}
}int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9,0 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

很簡單的一種排序方法，但我們可以發現一個問題，那就是冒泡排序不夠通用，它只能用于整型數組的排序，如果我要排序float類型，或者排序結構體要怎么辦呢。

下面，我們就來介紹一個比較萬能的排序函數，qsort函數

簡介

先來簡單了解一下qsort函數的各個部分

語法格式

它的固定格式如下：

int cmp_int(const void* e1, const void* e2)
{}

注意：他的格式是固定的，比如返回值類型必須是int類型，形參的類型也是固定的，只有返回值的部分是自己編寫的，也就是說，當返回值類型不是int的時候，我們需要進行強制類型轉換或者手動將其返回值改成int類型
（這在下文會詳細說明）

參數解釋

在調用函數時，傳參格式如下：

void qsort(void* base,size_t num,size_t width,int (*cmp)(const void* e1, const* e2)
);

可以看一下這張圖，里面講解了qsort函數的各個參數分別表示的是什么，
在這里插入圖片描述

base:起始位置,待排序數組的首元素地址 num：數組的大小，單位是元素，待排序數組的元素個數
width：元素大小，單位是字節，待排序數組的單個元素的大小 cmp：函數指針（比較函數：compare
function），比較兩個元素的函數的地址
解釋：對于不同類型元素的比較的方法是不同的，此處就是將兩個元素的比較方法寫成函數，傳到qsort函數中，然后使用指針cmp進行調用
e1和e2可以簡單地認為是要比較的兩個元素的地址，（下面會做補充說明）

對void *的解釋

先拋出一個問題：下面這個代碼有什么問題

int main()
{int a = 0;int *pa = &a;char* pc = &a; return 0;
}

問題就是：第四行和第五行：此處雖然可以存儲，但會報警告：從“int *”

到“char *”的類型不兼容。

那么，我們這時就可以使用，void *（無指針類型）來解決這個問題

void* p = &a;
//void *類型的指針可以接收任意類型的地址

此處就可以很好地解釋qsort函數的第一個參數：void* base

補充：

對于void *類型的指針無法進行解引用
因為不知道進行解引用之后，要訪問幾個字節
同理，也無法進行無符號型的指針與整數的運算

那么，在qsort函數中，如何比較e1與e2呢
可以將二者強制轉換成所需的類型（代碼中會提到這一點）

返回值

下圖是英文版的介紹
在這里插入圖片描述

對qsort函數返回值的解釋
當e1<e2,返回值小于0
當e1=e2，返回值等于0
當e1>e2 返回值大于0

提示：所以可以利用這個規律將不是int類型的返回值手動變成int型（下文float類型那里會詳細說明）

使用

此處我們舉三個例子，分別是int、float和結構體類型變量的比較

int類型

明確需要

我們需要三個函數：main函數（調用test函數），test函數（調用qsort函數、打印最終結果），和cmp_int函數（提供元素的比較方法）

test函數

1.創建數組
2.計算大小
3.調用qsort函數
4.打印最終結果

cmp_int函數

照著前面的固定格式，然后返回值那里就直接用

（這里我一寫*，他就識別成斜體，大家直接看下面的代碼吧…)

最終代碼

#include<stdlib.h>int cmp_int(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;}void test1()
{int arr[10] = { 1,2,3,4,5,6,7,8,9,0 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_int);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}int main()
{test1();return 0;
}

還是比較好理解的，就不做過多解釋了

float類型

對于cmp_float函數的說明

問題

我們知道cmp_float函數的返回值必須是int類型的，但,

*(float*)e1 - *(float*)e2

的返回類型是float類型，在運行時會報一個警告：return”: 從“float”轉換到“int”，可能丟失數據，
此處提供兩種解決方法：

1.使用if else語句手動判斷大小并根據情況分別返回一個負數、0、一個正數
代碼如下：

if (*(float*)e1 > *(float*)e2)
{return 1;
}
else if (*(float*)e1 == *(float*)e2)
{return 0;
}
else
{return -1;
}

2.使用強制類型轉換，轉換成int類型

最終代碼


#include<stdlib.h>int cmp_float(const void* e1, const void* e2)
{return *(float*)e1 - *(float*)e2;
}void test2()
{float f[] = { 9.0, 8.0, 7.0, 6.0 ,5.0 ,4.0 ,3.0, 2.0, 1.0 };int sz = sizeof(f) / sizeof(f[0]);qsort(f, sz, sizeof(f[0]), cmp_float);int i = 0;for (i = 0; i < sz; i++){printf("%.3f ", f[i]);}
}int main()
{test2();return 0;
}

結構體類型

如果我們想要排序結構體類型的變量，那就很有意思了，我們一步一步來分析

明確需要

main函數、test3函數、cmp_stu函數
下面我們重點解釋一下test3函數和cmp_stu函數

test3函數

1.創建結構體類型的數組，并初始化
2.求數組元素個數
3.調用qsort函數，里面包含了cmp_stu函數的地址，即調用cmp_stu函數

cmp_stu函數

照貓畫虎

我們按照前面的兩個例子寫出來的應該是

int cmp_struct(const void* e1, const void* e2)
{return *(struct*)e1 - *(struct*)e2;}

但這么寫是錯誤的，因為結構體是復雜對象，無法直接用 > 或 < 進行比較，那么我們就需要確定是用哪個成員去作為比較的標準
再通過->來訪問相應的成員

下面給出兩個例子，此處分別以年齡age作為排序標準和以名字name來排序，

cmp_stu_by_age函數

將e1和e2從void* 類型轉換成結構體類型指針，然后再通過->訪問相應的成員
然后直接讓二者相減即可，此處在強制類型轉換時別忘了寫上struct就行

int cmp_stu_by_age(const void* e1, const void* e2)
{return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;}

這個函數的實現還是與cmp_int函數有一些相似的，

cmp_stu_by_name函數

提示：此處比較的是字符串，同樣不能用 > < 來進行比較
而是要用strcmp函數進行比較，包含頭文件<string.h>

int cmp_stu_by_name(const void* e1, const void* e2)
{return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);}

最終代碼

#include<stdlib.h>struct Stu
{char name[40];int age;
};int cmp_stu_by_age(const void* e1, const void* e2)
{return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;}int cmp_stu_by_name(const void* e1, const void* e2)
{return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);提示，此處比較的是字符串，同樣不能用 > < 來進行比較而是要用strcmp函數進行比較
}void test3()
{struct Stu s[3] = { {"zhang", 20},{"li", 30},{"wang", 40} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}int main()
{test3();return 0;
}

三個例子到這里就介紹結束了，其實這樣看下來也不是很難理解。
下面我們來學習qsort函數的模擬實現，也就是優化bubble_sort函數，使它能排序任意類型的元素

模擬實現

引入：

此處提出一個問題：如果說，我不想使用qsort函數，我就想使用冒泡函數，那我要如何改進它，才能達到和qsort函數相同的效果呢？

函數調用方面的改進

接收地址

如果說想讓冒泡排序函數具有排序任意類型元素的功能，那么首先，它就應該能接收任意類型元素的地址（類似于qsort中的base參數）

元素個數

函數需要知道要排序多少個元素，所以就需要傳入數組的大小（類似num參數）

元素大小（寬度）

知道了待排序數組的起始位置和元素個數后，我們需要對數組中的元素進行移動操作，那么我們就需要知道元素的大小是什么

簡易版框架如下：

void bubble_sort(void* base, int sz, int width)
{int i = 0;//次數for (i = 0; i < sz; i++){//每次需要比較的元素對數int j = 0;for (j = 0; j < sz - 1 - i; j++)//比較兩個元素{}}
}

疑問1：

基本框架搭建好了，那我們要如何比較兩個元素呢，我們又不知道他們的類型？

所以我們在傳參的時候，還需要將兩個元素的比較方法（函數）一并傳進bubble_sort函數中，也就是第四個參數

首先，要傳入的肯定是函數的地址，
其次，我們需要返回一個值來告訴我們比較的結果是什么（此處類似qsort函數的返回值）
最后，對于要比較的兩個元素，因為要求函數具有通用性，所以參數類型就是void *類型

代碼如下：

void bubble_sort(void* base, int sz, int width, int(*cmp)(void* e1,void* e2) )
{int i = 0;//次數for (i = 0; i < sz; i++){//每次需要比較的元素對數int j = 0;for (j = 0; j < sz - 1 - i; j++)//比較兩個元素{if(cmp()>0)//交換if(cmp()>0)//交換{}}}}
}

疑問2：if語句

if(cmp()>0)//交換{}

我們知道這個語句是比較兩個元素，那我們怎么找到這倆個元素呢？

我們知道，base就是首元素的地址，

想法1

那么有人想通過加減整數來找到后面的元素，這個問題在我前面的文章提到過：因為元素是void*類型的，不知道元素大小，無法與整數進行運算

想法2

那么又有人想：將base傳換成（int*）類型再運算不就行了嗎，
還是不對，因為我們不知道傳進來的參數究竟是什么類型，所以我們不能假定他的類型

想法3

小明這時候提出來：我們已經知道了每個元素的大小：width，那可不可以先把base轉換成char*類型，再加上每個元素的字節大小width呢？

這么做就可以了，
因為char*大小是一個字節，每次移動width個字節，就進入到下一個元素中了

if語句代碼如下：

if(cmp((char*)base+ j*width, (char*)base +(j+1)*width)>0)//交換
{}

疑問3：怎么交換

這里先創建一個swap函數用于兩個元素的交換

void Swap(char*buf1, char*buf2)
{}void bubble_sort(void* base, int sz, int width)
{int i = 0;//次數for (i = 0; i < sz; i++){//每次需要比較的元素對數int j = 0;for (j = 0; j < sz - 1 - i; j++)//比較兩個元素{if(cmp((char*)base+ j*width, (char*)base +(j+1)*width)>0)//交換{Swap((char*)base + j * width, (char*)base + (j + 1) * width);}}}
}

但是，我們仔細看，Swap函數接收的參數類型是char*，一個字節大小，如果我這個元素是8個字節類型，要怎么交換呢，
所以如果按照一個字節一個字節這么交換的方式，我們就需要知道要交換的元素的字節大小（width），以及要交換幾次

代碼如下：

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++;}
}

簡單實現（int類型）

完整代碼如下：

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++;}
}void bubble_sort(void* base, int sz, int width, int (*cmp)(void*e1, void*e2))
{int i = 0;//次數for (i = 0; i < sz; i++){//每次需要比較的元素對數int j = 0;for (j = 0; j < sz - 1 - i; j++)//比較兩個元素{if(cmp((char*)base+ j*width, (char*)base +(j+1)*width)>0)//交換{Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}int cmp_int(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}void test4()
{int arr[10] = { 1,2,3,4,5,6,7,8,9,0 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
}int main()
{test4();return 0;
}