C语言-冒泡排序函数_冒泡函数

冒泡排序函数

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

#include <stdio.h>
void bubble_sort(int arr[], int sz)//int *arr
{
    int i = 0; // 确定冒泡排序的趟数
    // int sz = sizeof(arr) / sizeof(arr[0]); //这样对吗？ 不对
    for (i = 0; i < sz - 1; i++)
    {
        int flag = 1; //假设这一趟要排序的数据已经有序
        //每一趟冒泡排序
        int j = 0;
        for (j = 0; j < sz - i - 1; 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;// if不能break,这个break是跳出外层循环
        }
    }
}
int main()
{
    int arr[] = {3, 1, 7, 5, 8, 9, 0, 2, 4, 6}; //对arr进行排序，排成升序
    int sz = sizeof(arr) / sizeof(arr[0]);
    // bubble_sort(arr);                           //是否可以正常排序？
    // arr是数组，我们对数组arr进行传参，实际上传递过去的是数组arr首元素的地址 &arr[0]
    bubble_sort(arr,sz); // 冒泡排序函数
    int i = 0;
    for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

问题：只能排序整形数组

完善

void* 类型的指针 可以接受任意类型的地址
void* 类型的指针 不能进行解引用操作
void* 类型的指针 不能进行±整数的操作

qsort函数

qsort函数实现冒泡排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp_int(const void *e1, const void *e2)
{
    //比较两个整形值的
    return *(int *)e1 - *(int *)e2;
}

void test1()
{
    int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    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]);
    }
}

//比较浮点型
int cmp_float(const void *e1, const void *e2)
{
    /*if (*(float*)e1 == *(float*)e2)
		return 0;
	else if (*(float*)e1 > *(float*)e2)
		return 1;
	else
		return -1;*/

    return ((int)(*(float *)e1 - *(float *)e2));
}

void test2()
{
    float f[] = {9.0, 8.0, 7.0, 6.0, 5.0, 4.0};
    int sz = sizeof(f) / sizeof(f[0]);
    qsort(f, sz, sizeof(f[0]), cmp_float);
    int j = 0;
    for (j = 0; j < sz; j++)
    {
        printf("%f ", f[j]);
    }
}

//比较结构体类型
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)
{
    //比较名字就是比较字符串
    //字符串比较不能直接用><=来比较，应该用strcmp函数<string.h>
    return strcmp(((struct Stu *)e1)->name, ((struct Stu *)e2)->name);
}

void test3()
{
    struct Stu s[3] = {{"zhangsan", 20}, {"lisi", 30}, {"wangwu", 10}};
    int sz = sizeof(s) / sizeof(s[0]);
    qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
    //第一个参数：待排序数组的收元素地址
    //第二个参数：待排序数组的元素个数
    //第三个参数：待排序数组的每个元素的大小-单位是字节
    //第四个参数：是函数指针，比较两个元素的所用函数的地址-这个函数使用者自己实现
    //           函数指针的两个参数是：待比较的两个元素的地址
}

//实现bubble_sort函数的程序员，他是否知道未来排序的数据类型-不知道
//那程序员也不知道，待比较的两个元素的类型
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++;
    }
}

//因为首元素类型不同，v所以使用void指针
//sz要排序元素个数
//width每个元素的字节数
//两个元素比较的方法不一样，把比较函数的地址传进来,e1,e2要比较的元素
void bubble_sort(void *base, int sz, int width, int (*cmp)(void *e1, void *e2))
{
    int i = 0;
    //趟数
    for (i = 0; i < sz - 1; i++)
    {
        //每一趟比较的对数
        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);
            }
        }
    }
}

void test4()
{
    int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    int sz = sizeof(arr) / sizeof(arr[0]);
    //使用bubble_sort的程序员一定知道自己排序的是什么数据
    //就应该知道如何比较待排序数组中的元素
    bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
}

void test5()
{
    struct Stu s[3] = {{"zhangsan", 20}, {"lisi", 30}, {"wangwu", 10}};
    int sz = sizeof(s) / sizeof(s[0]);
    //bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_age);
    bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_name);
}

int main()
{

    //test1();
    //test2();
    //test3();
    //test4();
    test5();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143