AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

C语言进阶之冒泡排序

2024-01-22 47
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： C语言进阶之冒泡排序

前情回顾

函数指针

我们有一个函数，为Add,我们将函数的地址用指针来存储，这个指针就叫做函数指针。

int Add(int x,int y)
{
    return x+y;
}
int main()
{
    int (*pf)(int,int) = Add;//pf就是函数指针。
    return 0;
}

函数指针数组

把函数指针放在数组中，就是函数指针的数组。

int Add(int x,int y)
{
    return x+y;
}
int Sub(int x,int y)
{
    return x-y;
}
int Mul(int x,int y)
{
    return x*y;
}
int Div(int x,int y)
{
    return x/y;
}
int main()
{
    int (*arr[4])(int ,int) = {Add,Sub,Mul,Div};//这个就是函数指针数组。
    return 0;
}

函数指针数组就可以调用函数：

int main()
{
    int i = 0;
    scanf("%d",&i);
    int ret = arr[i](8,4);
    printf("%d\n",ret);
}

1、回调函数

回调函数就是应该通过函数指针调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。回调函数不是由这个函数的实现方直接调用，而是在特定的事件或条件发生时由另外的一方调用的，用于对该事件或条件进行响应。


我们可以把Add函数称为回调函数。

int Add(int x,int y)
{
    return x+y;
}
int main()
{
    int (*pf)(int,int) = Add;
    int ret = pf(8,4);
    return 0;
}

2、冒泡排序

对一个数组进行升序排序。

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 };
    //把数组排成升序
    int sz = sizeof(arr)/sizeof(arr[0]);
    bubble_sort(arr,sz);
    int i = 0;
    for(i=0;i<sz;i++)
    {
        printf("%d",arr[i]};
    }

这个冒泡排序不够高效，如果我们进行一趟冒泡排序，但是一个数字都没有交换，就说明这个数组已经排序好了，就不用继续排序了，

我们可以通过，在进行这一趟冒泡排序前设定int flag = 1;

如果数字进行了交换，就把flag的值改为0；

没有数字进行交换，那么flag的值还是1；

我们通过判断flag的值看数组是否已经排好序。

void bubble_sort(int arr[],int sz)
{
    int i=0;
    //趟数
    for(i=0;i<sz-1;i++)
    {
        int flag = 1;//假设数组是排好序的。
        //一趟冒泡排序的过程
        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;
                flag = 0;//数组进行了排序
            }
        }  
        if(flag == 1)
        {
            break;
        }    
    }
}
int main()
{
    int arr[] = {9,8,7,6,5,4,3,2,1 };
    //把数组排成升序
    int sz = sizeof(arr)/sizeof(arr[0]);
    bubble_sort(arr,sz);
    int i = 0;
    for(i=0;i<sz;i++)
    {
        printf("%d",arr[i]};
    }
    return 0;
}

3、库函数qsort

使用快速排序的思想实现的一个排序函数。

qsort可以排序任何类型的数据

void qsort(void* base,//你要排序的数据的起始位置
           size_t num,//待排序的数据元素的个数
           size_t width,//待排序的数据元素的大小(单位是字节)
           int(* cmp)(const void* e1,const void* e2)//函数指针-比较函数
           );

cmp（sqort中的比较函数，需要我们自定义）

int(* cmp)(const void* e1,const void* e2)中的e1,e2就是我们要比较数据的地址。

在这个比较函数中我们实现不同类型的元素比较

void*是无具体类型的指针，可以接收任何类型的地址

void*是无具体类型的指针，所以不能解引用操作，也不能+-整数

当比较函数返回的是大于0的数字，那么两组数据就会进行交换。

进行整型数据的比较， 这是进行升序排列

int cmp_int(const void* e1,const void* e2)
{
   return (*(int*)e1 - *(int*)e2);
}

整形的升序排列

通过qsort来将数组进行升序排序

//比较两个整形元素
//e1指向一个整形
//e2指向另外一个整形
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void* e1,const void* e2)
{
    return (*(int*)e1 - *(int*)e2);
}
int main()
{
    int arr[] = {9,8,7,6,5,4,3,2,1};
    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]);
    }    
    return 0;
}

cmp_int就是回调函数

整形的倒序排列

当我们需要进行降序排列，只要将e2和e1的顺序倒过来就可以实现

int cmp_int(const void* e1,const void* e2)
{
    return (*(int*)e2 - *(int*)e1);
}

结构体的排序

结构体按照名字(char类型)排序

char类型的数据不能够直接比较，我们用到strcmp进行比较，

库函数strcmp

头文件<string.h>

int strcmp( const char *string1, const char *string2 );

如果string1小于string2，就会返回小于0的数

如果string1等于string2，就会返回0

如果string1大于string2，就会返回大于0的数

#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[] = {{"zhangsan",15},{"lisi",30},{"wangwu",25}};
    int sz = sizeof(s) / sizeof(s[0]);
    qsort(s,sz,sizeof(s[0]),cmp_stu_by_name);
    return 0;
}

cmp_stu_by_name就是回调函数

结构体按照年龄(int类型)排序

#include<stdlib.h>
#include<string.h>
struct Stu
{
    char name[20];
    int age;
};
int cmp_stu_by_age(const void*e1,constvoid* e2)
{
     return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
int main()
{
    struct Stu s[] = {{"zhangsan",15},{"lisi",30},{"wangwu",25}};
    int sz = sizeof(s) / sizeof(s[0]);
    qsort(s,sz,sizeof(s[0]),cmp_stu_by_age);
    return 0;
}

库函数qsort的模拟实现（bubble_sort）

如何实现qsort函数？库函数qsort的设计原理是什么？

创建自定义函数实现库函数qsort的功能。

基于qsort实现原理，实现将整形数组升序排列

设计自定义函数bubble_sort，等同于库函数qsort

void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

base：数据的起始位置，首元素的地址

sz: 数据元素的个数，比较数组的话，就是数组中元素的个数

width:待排序的数据元素的大小(单位是字节),比较整形数组的话，就是4个字节，数组元素占内存的大小

cmp:自定义的比较函数。

关于bubble_sort的设计细节

这是我们对解决整形数组升序排列问题，也就是冒泡排序，原来的的bubble_sort.

但是我们现在要设计的bubble_sort，需要与qsort有相同的功能（排序任何类型的数据）

void bubble_sort(int arr[],int sz)
{
    int i=0;
    //趟数
    for(i=0;i<sz-1;i++)
    {
        int flag = 1;//假设数组是排好序的。
        //一趟冒泡排序的过程
        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;
                flag = 0;//数组进行了排序
            }
        }  
        if(flag == 1)
        {
            break;
        }    
    }
}

1.

void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))

参数void类型可以接收任何类型的数据

2.

判断大小，

原来：数组元素比较大小

现在：比较一种无知类型元素大小，通过比较函数（cmp）来比较，由于我们不知道要比较的元素类型是什么，但是我们要找到每个元素的地址，就通过（char*)base + j * width,

第一个元素的地址就是首元素的地址，

第二个元素的地址就是首元素的地址加上一个元素的字节

width:待排序的数据元素的大小(单位是字节)

在bubble_sort中，cmp((char*)base + j * width, (char*)base + (j + 1) * width)

3.

自定义函数（cmp）的实现，已知我们要比较的是整形元素的大小，和库函数qsort解决整形的升序排列一样

int cmp_int(const void* e1, const void* e2)
{
  return *(int*)e1 - *(int*)e2;
}

4.

交换元素

cmp_int的功能

当比较函数返回的是大于0的数字，那么两组数据就会进行交换。

进行整型数据的比较， 这是进行升序排列

在bubble_sort中，当cmp判断>0时

if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)

进行交换

交换函数

我们要找到各个元素我们才能进行比较，所以和cmp函数的实现类似，

我们要传递的参数

Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);

找到了各个元素的地址，也知道元素的大小（字节），就可以进行比较，

一个一个字节进行比较，

Swap函数实现：

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++;
  }
}

5.

为了函数的高效性，我们把原来的flag的设计保留。

也就是int flag = 1;(假设数组已经排列好）

如果在这一趟的冒泡排序的过程中，数字进行了交换，就把flag的值改为0；

没有数字进行交换，那么flag的值还是1，就可以直接跳出循环；

呈现bubble_sort函数的整体代码：

#include<stdio.h>
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++;
  }
}
int cmp_int(const void* e1, const void* e2)
{
  return *(int*)e1 - *(int*)e2;
}
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
  int i = 0;
  //趟数
  for (i = 0; i < sz - 1; i++)
  {
    int flag = 1;//假设数组是排好序
    //一趟冒泡排序的过程
    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);
        flag = 0;
      }
    }
    if (flag == 1)
    {
      break;
    }
  }
}
int main()
{
  int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
  //0 1 2 3 4 5 6 7 8 9
  //把数组排成升序
  int sz = sizeof(arr) / sizeof(arr[0]);
  //bubble_sort(arr, sz);
  bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    printf("%d ", arr[i]);
  }
}


bubble_sort的结构体排序

前面有完整的bubble_sort的实现，这里就不把bubble_sort写上了

#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);
}
void test()
{
  struct Stu s[] = { {"zhangsan", 15}, {"lisi", 30}, {"wangwu", 25} };
  int sz = sizeof(s) / sizeof(s[0]);
  bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_name);
  //bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}
int main()
{
  test();
  return 0;
}

age:

name:




文章标签：
C语言
存储
关键词：
C语言冒泡排序
C语言进阶
C语言进阶冒泡排序
猪巴戒
目录
相关文章
写代码的大学生
|
5月前
|
C语言
指针进阶（C语言终）
指针进阶（C语言终）
写代码的大学生
59 4
可惜已不在
|
24天前
|
算法 搜索推荐 C语言
【C语言】冒泡排序+优化版
【C语言】冒泡排序+优化版
可惜已不在
16 1
ephemerals__
|
11天前
|
C语言
【c语言】qsort函数及泛型冒泡排序的模拟实现
本文介绍了C语言中的`qsort`函数及其背后的回调函数概念。`qsort`函数用于对任意类型的数据进行排序，其核心在于通过函数指针调用用户自定义的比较函数。文章还详细讲解了如何实现一个泛型冒泡排序，包括比较函数、交换函数和排序函数的编写，并展示了完整的代码示例。最后，通过实际运行验证了排序的正确性，展示了泛型编程的优势。
ephemerals__
12 0
笨笨小乌龟
|
4月前
|
搜索推荐 C语言
C语言冒泡排序（附源码和动态图）
冒泡排序是一种简单的排序算法，其基本思想是通过重复遍历待排序的数列，比较每对相邻元素的值，如果它们的顺序错误（即满足一定的排序条件，如从小到大排序时前一个元素大于后一个元素），就交换它们的位置。这个过程就像水底的气泡一样逐渐向上冒，因此得名“冒泡排序”。
笨笨小乌龟
45 1
就学呗
|
5月前
|
数据库 C语言
C语言进阶 文件操作知识（上）
C语言进阶 文件操作知识（上）
就学呗
36 3
就学呗
|
5月前
|
存储 C语言
C语言进阶 文件操作知识(下)
C语言进阶 文件操作知识(下)
就学呗
37 2
码农阿豪
|
5月前
|
Java 程序员 Linux
探索C语言宝库：从基础到进阶的干货知识(类型变量+条件循环+函数模块+指针+内存+文件)
探索C语言宝库：从基础到进阶的干货知识(类型变量+条件循环+函数模块+指针+内存+文件)
码农阿豪
45 0
好奇的菜鸟
|
5月前
|
算法 搜索推荐 C语言
C语言冒泡排序介绍
C语言冒泡排序介绍
好奇的菜鸟
44 0
倔强的石头_
|
5月前
|
存储 C语言 C++
【C语言刷题系列】水仙花数的打印及进阶
【C语言刷题系列】水仙花数的打印及进阶
倔强的石头_
46 0
aliyun1622584902-46568
|
5月前
|
C语言
C语言----冒泡排序
C语言----冒泡排序
aliyun1622584902-46568
28 0