文章目錄

前言
一、冒泡排序
二、冒泡排序的局限性
三、qsort函式的使用及優點
四、利用冒泡排序模擬實作qsort函式
總結

前言

排序是我們日常撰寫程式經常可以用到的，冒泡排序也是我們最常見的排序方法，在這里我們分析一下冒泡排序，以及引入我們今天的主角----->C語言庫函式之快速排序的qsort函式

一、冒泡排序

首先我們先引入冒泡排序的代碼:

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

幾條重要的代碼決議：

1.計算陣列元素的個數

2.冒泡排序回圈的趟數

就我們目前的代碼，sz的數值為10，那么如果排序好9個數字，剩余的那1個數字肯定也是排好序的了，所以可以知道冒泡排序的趟數要比元素個數少1

3. 冒泡排序的元素個數

就我們目前的代碼，sz的數值為10，每一趟冒泡排序都可以排序好一個數字，所以下次回圈的元素個數要-1，把排序好的那個數字剔除掉，將剩余的元素進行下一次冒泡排序

4.比較判斷

如上代碼我們是將陣列元素升序排列，所以判斷是不是有前面的元素比后面的元素小的這種情況，如果有進入 if 陳述句，進行元素的交換

二、冒泡排序的局限性

如我們上圖的代碼中比較元素大小的代碼

我們上圖撰寫的代碼僅限于比較整型元素，如果我們把整型arr陣列改成--->字符arr陣列或者是結構體陣列（因為比較的方法同整型的比較方法不一致），所以這樣的陣列在我們目前編輯好的冒泡排序中是無法進行排序的

所以我們可以得出結論我們日常撰寫的冒泡排序，不能對各種型別的變數進行排序

下面我們引入今天的主角qsort函式

三、qsort函式的使用及優點

1.qsort函式所需要的頭檔案

2.qsort函式所需要的引數以及回傳型別

我們看到qsort函式的回傳型別為void（空型別）

然后我們逐個看函式所需要的引數

a. base為所需要排序的陣列首元素地址

b. 需要排序的陣列的元素個數

c. 陣列元素的大小（單位:位元組）

d.

這里我們需要自己寫一個比較函式

在這里我們不知道陣列的所有資訊（型別，元素個數，元素大小），所以在這里我們對于元素個數和元素大小統一采用 size_t的型別（無符號數）對于陣列首元素的地址，由于我們不知道所需要排序的陣列是什么型別的，所以我們用void* 來接收陣列首元素的地址（void* 可以轉化為任意類指標型別），我們自己撰寫的比較函式，因為不知道元素型別，所以統一寫為 void* 型別去接收兩個變數的地址，在qsort函式中傳入我們自己撰寫的比較函式的地址即可，

e.自己撰寫的cmp函式的回傳值

所以回傳值大于0升序排列，小于0降序排列，同我們冒泡排序中的if條件判斷陳述句的那段代碼，判斷與后方元素的大小關系

比較函式的代碼如下：

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

如上圖所示我們比較是兩個整型

因為e1是存放的變數型別的地址并且為void*型別所以我們需要把e1強制轉化為我們所需的比較型別如上的代碼比較的是整型資料，所以我們把e1強制轉換為int*型別，最后再解參考得到元素，e2同理，最后回傳的是兩個元素相減后與0的大小情況

qsort函式的全部代碼：

#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
int main()
{
	int arr[10] = { 2,7,1,3,4,5,6,9,8,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]);
	}
	return 0;
}

如上圖的代碼我們是將陣列進行了升序的排列

如果我們需要改為降序的排列我們僅需要把e1,e2的位置交換即可

下面我們嘗試一下利用qsort函式去對結構體進行排序

代碼如下：（按名字排序）我們利用qsort函式只需要去變換比較的函式就可以實作對任意型別的比較在這里的字串比較我們不能用加減我們需要借助庫函式strcmp 其他的同整型的判斷方法一致

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct stu 
{
	char name[20];
	int age;
};
int cmp_name(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}
int main()
{
	struct stu s[3] = { {"zhangsan",11},{"lisi",10},{"wangwu",12} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_name);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d %s\n", s[i].age, s[i].name);
	}
	return 0;
}

按照年齡排序：（改變比較函式即可）年齡是整型直接相減就可以判斷元素的大小

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct stu 
{
	char name[20];
	int age;
};
int cmp_age(const void* e1, const void* e2)
{
	return ((struct stu*)e1)->age-((struct stu*)e2)->age;
}
int main()
{
	struct stu s[3] = { {"zhangsan",11},{"lisi",10},{"wangwu",12} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_age);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d %s\n", s[i].age, s[i].name);
	}
	return 0;
}

四、利用冒泡排序模擬實作qsort函式

#include <stdio.h>
int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
void swap(char* buf1, char* buf2,int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char temp = *buf1;
		*buf1 = *buf2;
		*buf2 = temp;
		buf1++;
		buf2++;
	}
}
void Bubblesort(void* base,size_t num,size_t width,int(*cmp)(const void* e1, const void* e2))
{
	size_t i = 0;
	size_t j = 0;
	for (j = 0; j < num - 1; j++)
	{
		for (i = 0; i < num - j - 1; i++)
		{
			if (cmp((char*)base+i*width,(char*)base+(i+1)*width) > 0)
			{
				swap((char*)base + i * width, (char*)base + (i + 1) * width, width);
				
			}
		}
	}

}
int main()
{
	int arr[10] = { 2,7,1,3,4,5,6,9,8,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Bubblesort(arr, sz, sizeof(arr[0]), cmp_int);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

上圖代碼為利用冒泡排序模擬實作的qsort函式

我們進行分析：

1.

我們看主函式的代碼幾乎一致，只有排序的函式名字改變了（變成我們自己撰寫的Bubblesort）

2.自定義Bubblesort函式

這里因為不知道所排列的陣列是什么型別，陣列的大小是多少，每個元素的大小，所以這里的引數型別我們直接采用qsort函式的引數樣式即可

冒泡排序的趟數和元素個數撰寫方法都和普通的冒泡排序一致

這里的條件判斷if陳述句與普通的冒泡陳述句中的本條陳述句效果一致，即判斷相鄰兩個元素大小

決議本條陳述句：

1.為什么強制型別轉化使用的是char*

因為char*為最小的指標型別，char*+1型別每回跳過一個位元組，因為我們不清楚所需要排序的陣列型別，所以我們選擇char*型別，最小并且是最細的方法，把陣列的首元素強制型別轉化后，后面加上 i*width（實際陣列元素的大小），就是可以得到我們實際陣列的元素地址，如果這里我們采用int*，int*+1跳過的是四個位元組，如果排序的陣列是char型別，這樣的就獲得不了陣列的所有元素地址，所以我們需要采取最小最細的型別去對獲取陣列元素的地址

2.把我們獲取的兩個變數放入之前編輯好的比較函式中，比較兩個數字的大小

3.如果滿足我們的if條件句的條件我們就進入到元素交換的陳述句中來

本條陳述句與我們普通的冒泡排序中的的效果一致就是交換兩個元素的大小只不過我們利用一個函式去將換順序這個功能實作，

4.swap函式

這里的引數我們采用兩個指標去接收兩個變數的地址，而且還需要元素的大小

交換元素的代碼如下：

最終運行結果：

我們試一下結構體可不可以拿我們剛剛撰寫好的冒泡排序進行排序

#include <stdio.h>
void swap(char* buf1, char* buf2,int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char temp = *buf1;
		*buf1 = *buf2;
		*buf2 = temp;
		buf1++;
		buf2++;
	}
}
void Bubblesort(void* base,size_t num,size_t width,int(*cmp)(const void* e1, const void* e2))
{
	size_t i = 0;
	size_t j = 0;
	for (j = 0; j < num - 1; j++)
	{
		for (i = 0; i < num - j - 1; i++)
		{
			if (cmp((char*)base+i*width,(char*)base+(i+1)*width) > 0)
			{
				swap((char*)base + i * width, (char*)base + (i + 1) * width, width);
				
			}
		}
	}

}
struct stu
{
	char name[20];
	int age;
};
int cmp_age(const void* e1, const void* e2)
{
	return ((struct stu*)e1)->age-((struct stu*)e2)->age;
}
int main()
{
	struct stu s[3] = { {"zhangsan",11},{"lisi",10},{"wangwu",12} };
	int sz = sizeof(s) / sizeof(s[0]);
	/*qsort(s, sz, sizeof(s[0]), cmp_name);*/
	Bubblesort(s, sz, sizeof(s[0]), cmp_age);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d %s\n", s[i].age, s[i].name);
	}
	return 0;
}

按照年齡排

#include <stdio.h>
void swap(char* buf1, char* buf2,int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char temp = *buf1;
		*buf1 = *buf2;
		*buf2 = temp;
		buf1++;
		buf2++;
	}
}
void Bubblesort(void* base,size_t num,size_t width,int(*cmp)(const void* e1, const void* e2))
{
	size_t i = 0;
	size_t j = 0;
	for (j = 0; j < num - 1; j++)
	{
		for (i = 0; i < num - j - 1; i++)
		{
			if (cmp((char*)base+i*width,(char*)base+(i+1)*width) > 0)
			{
				swap((char*)base + i * width, (char*)base + (i + 1) * width, width);
				
			}
		}
	}

}
struct stu
{
	char name[20];
	int age;
};
int cmp_name(const void* e1, const void* e2)
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}
int main()
{
	struct stu s[3] = { {"zhangsan",11},{"lisi",10},{"wangwu",12} };
	int sz = sizeof(s) / sizeof(s[0]);
	Bubblesort(s, sz, sizeof(s[0]), cmp_name);
	/*Bubblesort(s, sz, sizeof(s[0]), cmp_age);*/
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d %s\n", s[i].age, s[i].name);
	}
	return 0;
}

按姓名排：

總結

這些就是qsort函式一些使用方法，以及利用冒泡排序去模擬實作qsort函式

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297143.html

標籤：其他

上一篇：Java實作雙向鏈表的基本操作

下一篇：關于堆的知識

C語言庫函式之----qsort函式決議（快速排序）