C语言之冒泡排序详解_c语言冒泡排序程序

1.冒泡排序的思想

冒泡排序的方法其实就是两两相邻元素进行比较，如果前面的元素大于(或小于)后面一个元素时就进行交换，直至所有元素都比较并完成交换，排序才结束。

由此我们可以这样来实现冒泡排序：

#include<stdio.h>
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;
			}
		}
	}
}

void Print_arr(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		//打印数组元素
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void test1()
{
	int arr[] = { 9,3,6,1,5,8,2,7,4 };
	int sz = sizeof(arr) / sizeof(arr[0]);

	printf("排序前:");
	Print_arr(arr, sz);

	Bubble_sort(arr, sz);

	printf("排序后:");
	Print_arr(arr, sz);
}

int main()
{
	test1();
	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

输出结果如图:

完成简单的冒泡排序后，我们不由得可以发现它的缺点，它只能对整型数组里的元素进行排序，而不能用来对其他类型的元素排序，所以我们可以尝试一下冒泡排序的进阶思想。

2.快速排序

在实现冒泡排序的进阶思想之前，我们需要了解一下快速排序：

快速排序，又称划分交换排序（partition-exchange sort）
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

而库函数就有一个关于快速排序的qsort函数，我们可以在cplusplus中搜索相关介绍：

该函数有四个参数：
(注意：size_t是unsigned int类型)

void qsort (void* base, //base指向待排序的第一个元素
 			size_t num, //待排序的元素个数
			size_t size,//待排序的数组元素的大小，单位是字节
            int (*compar)(const void*,const void*));
            //compar是一个函数指针，指向的函数能够比较2个元素
1
2
3
4
5

值得注意的是qsort的第四个参数，是一个函数指针，默认是升序排序，指向的函数对两个元素进行比较，存放的是函数的地址，而两个元素的类型均是const void*,const void*，采用void* 类型是为了可以赋予自定义任意的类型

compar函数的返回类型是int,返回值如下图所示：
第一个元素小于第二个元素返回<0,
第一个元素大于第二个元素返回>0,
第一个元素等于第二个元素返回=0

2.1整型排序

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 print_arr(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//qsort排序整型数组
void test2()
{
	int arr[] = { 3,1,5,7,2,4,8,6,0,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	print_arr(arr, sz);
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	print_arr(arr, sz);
}
int main()
{
	test2();
	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

运行结果：

2.2结构体类型排序

定义一个结构体存放学生名字和年龄，通过qsort函数对结构体进行排序：

#include<stdio.h>
#include <stdlib.h>
#include <string.h>
//qsort结构体排序
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);
}

void test3()
{
	struct Stu s[] = { {"zhnagsan",30},{"lisi",14},{"wangermazi",19} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
}

int main()
{
	test3();
	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

对名字进行排序，我们使用了一个专门用来对字符串进行比较的库函数strcmp，使用它需要调用头文件#include <string.h>，通过调试可以看出排序前后的结果：
排序前：

排序后：

3.冒泡排序实现任意类型的排序

在了解了qsort的用法后，可以通过冒泡排序和qsort相结合的方法实现对任意类型的排序。

比较函数tmp:
在实现之前，需要理解构建的第四个参数函数指针，将其强制类型转换为char * 类型，为什么是char * 类型，因为char类型刚好是一个字节，指向元素的首地址，而一个整形变量是4个字节，由于宽度(宽度的字节由元素类型决定)也是四个字节，(char * )base + j * width刚好跳过了j个整型，指向的也就是第j个元素，(char*)base + (j + 1) * width指向的也就是第 j+1个元素

tmp((char*)base + j * width, (char*)base + (j + 1) * width

交换函数Swap:

void Swap(char* ele1, char* ele2, size_t width)

地址在内存中存放是反着存放的(如下图)，首地址就是这个元素的值，所以定义一个char类型的变量，接收两个元素的首地址并依次进行交换，交换完自增，交换的宽度就是元素的字节。

for (i = 0; i < width; i++) //遍历每一个字节
{
char tmp = *ele1;
*ele1 = *ele2;
*ele2 = tmp;
ele1++;
ele2++;
}

假设这是程序员A写的，如同已经写在库函数里的qsort功能一样，构建一个方便别人调用的函数实现排序：

void Swap(char* ele1, char* ele2, size_t width)
{
	int i = 0;
	for (i = 0; i < width; i++) //遍历每一个字节
	{
		char tmp = *ele1;
		*ele1 = *ele2;
		*ele2 = tmp;
		ele1++;
		ele2++;
	}
}

void bubble_sort(void* base, size_t sz, size_t width, int (*tmp)(const void* e1, const void* e2))
{
	//排序趟数
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		//一趟排序
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (tmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
				//交换
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}
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

构建完排序函数，程序员B可以直接调用来排序了：

void print_arr(int arr[],int sz)
{
    int i = 0;
    for (i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

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

void use()
{
	int arr[] = { 3,1,5,2,4,8,7,6,9,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);//冒泡排序
	print_arr(arr, sz);
}
int main()
{
	use();
	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

运行程序：