冒泡与 qsort 排序策略集

今天我们要学习两种排序方法，分别是冒泡排序和qsort函数排序,冒泡排序相对qsort函数排序要简单一点，更易于理解。

1.冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复遍历元素列并比较相邻元素来实现排序。这个算法的名字来源于较小的元素会像气泡一样逐渐“浮”到数列的顶端。冒泡排序是一种稳定的排序算法，即它保持相等元素的初始顺序。

核心思想就是：两两相邻的元素进行比较。

 算法动画链接：
318217b5c82cf71a7313612a3b46fe62.gif (826×257)https://i-blog.csdnimg.cn/blog_migrate/318217b5c82cf71a7313612a3b46fe62.gif

void Bubble_sort(int* arr, int sz)//实现冒泡排序
{
	for (int i = 0; i < sz - 1; i++)//实现第一次循环，该数组一共有十个数，除去最后一个数以外，每个数都要与其他数进行比较，一共循环九次
	{
		for (int j = 0; j < sz - i - 1; j++)//实现第二次循环，实现前后相邻两两比较，第一个数需要与其他九个数比较，第二个就只需要比较八个数，依次递减
		{
			if (arr[j] > arr[j + 1])//如果前一个数大于后一个数，需要进行交换
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

int main()
{
	int arr[10] = { 23,45,43,56,232,567,21,12,198,88 };
	int sz = sizeof(arr) / sizeof(arr[0]);//求解arr数组内有多少个元素
	Bubble_sort(arr, sz);//
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

上述是一个简单的冒泡排序算法，他的时间复杂度是比较高的，我们可以对其做一定的优化：
 

void Bubble_sort(int* arr, int sz)
{
	int flag;//设置一个变量，判断数组是否有序
	for (int i = 0; i < sz - 1; i++)
	{
		flag = 1;//flag为1代表有序
		for (int j = 0; j < sz - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				flag = 0;//flag为0，代表无序，如果一个数排完还没有进行交换，flag没有置0，说明数组已经有序，后面的数无需再排
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		if (flag == 1)//有序退出循环
			break;
	}
}

int main()
{
	int arr[10] = { 23,45,43,56,232,567,21,12,198,88 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Bubble_sort(arr, sz);//
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

冒泡排序并非只能进行整型数组的排序，他还能进行浮点数，字符串甚至结构体的排序，我们在这里就不一一介绍了，它们的思想都是相同的，区别只是比大小和交换的区别，大家有兴趣可以了解一番。 

 2.qsort函数排序

 qsort函数要比冒泡函数复杂很多，我们将举更多示例来学习。

有关qsort详细信息的链接：

qsort - C++ Referencehttps://legacy.cplusplus.com/reference/cstdlib/qsort/?kw=qsort

qsort 函数是 C 标准库 <stdlib.h> 中提供的一个通用排序函数，它可以对任意类型的数组进行排序。

首先我们来看这个函数原型：

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

qsort函数参数有四个 ，分别为：

• base：指向要排序的数组的第一个元素的指针。由于使用 void* 类型，它可以接受任意类型的数组。
• nmemb：数组中元素的个数。
• size：每个元素的大小（以字节为单位）。
• compar：一个指向比较函数的指针，用于定义元素之间的比较规则。该比较函数接受两个 const void* 类型的参数，返回一个整数值表示两个元素的大小关系。它的函数原型为：

int compar(const void *a, const void *b);

int compare(const void* p1,const void* p2)
{
	return *((int*)p1) - *((int*)p2);
}

int main()
{
	int arr[10] = { 23,45,43,56,232,567,21,12,198,88 };
	size_t sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), compare);

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

上面的示例比较简单，我们要想学好qsort函数，还得多加练习，我们用qsort排序结构体试一下。

在排序结构体之前，我们先来学习另一个函数，strcmp，它是专门用来比较两个字符串大小的函数，它是怎么比较的呢？

有关strcmp详细详细信息的链接：

strcmp - C++ Referencehttps://legacy.cplusplus.com/reference/cstring/strcmp/?kw=strcmp

strcmp 函数是 C 语言标准库 <string.h> 中用于比较两个字符串的函数

strcmp 函数的主要作用是按照字典序（ASCII 码顺序）比较两个字符串，根据比较结果返回不同的值，从而帮助开发者判断两个字符串的大小关系。

函数原型：

int strcmp(const char *s1, const char *s2);

参数：

s1：指向要比较的第一个字符串的指针。

s2：指向要比较的第二个字符串的指针。

返回值：

返回值小于 0：表示 s1 所指向的字符串在字典序上小于 s2 所指向的字符串。也就是说，s1 字符串中第一个不同字符的 ASCII 码值小于 s2 中对应位置字符的 ASCII 码值，或者 s1 是 s2 的前缀。

返回值等于 0：表示 s1 所指向的字符串和 s2 所指向的字符串完全相同。

返回值大于 0：表示 s1 所指向的字符串在字典序上大于 s2 所指向的字符串。即 s1 字符串中第一个不同字符的 ASCII 码值大于 s2 中对应位置字符的 ASCII 码值，或者 s2 是 s1 的前缀。

struct Student {
	char name[10];
	int age;
};

int compare_name(const void* p1, const void* p2)
{
	return strcmp(((struct Student*)p1)->name,((struct Student*)p2)->name);
}

int compare_age(const void* p1, const void* p2)
{
	return ((struct Student*)p1)->age - ((struct Student*)p2)->age;
}

int main()
{
	struct Student stu[4] = { {"lisa",18},{"peter",20},{"kate",15},{"jane",25} };
	size_t sz = sizeof(stu) / sizeof(stu[0]);
	//qsort(stu, sz, sizeof(stu[0]), compare_name);//按照name排序
	qsort(stu, sz, sizeof(stu[0]), compare_age);//按照age排序


	for (int i = 0; i < sz; i++)
	{
		printf("%s ", stu[i].name);
	}

	printf("\n");

	for (int i = 0; i < sz; i++)
	{
		printf("%d ", stu[i].age);
	}
	return 0;
}

 3.用冒泡排序模拟qsort函数功能的实现

int compare(const void* p1, const void* p2)
{
	return (*(int*)p1 - *(int*)p2);//将p1,p2转换为整型指针，解引用后读取四个字节，就是原来数组的值
}

void Swap(void* p1, void* p2, size_t size)
{
	for (int i = 0; i < size; i++)//逐一交换每一个字节的内容，循环四次，交换整型变量
	{
		char temp = *((char*)p1+i);
		*((char*)p1 + i) = *((char*)p2 + i);
		*((char*)p2 + i) = temp;
	}
}

void Bubble(void* arr, size_t sz, size_t size, int (*compare)(const void*, const void*))
{
	for (int i = 0; i < sz - 1; i++)
	{
		for (int j = 0; j < sz - i - 1; j++)
		{
			if (compare((char*)arr + j * size, (char*)arr + (j + 1) * size) > 0)//调用比较函数
			{
				Swap((char*)arr + j * size, (char*)arr + (j + 1) * size, size);
			}
		}
	}
}

int main()
{
	int arr[10] = { 1,5,33,4,2,6,9,8,99,100 };
	size_t sz = sizeof(arr) / sizeof(arr[0]);
	Bubble(arr, sz, sizeof(arr[0]), compare);//模仿qsort函数

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