詳解qsort各種用法以及實作
文章目錄
- 詳解qsort各種用法以及實作
- 前言
- 一、qsort定義
- 二、qsort排序應用
- 1、整型排序
- 2、字符型排序
- 3、浮點型排序
- 4、字串排序
- 5、結構體排序
- 三、實作qsort
- 第一種寫法：
- 第二種寫法：
- 那么最后祝大家：
前言
- 在文章開頭，我們先來說一下qsort的作用，在正常我們寫完一個冒泡排序的時候比如void Bubble_sort(int arr[],int sz)；那么我們在用這個函式的時候就只能去給一個整型陣列大小排序，當我們想要去排序浮點型，字符型的時候該函式就不適用了，而qsort函式就能解決這個問題，只要你規定了排序方法，你就可以去排序字符，整型，浮點，結構體，做到萬物皆可排，
一、qsort定義
首先我們打開MSDN，搜索一下qsort
- 作用：Performs a quick sort.(執行快排)
- 頭檔案：<stdlib.h>
- 引數和回傳型別：
void qsort(
void *base, //接收所要排序的目標陣列名
size_t num, //接收排序陣列的個數（以元素為單位）
size_t width, //每一個元素大小（以位元組為單位）
int (__cdecl *compare )(const void *elem1, const void *elem2 ) //自定義的比較方法
);
-
這里要注意qsort函式里的void* ， 這里一旦寫成其他型別都會只能對一種資料型別排序，而空型別void*正好可以接收其他任何型別，從而當做引數！
-
自定義比較函式
這里MSDN上給出了一些關于該函式的說明，具體大家可以自行查看 -
引數型別：
int compare( const void * elem1,const void * elem2 ); -
回傳值：
并且注意按上邊這種回傳值去寫比較函式的話，最終是得到的是升序排列，
那么回傳值相反就會得到降序排列，
二、qsort排序應用
1、整型排序
- 首先我們給出一個亂序整型陣列，
int arr[] = { 1,3,4,8,2,6,7,5,9,10 };
- 接著按要求去寫qsort函式
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_int);
- 實作自定義cmp_int函式
那么這里也就是第一個引數小于第二個引數的話回傳值 < 0;
第一個引數大于第二個引數的話回傳值 > 0;
第一個引數等于第二個引數的話回傳值 = 0;
- 具體實作：
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
對傳進來的e1和e2用void* 來接收，并且考慮到使用的時候是對整型陣列排序，因此強轉成int * ，
用e1-e2，e1 > e2，回傳值大于0，e1 < e2，回傳值小于0，e1 = e2，回傳值等于0，滿足要求，
完整代碼：
#include<stdio.h>
#include<stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
int main()
{
int arr[] = { 1,3,4,8,2,6,7,5,9,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(arr[0]), cmp_int);
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
運行結果：
- 那么如果你想要實作降序只需修改一下自定義比較函式的回傳值（e2-e1）即可，
int cmp_int(const void* e1, const void* e2)
{
return *(int*)e2 - *(int*)e1;
}
2、字符型排序
- 我們知道字符是以ASC碼中對應的數字表示的，因此在寫比較函式時直接相減即可，
#include<stdio.h>
#include<stdlib.h>
int cmp_char(const void* e1, const void* e2)
{
return *(char*)e1 - *(char*)e2;
}
int main()
{
char a[] = { 'a','c','e','d','b' };
int sz = sizeof(a) / sizeof(a[0]);
qsort(a, sz, sizeof(a[0]), cmp_char);
for (int i = 0; i < sz; i++)
{
printf("%c ", a[i]);
}
return 0;
}
3、浮點型排序
- 這里只需要注意浮點型的資料儲存在計算機中是有誤差的，可能在你的電腦是1，那么其他電腦上就是2了，因此浮點數相等的比較不能直接相減，只能用fabs(a-b)<1e-20之類的這樣來判斷，所以這里只回傳了1和-1，
#include<stdio.h>
#include<stdlib.h>
int cmp_double(const void* e1, const void* e2)
{
return ((*(double*)e1 - *(double*)e2) > 0)? 1:-1;
}
int main()
{
double a[] = { 1.2,56.4,0.56,456.89,32.4 };
int sz = sizeof(a) / sizeof(a[0]);
qsort(a, sz, sizeof(a[0]), cmp_double);
for (int i = 0; i < sz; i++)
{
printf("%.2f ", a[i]);
}
return 0;
}
4、字串排序
#include<stdio.h>
#include<stdlib.h>
int cmp_string(const void* e1, const void* e2)
{
return strcmp((char*)e1, (char*)e2);
}
int main()
{
char a[5][6] = { "h","he","hel","hell","hello" };
int sz = sizeof(a) / sizeof(a[0]);
qsort(a, sz, sizeof(a[0]), cmp_string);
for (int i = 0; i < sz; i++)
{
printf("%s ", a[i]);
}
return 0;
}
- 值得注意的就是strcmp函式里邊強轉型別為char*后正好是 每一串字符的首地址，不用在解參考了，
5、結構體排序
struct student
{
char name[20];
int age;
};
這里我們定義了一個結構體，那么接下來按照名字和年齡兩種排序情況說明
1. 按照name排序
#include<stdio.h>
#include<stdlib.h>
struct student
{
char name[20];
int age;
};
int cmp_name(const void* e1, const void* e2)
{
return strcmp(((student*)e1)->name, ((student*)e2)->name);
}
void test()
{
student s[3] = { {"z",15},{"l",17},{"w",20} };
qsort(s, sizeof(s) / sizeof(s[0]), sizeof(s[0]), cmp_name);
for (int i = 0; i < 3; i++)
{
printf("%s ", s[i].name);
}
}
int main()
{
test();
return 0;
}
字典序結果：
2. 按照年齡排序：
#include<stdio.h>
#include<stdlib.h>
struct student
{
char name[20];
int age;
};
int cmp_age(const void* e1, const void* e2)
{
return ((student*)e1)->age - ((student*)e2)->age;
}
void test1()
{
student s[3] = { {"張三",15},{"李四",17},{"王偉",20} };
Bubble_sort(s, sizeof(s) / sizeof(s[0]), sizeof(s[0]), cmp_age);
for (int i = 0; i < 3; i++)
{
printf("%s ", s[i].name);
}
}
int main()
{
test1();
return 0;
}
三、實作qsort
這里我們采用冒泡排序來實作qsort函式：
void Bubble_sort(void* base, size_t num, size_t width, int(* compare)(const void* elem1, const void* elem2))
{
for (size_t i = 0; i < num; i++)//冒泡排序的趟數
{
for (size_t j = 0; j < num - 1 - i;j++)//每一趟
{
//判斷交換
}
}
}
- 那么框架寫完了，接下來就是判斷大小，規則在compare函式中用戶定義，那么怎么傳參呢？
- 由于比較函式要求的是要每個用來比較元素的地址，那么對于第n個元素我們只需要用base + j * width，即可找到第j個元素的地址，
- 但是要注意這里我們要（char*）base + j * width來強轉一下，我們知道char型別1個位元組，int 4個位元組，各種資料型別中最小的單位都是1個位元組，其他的都是其的n倍，因此（char*）強轉可以更好的進行以位元組為單位的資料交換！！！
void Bubble_sort(void* base, size_t num, size_t width, int(* compare)(const void* elem1, const void* elem2))
{
for (size_t i = 0; i < num; i++)//冒泡排序的趟數
{
for (size_t j = 0; j < num - 1 - i;j++)//每一趟
{
if (compare((char*)base+j*width,(char*)base+(j+1)*width) > 0)
{
Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
}
}
}
}
- 接下來就是swap函式的實作了
對于一個整型陣列：
其實際存盤如圖：（大端存盤）
- 每一個int型元素都是有四個位元組，需要把第一個元素和第二個元素在記憶體中的資料完全交換，而這里正好驗證上邊，以位元組為單位能夠方便很多，寬度是width（單位是位元組），只需要把每一個位元組的內容對應交換即可！！
第一種寫法：
完整代碼：
void Swap(char* buffer1, char* buffer2,int width)
{
for (int i = 0; i < width; i++)
{
char t = *buffer1;
*buffer1 = *buffer2;
*buffer2 = t;
buffer1++;
buffer2++;
}
}
void Bubble_sort(void* base, size_t num, size_t width, int(* compare)(const void* elem1, const void* elem2))
{
for (size_t i = 0; i < num; i++)//冒泡排序的趟數
{
for (size_t j = 0; j < num - 1 - i;j++)//每一趟
{
if (compare((char*)base+j*width,(char*)base+(j+1)*width) > 0)
{
Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
}
}
}
}
第二種寫法：
void myqsort(void * base, size_t nitems, size_t size, int(*compar)(const void *, const void *))
{
int i, j;
char * st = (char *)base; //void *不方便加減，用char *加減輕松且位元組跳轉為1，方便控制，
char tmp[16]; //考慮到long double型別，臨時空間做成16位元組比較保險
for (i = 0; i < nitems - 1; i++)
{
for (j = 0; j < nitems - 1 - i; j++) //冒泡常用回圈頭
{
if (compar(st + j * size, st + (j + 1) * size)) //比較的時候跳轉注意乘size
{
memcpy(tmp, st + j * size, size); //交換操作用memcpy完成就不會出問題，
memcpy(st + j * size, st + (j + 1) * size, size);
memcpy(st + (j + 1) * size, tmp, size);
}
}
}
}
那么最后祝大家：
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/296928.html
標籤：其他