一.冒泡排序

冒泡排序是一種常見的排序方式，它可以把數(shù)組元素有序或無序的數(shù)組進(jìn)行重新排序，并使得數(shù)組中的元素從大到小或從小到大進(jìn)行排序（就像泡泡一樣）。

冒泡排序原理：

每次比較數(shù)組中的相鄰的兩個(gè)元素的值，將較小的元素排在較大的元素的前面，就可實(shí)現(xiàn)數(shù)組元素從小到大排序；每次將較大的元素排在較小的元素的前面，就可實(shí)現(xiàn)數(shù)組元素從大到小排序。

以數(shù)字1,2,7,3,9,6為例，使其從大到小排序

對上表進(jìn)行分析：

?? 第一次排序?qū)⒆畲蟮臄?shù)字移動(dòng)到第一第一元素[0]的位置，并將其它數(shù)字以次向后移動(dòng)；第二次排序中，從第二個(gè)數(shù)字開始從剩余數(shù)字中挑選最大的數(shù)字，并將其移動(dòng)到第二個(gè)位置，剩余數(shù)字依次向后移動(dòng)；以此類推，可將數(shù)字1,2,7,3,9和6從大到小排列。

代碼實(shí)現(xiàn)：

#include<stdio.h>int main() {int arr[10] = { 0 };int i = 0, j = 0, tmp = 0;for (i = 0; i < 10; i++){scanf("%d", &arr[i]);//依次輸入你想排列的數(shù)字}for (i = 9; i >= 1; i--){for (j = i; j >= 1; j--){if (arr[j] > arr[j - 1]){tmp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = tmp;}}}for (i = 0; i < 10; i++){printf("%d ", arr[i]);}return 0;return 0; }

對上述代碼進(jìn)行分析：

我們可以看到總共有6個(gè)數(shù)字元素，單卻只排序5次。在最后依次排序過程2與1交換了位置剛好滿足從大到小排列，也就是說該數(shù)組你設(shè)置了n個(gè)元素那就要排序n -1次。

那依次排序中數(shù)組中的元素交換了多少次呢？

由圖表可知，在第一次排序中，我們可以觀察到【6,9】，【9,3】，【9,7】，【9,2】，【9,1】格一次總共是五次；在第二次排序中，因?yàn)槲覀円呀?jīng)知道9為最大值并且排在了[0]位置，所以9可以不用交換了，只需交換9后面的數(shù)字元素即可，這時(shí)總共交換了4次。以此類推可知第五次只需交換一次。由此可知，每次排序之后，數(shù)組元素需交換的次數(shù)都會(huì)減一。所以在代碼實(shí)現(xiàn)中我套用了兩層循環(huán)一層for(i=9;i>=1;i--)就是要排序的次數(shù)，另一層for(j=i;j>=1;j--)就是每次排序中需交換的次數(shù)。而j>=1這個(gè)判斷條件是為了防止數(shù)組越界的。（因?yàn)槿绻鹙=0的話arr[j-1]就越界了）

二.qsort函數(shù)詳解

??? qsort函數(shù)是C語言標(biāo)準(zhǔn)庫中的一種庫函數(shù)，它的作用就是快速排序，而要使用它的話就需要引用頭文件#include<stdlib.h>。

??? qsort的函數(shù)原型：

??? void qsort (void* base,size_t num,size_t size,int (* compar) (const void*e1,const void*e2)

??? 現(xiàn)在對qsort函數(shù)原型進(jìn)行分析：

??? 1.void qsort：

??? 這個(gè)void代表qsort函數(shù)是一個(gè)無返回類型的函數(shù)。

??? 2.void* base：

??? 這個(gè)void*代表著是base的類型。base被官方解釋為指向要排序的數(shù)組的第一個(gè)對象的指針，轉(zhuǎn)換為空*。也就是說base，其實(shí)就是數(shù)組首元素的地址。

??? 具體實(shí)現(xiàn)：int values[6]={40,10,100,90,20,25};

????????????????????? qosrt(values,6,sizeof(int),compare);

??? 3.size_t num：

??? 這個(gè)size_t代表著是num的類型（size_t其實(shí)就是unsigned int 無符號(hào)整型），在官方的解釋中num是按基數(shù)指向數(shù)組中的元素?cái)?shù)，也就是說num就是你傳給qsort這個(gè)函數(shù)的數(shù)組中的元素個(gè)數(shù)

??? 具體實(shí)現(xiàn)： qosrt(values,6,sizeof(int),compare);這個(gè)6就是num。

??? 4.size_t size

??? size_t同上，size在官方的解釋中就是數(shù)組中每個(gè)元素的大小（以字節(jié)為單位）。

??? 具體實(shí)現(xiàn)： qosrt(values,6,sizeof(int),compare);這個(gè)sizeof（int）就是int類型的值在內(nèi)存中占多少個(gè)字節(jié)，因?yàn)閿?shù)組values就是int類型的數(shù)組。

??? 5.int （*compare）（const void*e1，const void*e2）

??? 現(xiàn)在對上式進(jìn)行分析。這是一個(gè)返回值類型為整型的函數(shù)指針，其中compare函數(shù)的兩個(gè)參數(shù)的類型為const void*。而在官方的解釋中這是一個(gè)指向比較兩個(gè)元素大小的函數(shù)指針。

??? 在qsort函數(shù)中的compare函數(shù)的使用方式類似于strcmp函數(shù)，qsort函數(shù)主要是通過compare函數(shù)的返回值來判斷傳入compare函數(shù)的兩個(gè)元素的值的大小關(guān)系。如果返回值小于零的話那么元素e1就小于e2；如果返回值等于零的話e1==e2；如果返回值大于零的話e1就大于e2。

??? 也就是說compare函數(shù)就是一種比較方法，用來比較傳入compare函數(shù)的兩個(gè)值的大小的。

?這個(gè)圖片就是官方給出的解釋。

綜上，qosrt的使用就是這樣的：

qsort(數(shù)組名，數(shù)組元素個(gè)數(shù)，數(shù)組每個(gè)元素的大小（以字節(jié)為單位），比較函數(shù))

代碼實(shí)現(xiàn)：

#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h>int compare(void* e1, void* e2) {return (*(int*)e1 - *(int*)e2);//把e1，e2強(qiáng)制轉(zhuǎn)換為（int*）類型的因?yàn)閭鞯綌?shù)組的元素就是int類型的。 }int main() {int arr[10] = { 0 };for (int i = 0; i < 10; i++){scanf("%d", &arr[i]);}qsort(arr, 10, sizeof(arr[0]), compare);//總結(jié)就是 qsort(數(shù)組名，數(shù)組元素個(gè)數(shù)，數(shù)組每個(gè)元素的大小（以字節(jié)為單位），比較函數(shù))for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}return 0; }

?

運(yùn)行結(jié)果：

?

三.qosrt函數(shù)的模擬實(shí)現(xiàn)

通過觀察qsort函數(shù)的代碼實(shí)現(xiàn)以及函數(shù)原型，我們可以仿照出一個(gè)類似的函數(shù)，這個(gè)函數(shù)必須要具備qsort函數(shù)的所有功能。

我先設(shè)這個(gè)函數(shù)名稱為bubble_sort，很多人可能會(huì)問，為什么我要把冒泡函數(shù)與qsort函數(shù)一起講？等會(huì)你們就知道了。

我們既然要讓bubble_sort實(shí)現(xiàn)qsort的功能那么在bubble_sort函數(shù)內(nèi)部必然有一個(gè)排序語句來幫助bubble_sort這個(gè)函數(shù)正真實(shí)現(xiàn)快速排序，而冒泡排序法就是這個(gè)函數(shù)內(nèi)部的的排序語句。但是qsort函數(shù)的模擬實(shí)現(xiàn)最主要也是最難的就是數(shù)組元素的交換，因?yàn)樗婕暗搅?strong>函數(shù)指針和強(qiáng)制類型轉(zhuǎn)換，不多bb直接上代碼然后解釋一下具體怎么交換數(shù)組元素。

代碼實(shí)現(xiàn)：

#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h>int compare(void* e1, void* e2) {return (*(int*)e1 - *(int*)e2); } void bubble_sort(int* p, size_t num, size_t size, int(*compare)(void* e1, void* e2)) {int i = 0, j = 0;for (i = num - 1; i >= 1; i--){for (j = 0; j < i; j++){if (compare((char*)p+j*size,(char*)p+(j+1)*size) > 0){int x = 0;char tmp;for (x = 0; x < size; x++){tmp = *((char*)p + j * size+x);*((char*)p + j * size+x) = *((char*)p + (j + 1) * size+x);*((char*)p + (j + 1) * size+x) = tmp;}}}} } int main() {int arr[10] = { 0 };for (int i = 0; i < 10; i++){scanf("%d", &arr[i]);}bubble_sort(arr, 10, sizeof(arr[0]), compare);for (int i = 0; i < 10; i++){printf("%d ", arr[i]);}return 0; }

為了使我們模擬實(shí)現(xiàn)的bubble_sort函數(shù)能夠排序多種類型包括整型（int，short，long，long），字符型（char）以及實(shí)型也叫浮點(diǎn)型（float，double），所以我們需要把數(shù)組元素強(qiáng)制轉(zhuǎn)換為char*類型。

在上述代碼中我們可以看到compare（(char*)p+j*size,(char*)p+（j+1）*size），這里傳過去的的是（char*）p+j*size和（char*）p+（j+1）*size，在這里如果我們只傳（char*）p是顯然行不通的，因?yàn)閜這個(gè)地址就是數(shù)組arr的首元素地址，因?yàn)槲覀冃枰粨Q數(shù)組里面的所有元素所以我們就要傳兩個(gè)相鄰的數(shù)組元素，而這兩個(gè)元素會(huì)隨著循環(huán)次數(shù)增加而改變。如j=0是（char*）p+j*size實(shí)際上就是arr[0]，（char*）p+（j+1）*size顯然就是arr[1]了，而隨著j增加傳過去的元素也會(huì)改變。（其中size就是數(shù)組元素的大小，而（char*）p加了j*size，地址p就會(huì)向后移動(dòng)j*size個(gè)字節(jié)，也就是arr[]的下標(biāo)會(huì)移動(dòng)加j）。

而*（（char*）p+j*size+x）和*（（char*）p+（j+1）*size+x）其實(shí)就是對（char*）p+j*size+x以及后者的解引用而言，這里值得注意的是x，為什么要加x？是因?yàn)閜已經(jīng)被強(qiáng)制類型轉(zhuǎn)換成了char*型的所以我們?yōu)榱私粨Q數(shù)組元素就要一個(gè)字節(jié)一個(gè)字節(jié)的交換（char類型占內(nèi)存是1個(gè)字節(jié)，int是4個(gè)字節(jié)）。而且這個(gè)加x就是使p向后位移x位。

ps：compar函數(shù)傳過去的參數(shù)應(yīng)該是兩個(gè)指針。

總結(jié)

以上是生活随笔為你收集整理的冒泡排序和qsort函数详解以及如何模拟实现qsort函数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。