目錄
一.冒泡排序
二.指針類型 void*
三. qsort
1.簡介
?2.研究函數參數?
3.怎么用？
(1)排數組，升序
(2)排序結構體
四.用冒泡排序思想，模擬實現 qsort (可排序任意類型數據)
1.函數參數設計
2.在 if (cmp( )>0) 怎么傳參？
3.怎么交換？
五.整體代碼
一.冒泡排序
對數組進行排序，升序。思想：兩兩相鄰元素比較
void bubble_sort(int arr[], int sz)
{//趟數int i = 0;for (i = 0; i < sz - 1; i++){//一趟冒泡排序的過程int j = 0;for (j = 0; j < sz - 1 - i; j++){if (arr[j] > arr[j + 1]){int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}}
}int main()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);//打印 0 1 2 3 4 5 6 7 8 9int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}10個元素9趟，sz 個元素 sz-1 趟。
第一趟10個元素比較9次，第二趟9個元素比較8次 ......
缺點：只能排序整數。因為他的參數已經寫死了，只能是整形數組。想排序字符數組、浮點型、結構體......做不到。他的功能非常有限。
二.指針類型 void*
先跳過，看完 三.2.后，回來看。
為什么 qsort 的參數寫的 void*(無具體類型的指針) ?
因為：函數設計者，不知道未來你會比較什么類型的數據。
int a = 10;
float f = 5.5f;
int* p = &a;//編譯器沒報錯
p = &f;//編譯器報錯：從“float *”到“int *” 的類型不兼容void* pp = &f;//不報錯
pp = &a;//不報錯可以把 pp 理解為通用的指針。(垃圾桶)誰的地址往進放。
缺點：放進去，不能直接用
float f = 5.5f;
void* pp = &f;
printf("%f", *pp);
void* 類型的指針不能直接解引用。它沒有具體類型，自己都不知道自己是啥類型
pp++; 也不行。無具體類型，它也不知道它 + 一步，+ 多遠
當你都不知道未來別人給你傳誰的地址時，用 void* 類型的指針接收
怎么用？指針類型可以轉換
接著看 三.3.
三. qsort
qsort 內部的細節大家先不要關心，回頭小編帶大家模擬實現
1.簡介
是庫函數里提供的一個排序函數，底層用的是快速排序。頭文件 #include <stdlib.h>
?2.研究函數參數?
一共4個參數：1.待排序數組的起始地址。2.元素個數。3.一個元素的大小(字節)。
4.(函數指針)。int (*compar)(const void* e1, const void* e2)
先分析，對上面的 bubble_sort 函數部分進行改造。希望函數可以排整型、浮點型、結構體......(任意類型數據)，但還是用冒泡排序的思想，趟數和一趟比較的對數都不用變。
11-15行要變，因為：兩個整型可以直接用 > 比較。但兩個結構體元素不能用 > 比。
不同數據的比較方法不一樣，交換方式不一樣
想讓他排任意類型的數據，把比較兩個元素的方法抽離出來。
比如：程序員A 想排序兩個整型，自己提供兩個整型的比較方法；想排序結構體，自己提供兩個結構體的比較方法。
再把比較的方法傳進來，你按照我的方法比較這兩個元素就可以。
其實，qsort 就是這么實現的。自己寫個比較兩個東西函數，把函數的地址傳給 qsort ，恰好用(*compar)這個函數指針接收。然后 qsort 里面就按照這個函數指針指向的函數來比較。注意：&函數名? ? ? 函數名? ? ? ?都是地址
寫的函數就被稱為回調函數
e1 e2 分別是要比較的兩個元素的地址
3.怎么用？
(1)排數組，升序
#include <stdlib.h>
cmp_int()
{ }int main()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_int);// 這里是函數cmp_int 的地址int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}要把 cmp_int 的地址傳給 qsort 所需要的(*compar) 函數指針。
cmp_int 的參數、返回類型要與 qsort 的第四個參數的函數指針的參數、返回類型 保持一致
#include <stdlib.h>//實現一個比較整形的函數
int cmp_int(const void* e1, const void* e2)
{ //(int*)e1 把e1當成整型指針了return *(int*)e1 - *(int*)e2;
}int main()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_int);// 這里是函數cmp_int 的地址int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}
cmp_int 實現了比較 e1 e2 指向的兩個整型。把 cmp_int 的地址傳給 qsort
qsort 就知道了，說：你讓我 比較 arr 里 sz 個元素，每個元素大小為 sizeof(arr[0])，數組arr里兩個元素的比較方法是 cmp_int
想降序：return *(int*)e2 - *(int*)e1;
(2)排序結構體
1.按照學生年齡排序
#include <stdlib.h>struct Stu
{char name[20];int age;
};int cmp_stu_by_age(const void* e1, const void* e2)
{// (struct Stu*)e2 - e2強制轉化為結構體類型指針return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}int main()
{struct Stu s[3] = { {"zhangsan",20}, {"lisi", 50}, {"wangwu", 33} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);return 0;
}
2.按照學生名字排序
#include <stdlib.h>
#include <string.h>
struct Stu
{char name[20];int age;
};int cmp_stu_by_name(const void* e1, const void* e2)
{return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}int main()
{struct Stu s[3] = { {"zhangsan",20}, {"lisi", 50}, {"wangwu", 33} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);return 0;
}
四.用冒泡排序思想，模擬實現 qsort (可排序任意類型數據)
1.函數參數設計
參數1：為了能夠接受任意類型地址，用 void*? 。? 參數2：元素個數
為什么 qsort 要傳元素大小？
void* 無具體類型，只知道待排序數組元素個數，不知道一個元素占幾個字節
參數3：寬度? ? 參數4：提出比較方法
類型最好給 size_t ，個數、寬度永遠是正數
//實現一個比較整型的函數
int cmp_int(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}void bubble_sort(void* base, size_t sz, size_t 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() > 0){//交換}//if (arr[j] > arr[j + 1])//{// int tmp = arr[j];// arr[j] = arr[j + 1];// arr[j + 1] = tmp;//}}}
}void test3()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}
}int main()
{test3();return 0;
}2.在 if (cmp( )>0) 怎么傳參？
相鄰兩元素比較，傳過來要是兩元素的地址。比如，傳9 8地址。怎么算呢？
現在不知道里面放的什么類型的元素，沒法直接用下標來搞。只能通過偏移量來算。
8的地址是 base + 幾。但 base 是 void* ，不能直接加。
強制類型轉換。轉換成什么類型？
int ？ 不行，寫死了。
怎么辦？9的寬度是 width，從9偏移 width 個字節來到8。怎么來到8呢？
寬度 width 的單位是字節，如果把它轉換成 char* 的指針，char* 的指針+width=跳過width個字節
if(cmp((char*)base, (char*)base + width) > 0) //只是第一對元素if(cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{//交換
}if 里面是分別對應下標為 j? ?j+1 元素的地址，分別傳給 e1? ?e2 指針
cmp是比較函數，e1? ?e2? 是它比較的兩個元素
我們已經把待比較的兩個元素的地址傳給 e1? ?e2 。cmp 就通過這樣一個指針找到它所指向的比較函數。如果比較函數返回值 >0 就交換
3.怎么交換？
?給一個Swap 函數，把(char*)base + j * width , (char*)base + (j + 1) * width) 兩個指針指向的元素交換。
交換這兩個元素的寬度是多大呢？注意：我不知道我交換的兩個元素多大。把 width 傳過去
比較的時候都不知道比較誰，交換時也肯定不知道交換的是什么類型的數據，所以通過類型是沒辦法
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
{//交換Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
}但是注意，當我要交換兩個結構體的時候。我們沒辦法創建出10字節的臨時空間，但是可以創建一個字節的空間。
交換每一對字節，這兩個元素整體也就交換了
//已經強制轉換為char*，這里也不端著了，就寫成char* 的指針
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++;}
}
五.整體代碼
#include <stdio.h>
#include <string.h>struct Stu
{char name[20];int age;
};int cmp_stu_by_age(const void* e1, const void* e2)
{return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}int cmp_stu_by_name(const void* e1, const void* e2)
{return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}//實現一個比較整型的函數
int cmp_int(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}//已經強制轉換為char*，這里也不端著了，就寫成char* 的指針
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 bubble_sort(void* base, size_t sz, size_t width, int (*cmp)(const void* e1, const void* e2))
{//趟數size_t i = 0;for (i = 0; i < sz - 1; i++){//一趟冒泡排序的過程size_t j = 0;for (j = 0; j < sz - 1 - i; j++){if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){//交換Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}//使用我們自己寫的bubble_sort函數排序整型數組
void test3()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}
}//使用我們自己寫的bubble_sort函數排序結構體數組
void test4()
{struct Stu s[3] = { {"zhangsan",20}, {"lisi", 50}, {"wangwu", 33} };int sz = sizeof(s) / sizeof(s[0]);bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_age);bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_name);
}int main()
{test3();test4();return 0;
}
、tolower()、 isspace())
