𝙉𝙞𝙘𝙚!!👏🏻???????👏🏻??????? 👏🏻?????:Solitary-walk
? ? ? ?? ? ━━━┓
? ? ?- 个性标签 - :来于“云”的“羽球人”。 Talk is cheap. Show me the code
┗━━━━━━━ ?? ?本人座右铭 : ? 欲达高峰,必忍其痛;欲戴王冠,必承其重。
👑💎💎👑💎💎👑?
💎💎💎自💎💎💎
💎💎💎信💎💎💎
👑💎💎 💎💎👑 ? ?希望在看完我的此篇博客后可以对你有帮助哟👑👑💎💎💎👑👑 ? 此外,希望各位大佬们在看完后,可以互赞互关一下,看到必回
👑👑👑💎👑👑👑
首先我们需要先知道冒泡排序的核心是:两两相邻元素进行比较
冒泡排序的底层逻辑就是 ?双重for循环
1)外循环:需要进行9次比较对应代码
```c
for(int i = 0;i < sz - 1;i++)
```
2)内循环:一趟循环所需要比较的轮次
```c
for(int j = 0;j < sz-1-i;j++)
```
要求:对数组的各个数据按升序进行排列
首先我们先两两相邻元素进行比较:
第一趟比较后对应结果:
对应核心代码:
```c
if (arr[j] > arr[j + 1])
{
?? ?//交换
?? ?tmp = arr[j];
?? ?arr[j] = arr[j + 1];
?? ?arr[j + 1] = tmp;
}
```
```cpp
??
void bubble(int arr[], int sz)
{
?? ?for (int i = 0; i < sz - 1; i++)//确定总的趟数
?? ?{
?? ??? ?for (int 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[] = { 1,4,7,8,5,2,9,6,3,0 };
?? ?int sz = sizeof(arr) / sizeof(arr[0]);
?? ?bubble(arr, sz);
return 0;
}
}
```
其实对于这个代码还有很多地方可以进行优化,使之变得更具有鲁棒性
> 比如说,当我们这一趟的数据已经是有序的,我们就不需要再次进行比较了,以此节省效率
优化之后的版本:
void bubble(int arr[], int sz)
{
?? ?//确定sz 个元素对应的趟数;sz - 1
?? ?for (int i = 0; i < sz - 1; i++)
?? ?{
?? ??? ?//一趟冒泡排序的 执行
?? ??? ?int flag = 1;//假设一趟是有序的
?? ??? ?for (int 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;
?? ??? ??? ??? ?flag = 0;//这一趟是无序的
?? ??? ??? ?}
?? ??? ?}
?? ??? ?if (flag == 1)
?? ??? ?{
?? ??? ??? ?break;//直接终止循环,无需在进行排序,提高了效率
?? ??? ?}
?? ?}
}
void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*)); 参数介绍: void*base:指向待排序的第一个元素的地址size_t num:待排序元素的个数
size_t size:待排序的每一个元素的大小,单位字节
int (*compar)(const void*,const void*)) :函数指针,用来实现数据的排序,需要使用者自己? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 设计,注意这里参数类型不能改变
对整型数据排序:
int cmp_int(const void* p1, const void* p2)
{
//return (*p1 - *p2);//err 对于void* 类型的指针只能进行强转,之后在进行解引用或者是指针运算
return (*(int*)p1 - *(int*)p2);
}
void Print(int* parr, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ", *(parr + i));
}
}
int main()
{
int arr[] = { 7,4,1,8,5,2,9,6,3,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
qsort(arr, sz, sizeof(int), cmp_int);
Print(arr, sz);
return 0;
/*
直接对void*类型的指针解引用出现:非法的间接寻址
对于void*类型的指针只能进行强转,之后在进行解引用或者是指针运算
*/
}
?
?qsort()函数不是很牛吗,接下来看看对结构体类型数据排序如何?
对结构体类型数据进行排序:
struct Student
{
char name[10];
int age;
};
int cmp_by_name(const void* p1, const void* p2)
{
//return (*(char*)p1 - *(char*)p2); //注意字符串比较不能直接相减,借助strcmp()函数
//int strcmp ( const char * str1, const char * str2 );
return strcmp ((char*)p1 , (char*)p2);
}
int main()
{
/*int arr[] = { 7,4,1,8,5,2,9,6,3,0 };
int sz = sizeof(arr) / sizeof(arr[0]);*/
struct Student arr1[] = { {"wisi,12"},{"langwu",14},{"zhangsan",13} };
qsort(arr1, 3, sizeof(struct Student), cmp_by_name);
return 0;
/*
直接对void*类型的指针解引用出现:非法的间接寻址
对于void*类型的指针只能进行强转,之后在进行解引用或者是指针运算
*/
}
这是排序之前数组的内容:?
排序之后数组的内容:(注意是根据名字这个成员进行排序,也就是按对应位置的字母ASCII值进行比较)
?
思路的分析:
1)首先知道冒泡排序的核心:两两相邻元素进行比较
2)qsort( )各个参数意义:见文章上面介绍
3)void*类型指针应用的小注意
4)借助画图更易于理解
?以交换整型数据为例:
首先我们需要思考2个重要问题:
你有思绪了吗?没关系,接下来,我们一起来分析:
? ? ? ? 我们需要借助一个函数指针,来实现对数据的比较;其次这里对指针的使用是有要求的,因为数据类型可以是任意的:int,long,float,结构体.......
那我们这里到底使用什么类型指针?
? ? ? ?毋庸置疑:char*? ,它是最小的,对他进行解引用是一个字节一个字节的,这样就会避免我们对指针访问不精确的问题
对应核心代码:注意这里我们假设以升序来排列
还是以整型数据来进行分析:
因为已经知道每个元素大小:width,
要比较的第一个元素地址已知
注意对 void* 类型指针不能直接用这里借助强转
下标为 j 对应地址? ?(char*)base + j * width
下标为 j + 1对应地址? ?(char*)base +( j+1) * width
?
// 假设按升序来排序
if (cmp_int((char*)base + j * width, (char*)base + (j + 1) * width) > 0) //借助cmp_int来进行判断大小,需要把当前下标为j ,j+1 的地址传进去 ,重点是以什么类型指针来传进去
这里我们另写一个交换函数Swap( ) ,避免看起来复杂
? 其实这个问题和上一个大同小异,既然是要交换元素,必然传地址,那么以什么类型指针接收呢?
显然是char*,同时我们还需要把这个要比较元素的大小传进来,
?
对应核心代码:
void Swap( char* p1, char* p2,int size) //注意这里必须把要比较每一个元素大小传来
{
// 一个字节一个字节交换
char tmp = 0;
for (int i = 0; i < size; i++)
{
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
// p1,p2更新位置
p1++, p2++;
}
}
int cmp_int(const void* p1, const void* p2)
{
//return (*p1 - *p2);//err 对于void* 类型的指针只能进行强转,之后在进行解引用或者是指针运算
return (*(int*)p1 - *(int*)p2);
}
void Swap( char* p1, char* p2,int size) //注意这里必须把要比较每一个元素大小传来
{
// 一个字节一个字节交换
char tmp = 0;
for (int i = 0; i < size; i++)
{
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
// p1,p2更新位置
p1++, p2++;
}
}
void my_qsort(void* base, int num,int width,int (*cmp_int)(const void*,const void*))
{
//借助冒泡进行排序
for (int i = 0; i < num - 1; i++) //确定趟数
{
for (int j = 0; j < num - 1 - i; j++) //一趟的比较
{
// 假设按升序来排序
if (cmp_int((char*)base + j * width, (char*)base + (j + 1) * width) > 0) //借助cmp_int来进行判断大小,需要把当前下标为j ,j+1 的地址传进去 ,重点是以什么类型指针来传进去
{
// 进行交换
Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);//把下标为j 和j+1的地址传进去
}
}
}
}
int main()
{
int arr[] = { 7,4,1,8,5,2,9,6,3,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
//struct Student arr1[] = { {"wisi,12"},{"langwu",14},{"zhangsan",13} };
my_qsort(arr, sz, sizeof(arr[0]), cmp_int);
Print(arr, sz);
return 0;
/*
直接对void*类型的指针解引用出现:非法的间接寻址
对于void*类型的指针只能进行强转,之后在进行解引用或者是指针运算
*/
}
?
?接下来我们试一下看看对结构体类型的数据排序效果如何
?
?ok~~~以上就是今日要为大家分享的。要是觉得还不错的话,希望咱一波赞走起,给个关注,同时也蟹蟹各位大佬的支持,看到必回!!!