在日常生活中，經常涉及到對資料的處理和分析，有時我們需要對一組雜亂無章的資料進行排序，這時候就需要用到排序演算法，一般的對于整型資料的處理，我們可以用冒泡排序：
冒泡排序的應用舉例如下：
#include<stdio.h>
#include<stdlib.h>
void test0(int arr[], int sz)//冒泡排序基本演算法
{
int i, j;
//進行冒泡排序的趟數
for (i = 0; i < sz; ++i)
{ //每趟冒泡排序的對數
for (j = 0; j < sz - i - 1; ++j)
{
if (arr[j] > arr[j + 1])
{ //交換
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
int main()
{
int arr[] = { 5,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("before : ");
for (int i = 0; i < sz; ++i)
{
printf("%d ", arr[i]);
}
test0(arr, sz);
printf("\n");
printf("after: ");
for (int i = 0; i < sz; ++i)
{
printf("%d ", arr[i]);
}
return 0;
}輸出結果如下；
然而生活中我們碰到的資料遠不止是整型，有時是姓名，浮點小數（利率）以及甚至是一個復雜的物件，因此上述這種冒泡排序的弊端就顯現出來了（只能排序整數），事實上，C語言提供了一個為我們排序復雜物件的函式-qsort()，
我們先來看qsort()的函式原型：
void qsort (void* base, size_t num, size_t size,
int (*compar)(const void*,const void*));其中size_t是一個無符號整型的別名，compar是一個函式指標（存放函式地址）
下面我們來使用qsort()來排序浮點數：
#include<stdio.h>
#include<stdlib.h>//包含qsort()的原型及定義
//引數是函式指標，說明該指標能夠接受形參型別相同，回傳型別也相同的函式
int cmp_float(const float * a,const float* b)//比較浮點數的函式（使得能被收）
{
if (*a == *b)
return 0;
else if (*a > *b)
return 1;
else
return -1;
}
int main()
{
float arr[] = { 5.0,4.0,3.0,2.0,1.0 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("before: ");
for (int i = 0; i < sz; ++i)
{
printf("%lf ", arr[i]);
}
qsort(arr,sz, sizeof(arr[0]), cmp_float);
printf("\n");
printf("after: ");
for (int i = 0; i < sz; ++i)
{
printf("%lf ", arr[i]);
}
return 0;
}運行結果如下：
講完了怎么使用，不妨我們嘗試模擬實作這一個函式（核心演算法是冒泡排序）
我們注意到qsort()函式的第一個引數的型別是一個無型別的指標（不是空指標）（意味著我們可以用強制型別轉換成我們所要的指標），同時我們還要知道元素的個數和元素的大小，最重要的是我們要針對不同的資料型別設計不同的比較方法（把比較方法抽離出來）
核心部分的代碼：
void Myqsort(void* base, int sz, int width, int(*cmp)(void* e1, void* e2))
{
int i = 0
;
//比較趟數
for (i = 0; i < sz; ++i)
{ //每趟比較對數
for (int j = 0; j < sz - i - 1; ++j)
{//強制成字符指標，是因為字符型指標每解參考一次都會訪問一個位元組，
//乘以寬度就是跳過寬度個位元組，再乘以變數j就能控制訪問每一對元素
{ if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
swap((char*)base + j * width, (char*)base + (j + 1) * width, 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 cmp_int(void* e1, void* e2)
{
return *(int*)(e1)-*(int*)(e2);
}
//比較浮點數
int cmp_float(void* e1, void* e2)
{
if (*(float*)e1 == *(float*)e2) return 0;
else if (*(float*)e1 > *(float*)e2) return 1;
else return -1;
}
//比較學生結構體的年齡
int cmp_stu_age(void* e1, void* e2)
{
return ((Stu*)e1)->age - ((Stu*)e2)->age;
}
//比較學生結構體的姓名
int cmp_stu_name(void* e1, void* e2)
{ //箭頭的優先級比較高，所以要把強轉的結果括號起來
return strcmp(((Stu*)e1)->name, ((Stu*)e2)->name);
}測驗的部分：
//測驗整型
void testi()
{
int arr[] = { 9,8,7,6,5,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("before:");
for (int i = 0; i < sz; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
printf("after: ");
Myqsort(arr, sz, sizeof(arr[0]), cmp_int);
for (int i = 0; i < sz; ++i)
{
printf("%d ", arr[i]);
}
}
//測驗浮點型
void testf()
{
float arr[] = { 9.0,8.0,7.0,6.0,5.0,4.0,3.0,2.0,1.0 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("before:");
for (int i = 0; i < sz; ++i)
{
printf("%f ", arr[i]);
}
printf("\n");
printf("after: ");
Myqsort(arr, sz, sizeof(arr[0]), cmp_int);
for (int i = 0; i < sz; ++i)
{
printf("%f ", arr[i]);
}
}
//測驗年齡
void testa()
{
Stu s[] = { {"zhansan",16},{"lisi",28}, {"wangwu",22} };
int sz = sizeof(s) / sizeof(s[0]);
printf("before:");
for (int i = 0; i < sz; ++i)
{
printf("%s", s[i].name);
printf("%d ", s[i].age);
}
printf("\n");
printf("after: ");
Myqsort(s, sz, sizeof(s[0]), cmp_stu_age);
for (int i = 0; i < sz; ++i)
{
printf("%s", s[i].name);
printf("%d ", s[i].age);
}
}
//測驗姓名
void testn()
{
Stu s[] = { {"zhangsan",16},{"lisi",43}, {"wangwu",22} };
int sz = sizeof(s) / sizeof(s[0]);
printf("before:");
for (int i = 0; i < sz; ++i)
{
printf("%s", s[i].name);
printf("%d ", s[i].age);
}
printf("\n");
printf("after: ");
Myqsort(s, sz, sizeof(s[0]), cmp_stu_name);
for (int i = 0; i < sz; ++i)
{
printf("%s", s[i].name);
printf("%d ", s[i].age);
}
}主函式部分：
int main()
{
testi();
testf();
testa();
testn();
return 0;
}測驗結果如下：
比較年齡部分：
比較姓名：
完整代碼如下：
#include<stdio.h>
#include<string.h>
//引數是函式指標，說明該指標能夠接受形參型別相同，回傳型別也相同的函式
typedef struct student
{
char name[50];
int age;
}Stu;
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 Myqsort(void* base, int sz, int width, int(*cmp)(void* e1, void* e2))
{
int i = 0
;
//比較趟數
for (i = 0; i < sz; ++i)
{ //每趟比較對數
for (int j = 0; j < sz - i - 1; ++j)
{//強制成字符指標，是因為字符型指標每解參考一次都會訪問一個位元組，
//乘以寬度就是跳過寬度個位元組，再乘以變數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(void* e1, void* e2)
{
return *(int*)(e1)-*(int*)(e2);
}
//比較浮點數
int cmp_float(void* e1, void* e2)
{
if (*(float*)e1 == *(float*)e2) return 0;
else if (*(float*)e1 > *(float*)e2) return 1;
else return -1;
}
//比較學生結構體的年齡
int cmp_stu_age(void* e1, void* e2)
{
return ((Stu*)e1)->age - ((Stu*)e2)->age;
}
//比較學生結構體的姓名
int cmp_stu_name(void* e1, void* e2)
{ //箭頭的優先級比較高，所以要把強轉的結果括號起來
return strcmp(((Stu*)e1)->name, ((Stu*)e2)->name);
}
//測驗整型
void testi()
{
int arr[] = { 9,8,7,6,5,4,3,2,1 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("before:");
for (int i = 0; i < sz; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
printf("after: ");
Myqsort(arr, sz, sizeof(arr[0]), cmp_int);
for (int i = 0; i < sz; ++i)
{
printf("%d ", arr[i]);
}
}
//測驗浮點型
void testf()
{
float arr[] = { 9.0,8.0,7.0,6.0,5.0,4.0,3.0,2.0,1.0 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("before:");
for (int i = 0; i < sz; ++i)
{
printf("%f ", arr[i]);
}
printf("\n");
printf("after: ");
Myqsort(arr, sz, sizeof(arr[0]), cmp_int);
for (int i = 0; i < sz; ++i)
{
printf("%f ", arr[i]);
}
}
//測驗年齡
void testa()
{
Stu s[] = { {"zhansan",16},{"lisi",28}, {"wangwu",22} };
int sz = sizeof(s) / sizeof(s[0]);
printf("before:");
for (int i = 0; i < sz; ++i)
{
printf("%s", s[i].name);
printf("%d ", s[i].age);
}
printf("\n");
printf("after: ");
Myqsort(s, sz, sizeof(s[0]), cmp_stu_age);
for (int i = 0; i < sz; ++i)
{
printf("%s", s[i].name);
printf("%d ", s[i].age);
}
}
//測驗姓名
void testn()
{
Stu s[] = { {"zhangsan",16},{"lisi",43}, {"wangwu",22} };
int sz = sizeof(s) / sizeof(s[0]);
printf("before:");
for (int i = 0; i < sz; ++i)
{
printf("%s", s[i].name);
printf("%d ", s[i].age);
}
printf("\n");
printf("after: ");
Myqsort(s, sz, sizeof(s[0]), cmp_stu_name);
for (int i = 0; i < sz; ++i)
{
printf("%s", s[i].name);
printf("%d ", s[i].age);
}
}
int main()
{
testi();
testf();
testa();
testn();
return 0;
}有不足之處還望指正
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/325632.html
標籤：其他
上一篇：如何使用混合分隔符（即方括號、空格和雙引號）來決議日志（nginx/apacheaccess.log）？并可選擇轉換為json