一. 冒泡排序的思想以及初阶代码实现
我们先写出下面的这样一个数组
int arr[] = { 2,1,5,8,7,4,3,6,9,0,10 };
现在有要求如下：
设计一个函数 能够将这个数组升序排序
这个时候我们脑子里冒出来的第一个算法应该就是我们的冒泡排序了
1. 思想
对于这样的一个整型数组 我们只需要将它的每一个数和后面一个数比较大小 如果前面的一个数比后面的一个数大 那么我们就交换这两个数的位置 一趟下来 我们就可以将最大的一个数放到最后面 那么只需要经历数组元素个数减一次比较 我们就可以对整个数组完成一个升序排序
2. 简单的代码实现
bubble_sort(int arr[], int sz) { // 执行一趟排序 int i = 0; int j = 0; for ( i = 0; i < sz-1; i++) { //前面一个数与后面一个数比较大小 如果大于就交换位置 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; } } } }
简单的代码实现如上所示
现在我们来测试一下
创造一个print函数在使用冒泡排序之后打印数组arr里面的每一个元素
print函数的实现代码如下
Print(int arr[],int sz) { bubble_sort(arr, sz); for (int i = 0; i < sz; i++) { printf("%d\n", arr[i]); } }
实现效果如下
我们可以发现这段代码可以完美的实现一个升序操作
那么完美可以说这段冒泡排序代码是一个完美的代码嘛？
在回答这个问题之前 我们先来看另一个库函数的使用
二. qsort（）库函数的传参及使用
1. 定义
我们先到cpp网站浏览下qsort函数到底是什么样的
qsort函数的定义如下
我们可以发现 它需要传入四个参数 我们一个个来分析下
2. 四个参数
void* base 是一个无符号指针
（这里要注意的是void可以接受任何类型的地址 但是却不能去改变它们的内容
要想改变只能强转地址之后再改变）
Pointer to the first object of the array to be sorted, converted to a void*.
从这一段我们可以知道 它其实就是指向一个数组的首元素地址
sisz_t num 数量
Number of elements in the array pointed to by base.
size_t is an unsigned integral type.
这个很简单传递数组的数量进去就好
sisz_t size 大小
Size in bytes of each element in the array.
size_t is an unsigned integral type.
这个也很简单 元素的大小传递进去就可以
int (compar)(const void,const void*) 一个函数指针 指向了一个比较函数
Pointer to a function that compares two elements.
This function is called repeatedly by qsort to compare two elements. It shall follow the following prototype:
int compar (const void* p1, const void* p2);
这个参数稍微有点复杂 首先它是一个指针 它需要指向一个函数 这个函数具有比较两个数的功能 它需要我们输入两个无返回值的指针 形式如下
int compar (const void* p1, const void* p2);
那么我们就拿我们的arr数组来实验一下
传参格式如下
qsort( arr, sz, sz1, cmp);
cmp函数实现格式如下
int cmp(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; }
实现效果如下
我们可以发现这样子也是可以实现数组的排序的
那么这样子写的好处是什么呢？
我们说 如果我们想实现字符串的排序 乃至结构体的排序那么前一种冒泡排序的代码便失效了
因为它只能比较整型数组 我们来实验一下结构体的排序
我们可以发现 完全可以实现字符串的排序
三 bubble_sort重定义
既然知道了qsort（）的使用方法
那么我们可不可以使用bubble_sort()模仿qsort（）写一个类似的函数呢
我们来尝试下
首先跟着qsort（）的参数 我们来设计bubble_sort的参数
void bubble_sort(void * base,size_t num,size_t size,int(*cmp)(const void*e1,const void*e2))
那么我们应该如何实现两个的比较呢？
我们传进去的两个指针是个无符号的指针 想要找到下面的数字是不可能的
但是我们可以先将这两个指针转化成char类型的指针 然后再使用j*size的格式来找个各个元素并且比较大小
代码表示如下
if (cmp((char*)base+j*size,(char*)base+(j+1)*size)>0)
cmp函数
int cmp(const void* e1,const void *e2) { return (*(int*)e1) - (*(int*)e2); }
交换两个函数的代码表示如下
这里给大家讲解下为什么这么做
我们都知道再计算机中 数字是以字节的形式存放的 假设我们要交换两个数据的内容 我们只需要交换它们每一个字节的内容就好了
再这样子的思想知道下 我们可以用两个字符指针
交换它们这个字节内部储存的数据 交换x次（x为这个数据的大小 因为都是以字节为单位的）
就可以完全交换这两个数字的顺序啦
这样的好处是我们没有指定数据类型
任何类型的数据我们都可以交换
void swap(char* e1, char* e2,size_t size) { char tmp = 0; for (int i = 0; i < size; i++) { tmp = *e1; *e1 = *e2; *e2 = tmp; e1++; e2++; } }
完成的冒泡排序重定义代码表示如下
void bubble_sort(void * base,size_t num,size_t size,int(*cmp)(const void*e1,const void*e2)) { // 执行一趟排序 int i = 0; int j = 0; for (i = 0; i < num - 1; i++) { //前面一个数与后面一个数比较大小 如果大于就交换位置 for (j = 0; j < num - 1 - i; j++) { if (cmp((char*)base+j*size,(char*)base+(j+1)*size)>0) { swap((char*)base + j * size, (char*)base + (j + 1) * size, size); } } } }
我们来看看结果
可以完美运行
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够
不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
