C语言|C语言实现冒泡排序的三种优化和qsort函数的解析与模拟实现算法|c语言

文章图片

文章目录

冒泡排序
- 普通版本
- 对外层循环进行优化
- 对内循环进行优化
- 双向冒泡排序
qsort函数
- 分析与使用
- 模拟实现qsort函数

冒泡排序当我们第一次提起冒泡排序的时候，我们总是要问什么是冒泡排序呢？
简单的说，就是重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
而这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
普通版本我们先对整数类型的数据进行排序，比如我们要排 5 6 1 3 4 2 7 8 这8个数字，令它们变成有序数组。
图片分析如下：

文章图片

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include void BubbleSort(int* p, int sz) { int i = 0, j = 0; for (int i = 0; i < sz - 1; i++) //比较的总趟数为元素个数减1 {//控制每一趟过程比较的个数 //每一趟结束后，下一趟比较的最后一个元素就是前面那一位 for (int j = 0; j < sz - 1 - i; j++) {//前面元素大于后面元素就交换 if (p[j] > p[j + 1]) {int tmp = p[j]; p[j] = p[j + 1]; p[j + 1] = tmp; } } } }void Print(int* p, int sz) //打印数组内的元素 { int i = 0; for (i = 0; i < sz; i++) {printf("%d ", p[i]); } printf("\n"); }int main() {//用两个数组来验证 int arr[] = { 5,6,1,3,4,2,7,8 }; int arr2[] = { 10,9,8,7,6,5,4,3,2,1 }; //求出数组内的元素个数为sz int sz = sizeof(arr) / sizeof(arr[0]); int sz2 = sizeof(arr2) / sizeof(arr2[0]); //排序数组arr BubbleSort(arr, sz); //普通的冒泡排序 Print(arr, sz); //打印函数 //排序数组arr2 BubbleSort(arr2, sz2); Print(arr, sz); return 0; }

程序执行结果如下：

文章图片

对外层循环进行优化大家请先看第三轮到最后一轮的排序：

文章图片

不知道大家发现一个问题没有，上面从第四趟开始就已经是有序的了，但是我们的程序还是要跑一次，我们可以从这个地方入手来优化。
思路如下：
我们可以设一个变量flag等于0，在每一趟过程中；如果程序验证到前面的数比后面的数大，说明数组还没有序，并且令变量flag置为1。如果在一趟过程中都没有数比后面的数更大了，变量flag不作任何修改仍然为0，说明数组已经有序。
最后我们在每一趟结束后判断变量flag是否为0；如果flag为1，说明数组还没有排序好，程序仍然继续下一趟排序；如果flag为0，说明数组已经排序好了，不进行下一趟排序，退出。从而达到减少趟数的效果。
代码如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include //对外循环进行优化1 void BubbleSort1(int* p, int sz) { int i = 0; int j = 0; for (i = 0; i < sz - 1; i++)// 控制趟数 {//变量flag一定要放在每一趟的开头，这样flag每一趟才会置为0 int flag = 0; for (j = 0; j < sz - 1 - i; j++)//控制每一趟比较的次数 {if (p[j] > p[j + 1]) {//发现前面的数比后面的数大，数组没有序 //把flag置为1 int tmp = p[j]; p[j] = p[j + 1]; p[j + 1] = tmp; flag = 1; } } // 在每一趟结束后判断flag是否改变 if (flag == 0) {//flag没有变，数组已经有序，退出排序即可 return; } } }void Print(int* p, int sz) { int i = 0; for (i = 0; i < sz; i++) {printf("%d ", p[i]); } printf("\n"); }int main() {//用两个数组来验证 int arr[] = { 5,6,1,3,4,2,7,8 }; int arr2[] = { 10,9,8,7,6,5,4,3,2,1 }; //求出数组内的元素个数为sz int sz = sizeof(arr) / sizeof(arr[0]); int sz2 = sizeof(arr2) / sizeof(arr2[0]); //排序数组arr BubbleSort1(arr, sz); //优化版本1的冒泡排序 Print(arr, sz); //打印函数 //排序数组arr2 BubbleSort1(arr2, sz2); Print(arr, sz); return 0; }

对内循环进行优化大家再来看看原来数组排序的过程：

文章图片

大家发现一个问题没有，那就是在排序过程中后面一小段本来已经是有序的了，不需要我们再进行排序，我们只需要排序到最后元素交换的地方就可以了。
思路如下：
我们设个变量max来记录，最后一次元素交换的下标，从而我们在下一趟的排序中，只需要排序到变量max的地方即可，并且加上上面分析的趟数优化即可。
代码如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include void BubbleSort2(int* p, int sz) { int i = 0, j = 0; int pos = sz - 1; //第一次排序的极限先给到最后一个元素 int max = 0; //来保存最后一次交换的下标 for (i = 0; i < sz - 1; i++) {int flag = 0; for (j = 0; j < pos; j++) {if (p[j] > p[j + 1]) {int tmp = p[j]; p[j] = p[j + 1]; p[j + 1] = tmp; flag = 1; //每一次交换都把下标保存到max中 max = j; //不能在这里直接把j赋值给pos， //这里不能确定是最后一次元素交换的下标 //要等到每一趟结束后才行 } } // 每一趟过后把保存的下标赋值给pos //这里也不能直接把j赋值给pos， //因为最后一次交换的下标j还会继续变化 pos = max; if (flag == 0) {//flag没有变，数组已经有序，退出排序即可 return; } } }void Print(int* p, int sz) { int i = 0; for (i = 0; i < sz; i++) {printf("%d ", p[i]); } printf("\n"); }int main() {//用两个数组来验证 int arr[] = { 5,6,1,3,4,2,7,8 }; int arr2[] = { 10,9,8,7,6,5,4,3,2,1 }; //求出数组内的元素个数为sz int sz = sizeof(arr) / sizeof(arr[0]); int sz2 = sizeof(arr2) / sizeof(arr2[0]); //排序数组arr BubbleSort2(arr, sz); //优化版本2的冒泡排序 Print(arr, sz); //打印函数 //排序数组arr2 BubbleSort2(arr2, sz2); Print(arr, sz); return 0; }

双向冒泡排序 【C语言|C语言实现冒泡排序的三种优化和qsort函数的解析与模拟实现】我们在排序的过程中有时候会碰到特殊的例子，比如排序：9 1 2 3 4 5 6 0 。最大数9在最左边，而最小数0却在最右变，如果还是按照上面的方法优化是节省不了多少步数的。我们还需要另外一种方法才行。
思路如下：
这时候我们会想如果把最大数9和最小数0调换位置不就可以了嘛，所以我们想到了既然数组可以从左向右遍历，那也可以从右往左遍历。从左向右把最大的数移到最右；从右往左把最小的数移到最左。我们设两个变量left和right，当left小于right排序才执行，不然就退出。然后再加上前面的两种优化退出方式。
图片分析如下：

文章图片

代码如下：

//最终版本优化 void BubbleSort3(int* p, int sz) { int left = 0; //左边起始下标为0 int right = sz - 1; //右边起始下标为最后一个元素 int max = 0; int min = 0; while (left < right) {int i = 0; int flag = 0; // 从左边到右边排序 for (i = left; i < right; i++) {if (p[i] > p[i + 1]) {int tmp = p[i]; p[i] = p[i + 1]; p[i + 1] = tmp; flag = 1; // 保存交换的下标 max = i; } } //把最后交换的下标赋值给right right = max; if (flag == 0) {return ; }// 从右边往左边排序 flag = 0; //要把flag重新置为0 for (i = right; i > left; i--) {if (p[i] < p[i - 1]) {int tmp = p[i]; p[i] = p[i - 1]; p[i - 1] = tmp; flag = 1; min = i; } } //把最后交换的下标赋值给right left = min; if (flag == 0) {return ; } } }

qsort函数大家发现没有，前面分析的冒泡排序只能对整数进行排序，当我们想对字符串或者字符类型排序时就实现不了，那么有什么方法来解决呢？
我们就得提起qsort函数了，它能够对任何类型进行排序，下面是它的用法与解析。
分析与使用

文章图片

值得注意的是最后一个参数是函数指针类型，它要我们写一个函数来实现比较两个元素，然后qsort函数会自动帮我们进行排序。
使用举例：

#define _CRT_SECURE_NO_WARNINGS 1 #include #include #include //比较整形类型大小的函数 int compar1(const void* a, const void* b) { if ((*(int*)a - *(int*)b) > 0) {return 1; } else if ((*(int*)a - *(int*)b) == 0) {return 0; } else {return -1; } //return ( *(int*)a - *(int*)b ); //这样有可能会产生溢出 }//比较字符类型大小的函数 int compar2(const void* a, const void* b) { if ((*(char*)a - *(char*)b) > 0) {return 1; } else if ((*(char*)a - *(char*)b) == 0) {return 0; } else {return -1; } }int main() { int arr[] = { 9,8,7,6,5,4,3,2,1 }; char arr2[] = "gfedcba"; int sz = sizeof(arr) / sizeof(arr[0]); int sz2 = strlen(arr2); //对整形类型进行排序 qsort(arr, sz, sizeof(arr[0]), compar1); //对字符类型进行排序 qsort(arr2, sz2, sizeof(arr2[0]), compar2); int i = 0; for (i = 0; i < sz; i++) {printf("%d ", arr[i]); } printf("\n"); printf("%s\n", arr2); return 0; }

程序执行结果如下：

文章图片

模拟实现qsort函数经过上面的举例使用我们大概了解qsort函数的特性，那么再结合我们前面所分析的冒泡排序，我们能不能使用冒泡排序来模拟实现qsort函数呢？

文章图片

分析如下：
我们实现这个函数有两个难点：第一是怎么找到我的下一位元素呢？因为数组的第一个元素指针是void* 类型的，从而加减的步伐大小就不能确定。
第二个难点，就算确定两个元素了，因为数组的第一个元素指针是void* 类型的，就不能进行解引用，从而就不能进行元素之间进行交换了。
那么有没有解决的办法呢？
我们再来看看qsort函数的四个参数，其中第三个参数比较有特点，要把数组中的元素大小传过去，这有什么用处呢？这个参数是实现qsort函数的关键。
我们知道在所有指针类型当中，char* 类型指针的步伐是最小的，每次加一就跳过一个字节，所以当我们知道元素的大小即宽度之后，我们把第一个元素指针是void* 强制转化为char* 类型，在循环体中用个变量j乘上宽度再加上第一个元素指针，这样可以随便找到数组中的任意元素。
而我们知道元素的宽度，在两个元素交换的时候我们可以一个字节一个字节的交换，交换的次数就是元素的宽度。这样两个难点就解决了。
代码实现如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include #include #include struct people { char name[10]; int age; char fun[10]; double grade; }; //比较整形类型大小的函数 int compar1(const void* a, const void* b) { if (((struct people*)a)->age - ((struct people*)b)->age > 0) {return 1; } else if (((struct people*)a)->age - ((struct people*)b)->age == 0) {return 0; } else {return -1; } } int compar3(const void* a, const void* b) { return strcmp(((struct people*)a)->name, ((struct people*)b)->name); }void Swap(char* str1, char* str2, int width) { //交换元素，一个字节一个字节进行交换 //交换的次数为宽度大小 while (width--) {char tmp = *(str1); *(str1) = *(str2); *(str2) = tmp; str1++; str2++; } }void my_qsort(void* base, int sz, int width, int compar(const void* a, const void* b)) { //冒泡排序的方式实现qsort int i = 0, j = 0; for (i = 0; i < sz - 1; i++) {int flag = 0; for (j = 0; j < sz - 1 - i; j++) {//把要比较的元素地址传给比较函数compar if (compar((char*)base + j * width, (char*)base + (j + 1) * width) > 0) {//交换元素 Swap((char*)base + j * width, (char*)base + (j + 1) * width,width); flag = 1; } } if (flag == 0) {return; } } }void Print(struct people* pc,int sz) { int i = 0; for (i = 0; i < sz; i++) {printf("%s ", pc[i].name); printf("%d ", pc[i].age); printf("%s ", pc[i].fun); printf("%f ", pc[i].grade); printf(""); } printf("\n\n"); }int main() { struct people arr[] = { { "zhangsan",22,"add",3.14},{ "lisi",18,"sub",6.67},{ "wangw",28,"ghe",8.84} }; int sz = sizeof(arr) / sizeof(arr[0]); //对字符串大小进行排序 printf("对字符串大小进行排序:\n"); my_qsort(arr, sz, sizeof(arr[0]), compar3); Print(arr, sz); // 对整形大小进行排序 printf("对整形大小进行排序:\n"); my_qsort(arr, sz, sizeof(arr[0]), compar1); Print(arr, sz); return 0; }

注意：qsort函数可以帮我们实现很多类型的排序，但是我们要自己写一个能比较两个元素大小的函数，并且把函数地址传给qsort。
程序执行结果：