从冒泡到模拟q sort函数——初见排序算法的探索和思考
国庆中秋喜相连，万家团圆乐同庆。
各位小伙伴们大家好，我是此方，在此，先祝大家双节快乐！
我们都知道排序有很多种：例如冒泡排序，插入排序，快速排序，等等很多种。
而冒泡排序，是各种计算机语言中最经典的一种排序算法。
今天我将从冒泡排序开始，到实现qsort函数的模拟。逐层深入，探索排序问题。
并给出鄙人的一些拙见。
上正文：
一，冒泡排序：最经典的排序算法
假如有一个十元素整型数组，他是完全倒着排序的：就像这样
now，我们要按照从小到大的顺序将这十个数字重新排列。
如果我们想要用冒泡排序：那么他的逻辑应该是这样的：
首先让最左边的数字和他右边的数字比较：9>8，将9和8互换位置：
让9继续和他右边的数字比较，再互换位
以此类推：9不断的比较——>移动——>再比较：最后；会到达最右边，这样，我们就让最大的数字9放在了最低位置
然后是8，接下来是7，6，5......................直到最后，数列变成0，1，2，3，4，5，6，7，8，9
结束；
我们将一个数字通过不断和他右边的数字”比较，移动。直到这个数字到达他基于升序排序应该到达的位置“这一整个过程称为”一趟“。
将每一个数字的一趟中的每一次移动称为”一次“
那么，冒泡排序函数应该是这样的：
int*arr表示接收arr（数组首元素的地址），sz是数组元素个数，（width（串了，应该删除））
变量 i 表示趟数：一共有sz-1趟：因为有sz个数字，而将前9个数字全部排好后，最后一个数字默认到达了他应该在的位置。
变量 j 表示次数：每一趟有j-1-i次：因为某一个数字（首先假设他是最左边的那个），在考虑最坏的情况下，他可能要移动到数列的最后一个，即他后面有几个数字就移动几次。紧接着第二趟（此时i+1），同样在考虑最坏的情况下，他后面有几个数字就要移动几次但是要去掉目前最后一个数字。以此类推；第一趟额外-0，第二趟额外-1：这与i的变化完全一致：所以使用j-i-1来说明每趟需要的次数。
呈现一下源代码：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<string.h> #include<stdlib.h> void bouble_qsort( int* arr,size_t sz,int width)//默认升序 { 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 change = 0; change = *(arr + j); *(arr + j) = *(arr + 1 + j); *(arr + 1 + j) = change; } } } } void print(int* arr, size_t sz) { int i; for (i = 0; i < sz; i++) { printf("%d ", *(arr + i)); } } int main() { int arr[10] = { 2,5,8,7,4,1,3,6,9,0}; int sz = sizeof(arr) / sizeof(arr[0]); bouble_qsort(arr,sz,arr[0]); print(arr,sz); return 0; }二，qsort函数
qsort函数的功能是为一切类型进行排序；他的使用需要头文件<string.h>，
他有四个参数：
base：待排序数组的首元素地址。
num：待排序元素个数。
size：待排序元素的大小单位字节。
cmp：比较函数指针。
同时对比较函数的返回值做了规定：
比较函数必须返回三种值：
- 负数：表示
a < b（a应该在b前面） - 零：表示
a == b - 正数：表示
a > b（a应该在b后面）
学会了这些之后，我们不妨写下如下代码测试一下qsort的强大功能：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> int cmp_int(const void* p1,const void* p2) { return *((int*)p1) - *((int*)p2); } test1() { int arr[] = { 1,4,7,2,5,8,6,3,9,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)); } } int main() { test1();//排序整型 // test2();//排序结构体————以整数成员 // test3();//排序结构体————以字符成员 return 0; } 实际上，为了测试qsort可以排序任意类型数据的万能性：我们还有以下代码:
struct stu { char name; int age; }; int cmp_stu_by_name(const void*p1,const void*p2) { return strcmp(((struct stu*)p1)->name, ((struct stu*)p2)->name); } void test2() { struct stu s1[3] = { {"zhangsan",18},{"lisi",19} ,{"wangwu",22}}; int sz = sizeof(s1) / sizeof(s1[0]); qsort(s1, sz, sizeof(s1[0]), cmp_stu_by_name); } int main() { //test1();//排序整型 test2();//排序结构体————以整数成员 //test3();//排序结构体————以字符成员 return 0; }好了，既然qsort的功能如此强大。那么我们可不可以模拟一个qsort函数呢？
事实上是可以的：
三，冒泡排序模拟qsort函数
qsort函数，其本质上是使用了快速排序算法；
这里我们可以用冒泡排序算法来完成他：
不难发现：qsort的前三个参数用来用指针的方式排序每个元素。
最后一个函数指针参数，传入比较函数的指针，在qsort函数内用来调用比较函数。（回调函数）
此外，对比冒泡排序的局限性（只能排序整数。）模拟qsort函数必须具备可以排序任意类型给能力：所以交换函数也得改成泛式编程。
直接上源码
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<string.h> #include<stdlib.h> void swap(void* buf1, void* buf2, size_t width) { int i = 0; for (i = 0; i < width; i++) { char tmp = *((char* )buf1+i); *((char*)buf1 + i) = *((char*)buf2 + i); *((char*)buf2 + i) = tmp; } } void bouble_qsort( void* base,size_t sz,size_t width,int (*cmp)(const void*,const void*))//默认升序 { 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) { swap((char*)base + j * width, (char*)base + (j + 1) * width,width); } } } } int cmp_int(const void*p1, const void*p2) { return (*(int*)p1 - *(int*)p2); } void print(int* arr, size_t sz) { int i; for (i = 0; i < sz; i++) { printf("%d ", *(arr + i)); } } int main() { int arr[10] = { 2,5,8,7,4,1,3,6,9,0}; int sz = sizeof(arr) / sizeof(arr[0]); bouble_qsort(arr,sz,sizeof(arr[0]),cmp_int); print(arr,sz); return 0; }好的，本期到此结束，感谢你的观看。
