【落羽的落羽 C语言篇】指针·之其五

一、冒泡排序

冒泡排序的核心思想就是：两两相邻的元素进行比较和交换。
现在，我们想编写一个函数，使它能够运用冒泡排序的原理，由小到大排好一个乱序的整形数组。例如：假如输入5、2、1、10、9、7、3、4、8、6，能输出1、2、3、4、5、6、7、8、9、10。如果画图分许这个排序过程的每一步：
看，经过第一轮的两两比较，较大的数排到右边，这样最大的10就来到了最右边。
而经过第二次排序，第二大的9就能来到倒数第二个位置。

像这样继续排序，这个数组的大小是10，经过9次（10-1次）排序，就能完成1到10的排序。
知道了原理，在代码层面编写这样的函数就非常简单了：

void bubble_Sort(int* p ,int sz)
{
for(int turn=1 ; turn<=sz-1 ; turn++)//要排n个数字，就需要进行n-1轮排序for(int i=0 ; i<sz-1 ; i++)if(p[i] > p[i+1]){int tmp = p[i];p[i] = p[i+1];p[i+1] = tmp;}
}

当然，为了节省运行时间，我们还可以进行一点优化：假如这个数组在第一趟排序后就已经有序了，它就可以直接停止而没必要再排序好多次。

void bubble_Sort(int* p ,int sz)
{
for(int turn=1 ; turn<=sz-1 ; turn++)
{int flag = 1;//假设这一次已经有序了for(int i=0 ; i<sz-1 ; i++){if(p[i] > p[i+1]){flag = 0;//发生了交换说明这一次还不是有序int tmp = p[i];p[i] = p[i+1];p[i+1] = tmp;}}if(flag==1)break;//这一次没有发生交换，说明已经有序了，可以退出函数了
}
}

这样，整个程序就是：

#include<stdio.h>
void bubble_Sort(int* p ,int sz)
{
for(int turn=1 ; turn<=sz-1 ; turn++)
{int flag = 1;for(int i=0 ; i<sz-1 ; i++){if(p[i] > p[i+1]){flag = 0;int tmp = p[i];p[i] = p[i+1];p[i+1] = tmp;}}if(flag==1)break;
}
}int main()
{
int arr[10]={0};
for(int i=0 ; i<10 ; i++)scanf("%d",&arr[i]);
bubble_Sort(arr, sizeof(arr)/sizeof(arr[0]));
for(int i=0 ; i<10 ; i++)printf("%d ",arr[i]);
return 0;
}

结果也是非常的成功~

二、qsort排序

1. qsort使用指南

冒泡排序只能用来排序整型数字，而且写起来太麻烦了。如果我们有了一组数据，想要直接快速按某种方式排序，该怎么办呢？
乂~C语言提供了一个库函数qsort，可以按照你想要的方式排序各种类型的数据，使用它需要包含头文件stdlib.h
在链接https://legacy.cplusplus.com/reference/clibrary/中，我们可以查到：

借助翻译：
不理解也没关系，简言之，qsort函数的语法形式是：

void qsort(void* base, size_t num, size_t size, int(*compar)(const void*,const void*));

其中：

• base指针指向的是待排序数据中的第一个元素
• num是待排序数据的个数
• size是待排序数据中的每一个元素的字节大小
• compar是一个函数指针，这个函数用来比较base指向的数据中任意两个元素的大小
  注意：compar函数需要使用者自己提供，也就是要自己提供比较数据的方式。这个函数有两个参数（也就是要比较的两个元素），需要返回一个整型数。

不要着急，我们先来个简单的栗子：用qsort函数排序一个整型乱序数组：

#include<stdlib.h>
#include<stdio.h>
int compar_int(const void* p1, const void* p2)
{
return ( *(int*)p1 - *(int*)p2 );
//p1和p2一开始是void*指针，但是实际上他们指向的都是整型数据，所以要(int*)强制类型转换
}int main()
{
int arr[] = {5,2,1,10,9,7,3,4,8,6};//待排序数组
int sz = sizeof(arr)/sizeof(arr[0]);
qsort(arr, sz, sizeof(int), compar_int);
//arr：第一个元素的地址
//sz：元素个数
//sizeof(int)：每个元素的字节大小
//compar_int：用来比较的函数的地址
for(int i=0 ; i<sz ; i++)printf("%d ",arr[i]);
return 0;
}

很完美的结果。
但我们不禁思考，这个qsort函数是怎么依靠compar函数实现交换和排序的呢？
其实，qsort函数每次比较compar函数的两个参数，这两个指针参数指向的是任意的元素，依靠compar函数的返回值判断是否要交换：

• 返回值为负，就把p1指向的元素放在p2指向的元素后面；
• 返回值为0，不交换；
• 返回值为正，就把p1指向的元素放在p2指向的元素前面。

（这里“前”指的是数组下标较大的位置，“后”是下标较小的位置）

所以，上面的程序能实现由小到大的排序，而如果你想由大到小排，只需要把compar_int里的return ( *(int*)p1 - *(int*)p2 );改为return ( *(int*)p2 - *(int*)p1 );就可以了：

不光是整型，如果我们想把一个字符数组按照ASCII的大小排序，也可以使用qsort函数：

#include<stdlib.h>
#include<stdio.h>
int compar_char(const void* p1, const void* p2)
{
return ( *(char*)p1 - *(char*)p2 );
//p1和p2一开始是void*指针，但是实际上他们指向的都是字符型数据，所以要(char*)强制类型转换
}int main()
{
char arr[] = {'b','t','m','a','a','x'};//待排序数组
int sz = sizeof(arr)/sizeof(arr[0]);
qsort(arr, sz, sizeof(char), compar_char);
for(int i=0 ; i<sz ; i++)printf("%c ",arr[i]);
return 0;
}

2.回调函数

回调函数的概念很简单，它就是一个通过函数指针调用的函数。
如果你把函数的地址作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，被调用的函数就是回调函数了。回调函数不是由该函数的实现方直接调用的，而是在特定的条件下由另一方调用的，用于对该条件进行响应。

3. qsort函数的模拟实现

首先我要说的是，后期我们还会学习到很多的函数，他们都有不同的功能，但我们不仅要学会使用他们，还应该学会模拟实现这些函数。所谓模拟实现，是创造一个自己的函数，传递原函数相同的参数，也要能达到原函数的效果。今天，我们也应该学会模拟实现qsort函数。定义一个函数void Mine_qsort(void* base, size_t num, size_t size, int(*compar)(const void*,const void*));这就是我模拟实现的qsort函数。
而具体交换思路呢，可以分为比较、交换两步，运用了回调函数的概念和冒泡排序的思想。

#include<stdio.h>
int compar_int(const void* p1, const void* p2)
{
return (*(int*)p1 - *(int*)p2);
}void swap(const void* p1, const void* p2)
{
int tmp = *((int*)p1);
*((int*)p1) = *((int*)p2);
*((int*)p2) = tmp;
}void Mine_qsort(void* base, size_t num, size_t size, int(*compar)(const void*,const void*))
{
for(int turn=1 ; turn<=num-1 ; turn++)for(int i=0 ; i<num-1 ; i++)if(compar( (int*)base+i, (int*)base+i+1 ) > 0)swap( (int*)base+i, (int*)base+i+1 );
}int main()
{
int arr[]={2,6,4,10,5,3,1,8,7,9};
Mine_qsort(arr, sizeof(arr)/sizeof(arr[0]), sizeof(int), compar_int);
for(int i=0 ; i<10 ; i++)printf("%d ",arr[i]);
return 0;
}

这样，我们就模拟实现了qsort函数

然鹅，我的代码只能排序整型数组，如果要排序其他类型数据，也可以采用另外一种通法：一个字节一个字节地交换，这样能突破不同数据类型大小不同的限制。感兴趣的各位可以自行研究~

欲知后事如何，且听下回分解~

本篇完，感谢阅读