C語言中qsort函數用法及用氣泡排序實現

2022-10-28 14:03:55

一、qsort函數簡介

qsort函數是由C語言提供的標準庫函數, 它的實現思想是快速排序，qosrt函數的標頭檔案是stdlib.h。

qsort函數可以排序任意型別的陣列。它的返回型別是void，引數是(void* base,size_t num,size_t size,int(*compar)(const void* e1,const void* e2))。

接下來對它的引數進行分析：

引數void* base中base是void*型別的指標，base指向待排序陣列的第一個元素的地址，也就是指向陣列的起始位置。

引數size_t num中size_t表示的是無符號整型，num表示的是待排序陣列中總的元素個數。

引數size_t size中size表示的是待排序陣列中每個元素佔幾個位元組。

引數int (*compar)(const void* e1, const void* e2)是函數指標，int表示指向函數的返回型別是int型別，compar表示的是函數指標變數，指向函數的地址，被指向的函數用於比較兩個元素的大小。

在引數int (*compar)(const void* e1, const void* e2)中，函數指標變數compar指向的函數返回型別是int，返回值的大小可以分為三種情況：

返回值	條件
>0	e1>e2
<0	e1<e2
=0	e1=e2

二、qsort函數的使用

1.整型陣列排序

#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
    return *((int*)e1) - *((int*)e2);//預設是升序，將return中e1和e2的位置交換可以使其降序
    //無法對void*型別的指標進行具體操作，因此要將其強制型別轉換為int*,使其能夠在解除參照時存取到4個位元組
}
int main()
{
    int i = 0;
    int arr[] = { 7,8,9,4,5,6,1,2,3,10 };
    int sz = sizeof(arr) / sizeof(arr[0]);//計算整型陣列中有多少個元素
    qsort(arr, sz, sizeof(int), cmp_int);//sizeof(int)是用來計算int型別的資料所佔位元組數
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);//輸出為1 2 3 4 5 6 7 8 9 10
    }
    return 0;
}

注意：當函數的形參為void*型別，要對其進行具體操作時，應該將其強制型別轉換為所需的指標型別

2.字串排序

#include <stdio.h>
#include <stdlib.h>
int cmp_char(const void* e1, const void* e2)//字串排序
{
    return strcmp((char*)e1, (char*)e2);//比較字元大小用strcmp
}
int main()
{
    char arr[] = "badecf";
    int i = 0;
    //int sz = sizeof(arr) / sizeof(arr[0]);//sizeof求字串長度會將算進去,也就是實際計算出來的會比陣列中的多1。
    int sz = strlen(arr);//strlen是用來計算字串長度的，且只能用來計算字串的長度。
    qsort(arr,sz , sizeof(char), cmp_char);
    printf("%sn", arr);//abcdef
    return 0;
}

3.字串長度排序

#include <stdio.h>
#include <stdlib.h>
int cmp_char_strlen(const void* e1, const void* e2)//比較字串長度
{
    return strlen(*(char**)e1) - strlen(*(char**)e2);//先將e1和e2強制型別轉換成為char**型別，再解除參照取出陣列中字串的地址，計算字串長度
}
int main()
{
    //char* arr[] = {"abcdef" "abc","defs" };
    //也可以通過下面的方式來寫指標陣列，下面的4行和上面的這一行作用一樣
    char* arr1 = "abc";
    char* arr2 = "abcd";
    char* arr3 = "abcdef";
    char* arr[] = { arr1,arr2,arr3 };
    int i = 0;
    qsort(arr, 3, sizeof(char*), cmp_char_strlen);
    for (i = 0; i < 3; i++)
    {
        printf("%sn", arr[i]);//輸出結果為 abc  defs  abcdef
    }
    return 0;
}

4.浮點型陣列排序

#include <stdio.h>
#include <stdlib.h>
int cmp_float(const void* e1, const void* e2)//浮點型陣列排序
{
    //return (int)(*(float*)e1 - *(float*)e2);//可能會出錯，如12.002和12.001比較之後再強制型別轉換為int型別後，結果為0
    if (*(float*)e1 - *(float*)e2 > 0.000000)
    {
        return 1;//當e1>e2時，返回大於0的數
    }
    if (*(float*)e1 - *(float*)e2 < 0.000000)
    {
        return -1;//當e1<e2時，返回小於0的數
    }
    else
        return 0;//當e1和e2相等時，返回等於0的數
}
int main()
{
    float arr[3] = { 12.01f,12.03f,12.09f };
    int sz = sizeof(arr) / sizeof(arr[0]);//計算陣列長度
    qsort(arr, sz, sizeof(float), cmp_float);
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%f  ", arr[i]);//輸出結果為12.010000  12.030000  12.090000
    }
    return 0;
}

5.結構體型別排序

#include <stdio.h>
#include <stdlib.h>
struct stu
{
    char name[20];
    int age;
};
int cmp_s_age(const void* e1, const void* e2)//比較結構體中int型別
{
    return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
int cmp_s_name(const void* e1, const void* e2)//比較結構體中char型別的陣列
{
    return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}
int main()
{
    struct stu s[] = { {"zhangsan",21} ,{"lisi",20},{"wangwu",52}};
    int i = 0;
    int sz = sizeof(s) / sizeof(s[0]);
    for (i = 0; i < sz; i++)
    {
        printf("%s %dn", s[i].name, s[i].age);
    }
    qsort(s, sz, sizeof(struct stu), cmp_s_age);//比較年齡，即比較int型別
    //qsort(s, sz, sizeof(struct stu), cmp_s_name);//比較姓名，即比較char型別的陣列
    printf("n");
    for (i = 0; i < sz; i++)
    {
        printf("%s %dn", s[i].name, s[i].age);//輸出為年齡按照升序排列，如果比較姓名，則按照姓名的首字元的ASCII值按照升序排列
    }
    return 0;
}

三、氣泡排序實現qsort函數的功能

1.氣泡排序簡介

氣泡排序是通過對兩個相鄰元素進行比較，如果不符合條件就相互交換位置，並與後面相鄰的元素再次比較，直至滿足條件為止。

對於氣泡排序，如果它有n個元素，它將進行n-1次的迴圈。氣泡排序的缺點是隻能對整型陣列進行排序。

我們通過對整型陣列排序進一步瞭解氣泡排序

//用氣泡排序對整型陣列進行排序
#include <stdio.h>
int main()
{
    int i = 0;
    int j = 0;
    int arr[] = { 7,8,9,4,5,6,1,2,3,10 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    for (i = 0; i < sz-1; i++)//總共迴圈sz-1次
    {
        int flag = 1;//標記，假設陣列是有序的
        for (j = 0; j < sz - 1 - i; j++)//第一個元素需要和剩餘的sz-1個元素比較，第二個元素需要和sz-1-1個元素比較……所以每次迴圈需要比較的次數為sz-1-i
        {
            if (arr[j] < arr[j + 1])//從大到小排列
            {
                int tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
                flag = 0;//倘若發生交換說明陣列是無序的
            }
        }
        if(flag == 1)
        {
            break;//如果沒發生一次交換說明陣列已經是符合要求的有序陣列
        }
    }
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);//輸出結果為 10 9 8 7 6 5 4 3 2 1
    }
    return 0;
}

2.氣泡排序實現qsort函數功能

對氣泡排序進行qsort化時，要參照qsort函數的引數，儘量做到引數一致。

void qsort_bubble(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))

void* base表示對應陣列元素的起始位置。

int sz表示陣列中元素總個數。

int width表示陣列中每個元素所佔位元組數。

int(*cmp)(const void* e1, const void* e2)是函數指標，指向比較兩個元素大小的函數。

設計的氣泡排序qsort化函數qsort_bubble與庫函數qsort的引數意義相同。在qsort_bubble和qsort引數中函數指標指向的用於比較陣列中兩個元素大小的函數不用發生改變，可以直接參照。

利用氣泡排序思想實現qsort函數功能並對結構體排序。

#include <stdio.h>
struct stu
{
	char name[20];
	int age;
};
int cmp_s_age(const void* e1, const void* e2)//比較結構體中整型
{
	return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
int cmp_s_name(const void* e1, const void* e2)//比較結構體中整型
{
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}
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 qsort_bubble(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width)>0)
				//強制轉換成char*型別的指標，進行交換時一個位元組一個位元組的交換，+width，向後走對應的位元組
			{
				Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);//滿足條件進行交換
			}
		}
	}
}
int main()
{
	struct stu s[] = { {"zhangsan",21} ,{"lisi",20},{"wangwu",52}};
	int i = 0;
	int sz = sizeof(s) / sizeof(s[0]);
	//printf("%d", sz);
	for (i = 0; i < sz; i++)
	{
		printf("%s %dn", s[i].name, s[i].age);
	}
	qsort_bubble(s, sz, sizeof(struct stu), cmp_s_age);//比較年齡，即比較int型別
	//qsort_bubble(s, sz, sizeof(struct stu), cmp_s_name);//比較姓名，即比較char型別的陣列
	printf("n");
	for (i = 0; i < sz; i++)
	{
		printf("%s %dn", s[i].name, s[i].age);
	}
	return 0;
}

到此這篇關於C語言中qsort函數用法及用氣泡排序實現的文章就介紹到這了,更多相關C語言 qsort函數內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！