C语言冒泡排序法和amp;Qsort函数和自定义实现八大排序:二

目录

冒泡排序原理

冒泡排序代码

库函数中的Qsort函数

• qsort函数原型
• 各个参数的说明

Qsort函数自定义实现

• 1、先定义出一个void bubble_sort函数，四个参数
• 2、自定义的函数体
• 3、if语句内的条件、Swap函数的参数

自定义类似Qsort函数代码

---

冒泡排序原理

 是一种较简单的排序算法，依次比较相邻元素，如果顺序错误则进行调换（A ~ Z，或数字），算法的核心在于依次比较，依次调换位置

冒泡排序升序： 

如：3，1，4，2

升序后：1，2，3，4

第一批比较：

3>1，所以1和3互换：1，3，4，2

3<4，所以3和4位置不变

4>2，所以4和2互换：1，3，2，4

第一批比较完毕，调换了3次。此时最大数4已经放在了最末尾，所以4不再进行比较排序。

第二批比较：

1<3，所以1和3位置不变

3>2，所以2和3交换：1，2，3，4

到此，其实结果已经出来了，但是根据冒泡排序原理：

第一批是将4放在了末尾，第二批是将3放在了倒数第二位。所以还剩下1和2没有排序。

第三批比较：

1<2：所以1和2位置不变。

---

从简单的1，2，3，4序列进行冒泡排序的理解。

我们可以得知：n个数的第一批进行n-1次比较排序。

（所以最外层是n-1次循环）

1.  
   for(int i =1; i<n; i )
2.  
   {
3.  
    
4.  
   }

对于内层分析：

第一批：n-1次比较循环

第二批：n-2次比较循环

...

第i批：n-i次比较循环

1.  
   for(int i=1;i<n;i )
2.  
   {
3.  
    
4.  
   for(int j=0;j<n-1-i;j )/*j从0开始，因为数组下标从0开始*/
5.  
   {
6.  
   if (num[j] < num[j 1])
7.  
   {
8.  
   int temp = num[j];
9.  
   num[j] = num[j 1];
10.  
    num[j 1] = temp;
11.  
    }
12.  
    }
13.  
     
14.  
    }
15.  
    //为什么是n-1-i？

 j的范围

j从0开始：数组下标从0开始

进行第i次循环：n-i

因为是num[j]和num[j 1]进行比较，所以要保证 j 1 不越界

所以j 1<n-i

j<n-1-i

冒泡排序代码

1.  
   #include <stdio.h>
2.  
   #define N 10
3.  
   void print(int* parr)
4.  
   {
5.  
   int i = 0;
6.  
   for (i = 0; i < 10; i )
7.  
   {
8.  
   printf("%d ", *(parr i));
9.  
   }
10.  
    }
11.  
    void Bubble_Sort(int num[], int n)
12.  
    {
13.  
    int flag = 1;
14.  
    for (int i = 0; i < N-1; i )//有10个元素，则循环9次
15.  
    {
16.  
    for (int j = 0; j < N - 1 - i; j )//N-1表示末端元素下标，因为后续有j 1，所以j不取等
17.  
    {
18.  
    if (num[j] > num[j 1])//从0号元素开始，相邻进行比较
19.  
    {
20.  
    int temp = num[j];
21.  
    num[j] = num[j 1];
22.  
    num[j 1] = temp;
23.  
    flag = 0;
24.  
    }
25.  
    }
26.  
    if(flag) break;
27.  
    }
28.  
    }
29.  
     
30.  
    int main()
31.  
    {
32.  
    //相邻两个元素进行比较，大的放后面。n个元素比较n-1次
33.  
    int arr[N] = { 12,33,4,57,9,100,123,32,87,98 };
34.  
     
35.  
    printf("原数顺序：>");
36.  
    print(arr);
37.  
     
38.  
    Bubble_Sort(arr, N);
39.  
     
40.  
    printf("\n冒泡排序后顺序：>");
41.  
    print(arr);
42.  
     
43.  
    return 0;
44.  
    }

 如果要进行降序的冒泡排序，只需要把if中的大于号改成小于号即可：

1.  
   void Reverse_Bubble(int num[], int n)
2.  
   {
3.  
   for (int i = 1; i < N; i )//有10个元素，则循环9次
4.  
   {
5.  
   for (int j = 0; j < N - 1 - i; j )//N-1表示末端元素下标，因为后续有j 1，所以j不取等
6.  
   {
7.  
   if (num[j] < num[j 1])//从0号元素开始，相邻进行比较
8.  
   {
9.  
   int temp = num[j];
10.  
    num[j] = num[j 1];
11.  
    num[j 1] = temp;
12.  
    }
13.  
    }
14.  
    }
15.  
    }

---

库函数中的Qsort函数

qsort函数（quick sort）C语言编译器函数库自带的排序函数；

包含在C 标准库 - <stdlib.h>中。

对一维数组、二维数组、字符串、结构体、结构体中的字符串等等进行快速排序。

qsort函数原型

 

各个参数的说明

base：将首元素的地址传给qsort函数，确定开始排序的位置。 

num：排序元素的个数。

size：排序的元素的（大小），单位是字节。由于qsort函数可以排序大部分类型的数据，输入数据类型，将void*强制类型转化为int*或char*等，由此导致了qsort函数的普适性。

自定义compar函数：你需要告诉qsort函数，你需要如何进行比较，进行升序排列还是降序排列，如何自定义一个compar函数即可。用来比较待排序数据中两个元素的大小。

返回值：

1、后一个元素更大：返回值小于0

2、两个元素一样大：返回值等于0

3、前一个元素更大：返回值大于0

qsort函数使用示例1（数字排列）：>

1.  
   #include <stdio.h>
2.  
   #include <stdlib.h>
3.  
    
4.  
   int arr[] = { 2, 3, 6, 5, 4, 1 };//要排序的数组
5.  
   int sz = sizeof(arr) / sizeof(arr[0]);//数组元素个数
6.  
    
7.  
   int compare(const void* a, const void* b)
8.  
   {
9.  
   return (*(int*)a - *(int*)b);
10.  
    }
11.  
     
12.  
    int main()
13.  
    {
14.  
    int n;
15.  
    qsort(arr, sz, sizeof(int), compare);
16.  
    for (n = 0; n < 6; n )
17.  
    printf("%d ", arr[n]);
18.  
     
19.  
    return 0;
20.  
    }//输出结果：> 1 2 3 4 5 6
21.  
    //如果需要降序，只需将compare函数中return改为b-a的形式即可

 qsort函数使用示例2（结构体成员按照序号排列&按照名字排列）：>

1.  
   #include <stdio.h>
2.  
   #include <stdlib.h>
3.  
   struct Stu
4.  
   {
5.  
   char name[20];
6.  
   int num;
7.  
   };
8.  
   int sort_by_num(const void* a, const void* b)//使用const增加常属性，防止比较的数据被改变
9.  
   {
10.  
    return ((struct Stu*)a)->num - ((struct Stu*)b)->num;
11.  
    }
12.  
    int sort_by_name(const void* a, const void* b)
13.  
    {
14.  
    return strcmp(((struct Stu*)a)->name, ((struct Stu*)b)->name);
15.  
    }
16.  
    int main()
17.  
    {
18.  
    struct Stu s[] = { {"一号",1},{"四号",4},{"三号",3},{"五号",5},{"二号",2}};
19.  
    int sz = sizeof(s) / sizeof(s[0]);
20.  
    printf("排序前：>\n");
21.  
    for (int i = 0; i < sz; i )
22.  
    printf("%s %d ", s[i].name, s[i].num);
23.  
    //按照序号排序
24.  
    qsort(s, sz, sizeof(s[0]), sort_by_num);
25.  
    printf("\n按照序号排序后：>\n");
26.  
    for (int i = 0; i < sz; i )
27.  
    printf("%s %d ", s[i].name, s[i].num);
28.  
    //按照名字排序（a~z）
29.  
    qsort(s, sz, sizeof(s[0]), sort_by_name);
30.  
    printf("\n按照序号排序后：>\n");
31.  
    for (int i = 0; i < sz; i )
32.  
    printf("%s %d ", s[i].name, s[i].num);
33.  
    }

---

Qsort函数自定义实现

模仿qsort函数的原型，自定义一个通用的冒泡排序bubble_sort：

1、自定义bubble_sort函数

2、自定义compare函数（下面简化为cmp函数）

3、交换函数Swap（使用空瓶、异或操作符）

1、先定义出一个void bubble_sort函数，四个参数

2、自定义的函数体

//与冒泡排序原理相似，唯一的区别在于上述冒泡排序函数功能单一
    int i = 0;
    for (i = 0; i < sz - 1; i )
    {
        int j = 0;
        for (j = 0; j < sz - 1 - i; j )
        {

                if(表达式大于0)
            {
                //条件满足则进行交换
                Swap(参数);

             }

         }

     }

3、if语句内的条件、Swap函数的参数

数据处理：

对于一个数组两个元素比较即： arr[ j ] 与 arr[ j 1 ]

在指针中就是：  *( arr j ) 与 *( arr j 1)

参照自定义函数写成： *(base j) 与 *(base j 1)

由于是void函数，类型大小用size表示，size表示类型大小（字节）

所以最终表述为：  (*base) j*size 与 (*base) (j 1)*size

补充一下细节：

• 比较两个元素，传入两个元素的地址给cmp函数
• char是1byte，可以随意改变访问的跨度
• 加上一个元素所占字节就可以跳到下一个元素
• 所以用char*base表示首地址，由于是函数参数是void*
• 所以强制类型转换(char*)base表示数据首地址

if语句：将两个数据放入cmp函数中，判断返回值是否大于0

Swap函数：交换两个指针变量即可，下列代码用空瓶实现（优化可以用^进行交换）

1.  
   void Swap(char* bu1, char* bu2, int sz)
2.  
   {
3.  
   int i = 0;
4.  
   for (i = 0; i < sz; i )
5.  
   {
6.  
   char tmp = *bu1;
7.  
   *bu1 = *bu2;
8.  
   *bu2 = tmp;
9.  
   bu1 ;
10.  
    bu2 ;
11.  
    }
12.  
    }
13.  
    void bubble_sort(
14.  
    void* base,//第一个元素地址
15.  
    int sz, //元素个数
16.  
    int size, //元素类型（大小）
17.  
    int(*cmp)(const void* a, const void* b)//自定义函数compare
18.  
    )
19.  
    {
20.  
    int i = 0;
21.  
    //进行排序的趟数
22.  
    for (i = 0; i < sz - 1; i )
23.  
    {
24.  
    int j = 0;
25.  
    for (j = 0; j < sz - 1 - i; j )
26.  
    {
27.  
    if (cmp((char*)base j*size,(char*)base (j 1)*size) > 0)
28.  
    {
29.  
    //条件满足则进行交换
30.  
    Swap((char*)base j * size, (char*)base (j 1) * size,size);
31.  
    }
32.  
    }
33.  
    }
34.  
    }

 代码看起来好像很复杂，是因为要交换的元素书写比较复杂，理解如下：

if ( cmp(参数1，参数2) > 0 )

Swap(参数1，参数2)

 最后，只需要将qsort函数注释掉，用bubble_sort函数进行实现即可，代码如下

自定义类似Qsort函数代码

1.  
   //头文件引入
2.  
   #include <stdio.h>
3.  
   #include <string.h>
4.  
   //函数声明
5.  
   void Swap(char* bu1, char* bu2, int sz);
6.  
   int cmp_int(const void* a, const void* b);
7.  
   int cmp_by_num(const void* a, const void* b);
8.  
   int cmp_by_name(const void* a, const void* b);
9.  
   void bubble_sort(void* base, int sz, int size, int(*cmp)(const void* a, const void* b));
10.  
    //结构体声明
11.  
    struct Stu
12.  
    {
13.  
    char name[20];
14.  
    int num;
15.  
    };
16.  
     
17.  
    //主函数
18.  
    int main()
19.  
    {
20.  
    int arr[] = { 2, 3, 6, 5, 4, 1 };//要排序的数组
21.  
    int sz_arr = sizeof(arr) / sizeof(arr[0]);
22.  
    //要排序的结构体成员
23.  
    struct Stu s[] = { {"一号",1},{"四号",4},{"三号",3},{"五号",5},{"二号",2} };
24.  
    int sz_s = sizeof(s) / sizeof(s[0]);
25.  
    printf("排序前的数组>\n");
26.  
    for (int i = 0; i < sz_arr; i )
27.  
    printf("%d ", arr[i]);
28.  
    printf("\n排序前的结构体成员>\n");
29.  
    for (int i = 0; i < sz_s; i )
30.  
    printf("%s %d ", s[i].name, s[i].num);
31.  
    //开始排序
32.  
    bubble_sort(arr, sz_arr, sizeof(arr[0]), cmp_int);
33.  
    bubble_sort(s, sz_s, sizeof(s[0]), cmp_by_num);
34.  
     
35.  
    printf("\n排序后的数组：>\n");
36.  
    for (int i = 0; i < sz_arr; i )
37.  
    printf("%d ", arr[i]);
38.  
    printf("\n按序号排序后的结构体成员>\n");
39.  
    for (int i = 0; i < sz_s; i )
40.  
    printf("%s %d ", s[i].name, s[i].num);
41.  
    bubble_sort(s, sz_s, sizeof(s[0]), cmp_by_name);
42.  
    printf("\n按字母名字排序后的结构体成员>\n");
43.  
    for (int i = 0; i < sz_s; i )
44.  
    printf("%s %d ", s[i].name, s[i].num);
45.  
     
46.  
    }
47.  
     
48.  
    //交换两个数据的函数
49.  
    void Swap(char* bu1, char* bu2, int sz)
50.  
    {
51.  
    int i = 0;
52.  
    for (i = 0; i < sz; i )
53.  
    {
54.  
    char tmp = *bu1;
55.  
    *bu1 = *bu2;
56.  
    *bu2 = tmp;
57.  
    bu1 ;
58.  
    bu2 ;
59.  
    }
60.  
    }
61.  
     
62.  
    //自定义int compare函数
63.  
    int cmp_int(const void* a, const void* b)
64.  
    {
65.  
    return (*(int*)a - *(int*)b);
66.  
    }
67.  
    int cmp_by_name(const void* a, const void* b)
68.  
    {
69.  
    return strcmp(((struct Stu*)a)->name, ((struct Stu*)b)->name);
70.  
    }
71.  
    int cmp_by_num(const void* a, const void* b)
72.  
    {
73.  
    return ((struct Stu*)a)->num - ((struct Stu*)b)->num;
74.  
    }
75.  
     
76.  
    //自定义sort函数
77.  
    void bubble_sort(
78.  
    void* base,//第一个元素地址
79.  
    int sz, //元素个数
80.  
    int size, //元素类型（大小）
81.  
    int(*cmp)(const void* a, const void* b)//自定义函数compare
82.  
    )
83.  
    {
84.  
    int i = 0;
85.  
    //进行排序的趟数
86.  
    for (i = 0; i < sz - 1; i )
87.  
    {
88.  
    int j = 0;
89.  
    for (j = 0; j < sz - 1 - i; j )
90.  
    {
91.  
    if (cmp((char*)base j * size, (char*)base (j 1) * size) > 0)
92.  
    {
93.  
    //条件满足则进行交换
94.  
    Swap((char*)base j * size, (char*)base (j 1) * size, size);
95.  
    }
96.  
    }
97.  
    }
98.  
    }

期待你的点赞加关注啦，第一篇博客收工！

oh yeah~

这篇好文章是转载于：学新通技术网