【C语言】冒泡排序的快排模拟

说到排序，必然绕不开两个排序，冒泡排序与快速排序
冒泡排序是大多数人的启蒙排序，因为他的算法简单。但效率不高，便于新手理解；
而快速排序是集大成之作，效率最高，使用最为广泛。

今天这篇文章带来如何使用qsort（quick sort，快速排序），和如何使用冒泡排序的快速排序的模拟。
也会在不久后讲解几大排序的算法。

冒泡排序：

开始之前先来回顾一下冒泡排序的实现

冒泡排序的思想是让数组的元素从头开始两两比较，大的放在后边（根据情况定），解决完一个元素在进行下一个，如下图。

从上图中我们发现排序第一趟要进行5次（len-1次）
而一趟可以解决1个元素的位置（当剩最后一个元素时不用排序）
所以可以得到一共需要进行5趟（len-1趟）
故可以写一个外层for循环模拟趟数，循环变量为i，从0开始

第二次时就进行4次
每趟都会减少一个需要排序的元素，与外层循环变量i有关
故我们控制一趟次数的内循环可以根据i来写出适当的表达式

代码实现：

void bubble_sort(int arr[], int len)
{
	for (int i = 0; i < len-1; i++)
	{
		for (int j = 0; j < len - 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,0 };
	int len = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, len);
	for (int i = 0; i < len; 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

这样一个朴实无华的冒泡排序就完成了。
接下来研究qsort。

一一一一一一一一一分割线一一一一一一一一

qsort的参数设计：

登录网站cpulsplus.com,可以查询qsort函数信息

cpp网站链接

觉得难以理解不要紧，下边有详细的解释。

我们发现qsort有4个参数

void qsort (void* base, 
            size_t num, 
            size_t size,
            int (*compar)(const void*,const void*));
1
2
3
4

参数：

1.void*base：
大家看到这个肯定就懵了，啥是void*？
void*也是一种指针类型，不过他可以接收任意类型的数据；
什么？任意类型，这也就说明qsort不只可以排序整形，字符，甚至结构体都可以排序
base就是数组的数组名，因为知道数组在哪里才可以进行排序。

2.size_t num：
size_t是sizeof这个操作符的返回值类型，本质是unsigned类型。
num是指数组中元素个数的多少

3.size_t size：
排序有了数组名，有了个数就可以排序了吗？
想到冒泡排序好像就是这样，但是，别忘记qsort可以排序任意类型，这也就意味着我们不仅需要知道数组名与元素个数，还需要知道排序的是什么类型，也就是多少字节，size就是数组中每个元素的字节大小。

4.int (*compar)(const void*,const void*))
仔细看，发现他像什么？
没错是个函数指针，他的类型是int (*)(const void*,const void*))，为什么qsort需要传参一个函数指针，因为qsort需要知道两个数据间是如何比较，这取决于使用者的想法，比如结构体你想按照其中的字符串比较还是整形比较

这是比较函数的返回值：

当返回值小于0 ，p1指向元素被排在p2指向元素左边。即[*p1, *p2];

当返回值大于0 ，p1指向元素被排在p2指向元素右边。即[*p2, *p1];

当返回值等于0 ，p1指向元素和p2指向元素顺序不确定。

即e1指向的值大于e2指向的值，返回正数，否则返回负数，相等时返回0（默认升序）
知道了参数是什么，那我们应该怎样使用呢？
不要看着感觉复杂，其实很简单

#include 
//qosrt函数的使用者得实现一个比较函数
int int_cmp(const void * p1, const void * p2)
{
    return (*( int *)p1 - *(int *) p2);
    //因为我们比较的是int类型，所以需要将e1，e2强转后再解引用
    //void*类型是不可以解引用的
}
//注意比较函数的返回值
e1＞e2返回一个正数
int main()
{
    int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
    int i = 0;
    qsort(arr, 
          //数组名
          sizeof(arr) / sizeof(arr[0]), 
          //数组的元素个数
          sizeof (int),
          //每个元素类型
          int_cmp);
          //比较函数
    for (i = 0; i< sizeof(arr) / sizeof(arr[0]); i++)
    {
        printf( "%d ", arr[i]);
    }
    printf("\n");
    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

这就实现了如何使用qsort。

一一一一一一一一一分割线一一一一一一一一

冒泡排序的快排模拟：

那么如果我们将qsort中的参数放到冒泡排序中，该如何以qsort的方式实现冒泡排序呢？
我们发现，整体的逻辑不需要改动，需要改动的是两个元素的比较需要使用我们自己定义的cmp函数
那么请看代码，会在代码中解释大家的各种疑问
代码实现：

先来看函数的主体部分：，只是改写了参数

int main()
{
	int arr[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 ,0};
	int len = sizeof(arr) / sizeof(arr[0]);
	//参数改成qsort形式的参数
	bubble_sort(arr, len, sizeof(arr[0]), cmp);
	for (int i = 0; i < len; i++) 
	{
		printf("%d ", arr[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

然后看冒泡排序的实现：

//比较函数
int cmp(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}

void bubble_sort(void*base,int len,int width,int(*cmp)())
{
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - 1 - i; j++)
		{
		if (cmp((char*)base+width*j, (char*)base + width * (j+1))> 0)
//因为base是void*类型，需要强转成（char*），因为char*是最小的单位，
//容易操作，同时利用width和j得出当前元素与下一个元素的地址，
//在cmp中强转为int*进行比较
//当返回值为正数1说明e1指向的数大于e2指向的，需要交换
			{
				swap((char*)base + width * j, 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

交换函数：
共循环width次，因为width为字节大小，而我们是char*类型，只有1字节，我们通过for循环来交换

void swap(char* p,int width)
{
	for (int i = 0; i < width; i++)
	{
		char tmp = *(p+i);
		*(p+i) = *(p + i + width);
		*(p + i + width) = tmp;
	}
}
1
2
3
4
5
6
7
8
9

一一一一一一一一一分割线一一一一一一一一
整体代码：

int cmp(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}
void swap(char* p,int width)
{
	for (int i = 0; i < width; i++)
	{
		char tmp = *(p+i);
		*(p+i) = *(p + i + width);
		*(p + i + width) = tmp;
	}
}
void bubble_sort(void*base,int len,int width,int(*cmp)())
{
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - 1 - i; j++)
		{
			if (cmp((char*)base+width*j, (char*)base + width * (j+1)) > 0)
			{
				swap((char*)base + width * j, width);
			}
		}
	}
}

int main()
{
	int arr[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 ,0};
	int len = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, len, sizeof(arr[0]), cmp);
	for (int i = 0; i < len; 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

欢迎纠错与交流！