冒泡排序【详解】

本文主要是介绍冒泡排序【详解】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
本期介绍🍖
主要介绍：排序中的冒泡排序。

文章目录

1. 前言
2. 冒泡排序
3. 冒泡排序（外循环优化版）
4. 冒泡排序（内循环优化版）

1. 前言

相信只要接触过C语言的同学都或多或少了解排序问题，而最基本且最为人所熟知的应该冒泡排序。下面我会带着大家把排序方法走一遍，使你能够透彻的理解冒泡排序的原理，并且实现算法。

2. 冒泡排序

在这里插入图片描述

冒泡排序的核心思想：相邻的两个元素，两两进行比较。与选择排序不同的是，冒泡排序每一趟走下来，不仅可以得到一个最大（或最小）的元素，还能使得数列中较大的数下沉，较小的数冒起来。
如此数列必然在n-1趟之前就基本可以做到有序，可见冒泡排序的效率是高于选择排序的。抽象观察整个排序过程，你会发现数列中的元素就如同气泡一样，大的下沉小的冒起，所以这种排序才会被生动形象的称作冒泡排序，如上图所示。
在这里插入图片描述
如上图所示，冒泡排序每趟会排好一个元素，且使得这次数列中大数下沉小数冒起。排序中将执行n-1趟，每趟会比较n-1次。实现程序如下：

#include<stdio.h>void bubble_sort(int* arr, int num)
{int i = 0;//该循环决定趟数for (i = 0; i < num - 1; i++){int j = 0;//该循环决定每趟中元素比较的次数for (j = 0; j < num - 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 i = 0;int arr[] = { 6,7,5,3,4,1,8 };int sz = sizeof(arr) / sizeof(arr[0]);//计算数组元素的个数bubble_sort(arr, sz);//冒泡排序for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

在这里插入图片描述

3. 冒泡排序（外循环优化版）

如果逐语句的走一遍冒泡排序案例后，你必然会发现很多时候冒泡排序压根就不需要执行n-1趟，排序有时可能仅仅只需要执行一趟就可以使得整个序列有序，就如下图所示的案例：

在这里插入图片描述
那我们该怎么做才能使得排序时不用重复那么多趟呢？也就是说：若整个序列达到了有序但趟数还没有达到n-1趟时，剩下的趟数就被必要执行了。那程序上该怎么改进呢？答案：指需确定某一趟排序中一次都没有进行交换，那么就说明序列已经是有序的了，不需要再进行排序，直接退出循环就可。下面是代码：

#include<stdio.h>void bubble_sort(int* arr, int num)
{int i = 0;//该循环决定趟数for (i = 0; i < num - 1; i++){int flag = 1;int j = 0;//该循环决定每趟中元素比较的次数for (j = 0; j < num - 1 - i; j++){if (arr[j] > arr[j + 1]){//交换两元素int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = 0;}}//判断整个数组是否有序//若flag=1则表示数组已经有序，否则表示数组还是无序的；if (flag == 1)break;}
}int main()
{int i = 0;int arr[] = { 6,7,5,3,4,1,8 };int sz = sizeof(arr) / sizeof(arr[0]);//计算数组元素的个数bubble_sort(arr, sz);//冒泡排序for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

在这里插入图片描述

4. 冒泡排序（内循环优化版）

冒泡排序经过上面的优化后，其实还是存在着一些不必要的比较动作。因为按照现有的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 ……但实际上，数列真正的有序区可能会大于这个长度，比如下图所示的这个前半段无序后半段有序的例子。
在这里插入图片描述
如果还是按照上面的方法来排序，那每一趟都必然执行 n-1-i 次的比较，但其实用不到那么多次，因为后面的5、6、7、8已然有序还去比它干神马？这是毫无意义的事。那该如何避免这种情况呢？其实可以在每一趟排序中记录下最后一次元素交换的位置，那个位置也就是无序数列的边界（再往后就是有序区了），然后通过这个位置就避免无意义的比较了。但还是有同学会有质疑：你这举得例子不全面啊，前半段数列里全是要比后半段序列小的元素。如果把上图中的元素3改成9那还能实现该功能吗？当然可以，你可别捡了芝麻丢了西瓜，别死抓着这里数列后半段为有序的这个观点，而忘了冒泡排序的每一趟都可以把一个最大的元素放置到最后！！！

下面是代码：

#include<stdio.h>
#include<stdbool.h>void bubble_sort(int* arr, int num)
{int i = 0;//该循环决定趟数for (i = 0; i < num - 1; i++){bool flag = true;int j = 0;//无序数组的边界，每次比较只需比较到此为止int border = num - 1;//记录最后一次交换位置int position = 0;//该循环决定每趟中元素比较的次数for (j = 0; j < border; j++){if (arr[j] > arr[j + 1]){//交换两元素int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = false;//把无序数列的边界更新为最后一次交换元素的位置position = j;}}border = position;//最后的位置就是无序数组的边界//判断整个数组是否有序//若flag=true则表示数组已经有序，否则表示数组还是无序的；if (flag){break;}}
}int main()
{int i = 0;int arr[] = { 9,3,4,2,1,5,6,7,8 };int sz = sizeof(arr) / sizeof(arr[0]);//计算数组元素的个数bubble_sort(arr, sz);//冒泡排序for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}