冒泡排序（Bubble Sort）的原理是什么？

本文共计2576个文字，预计阅读时间需要11分钟。

一、算法概述

1.1 算法分类

十种常见排序算法可以分为两大类：

1.比较类排序：通过比较元素之间的相对大小来确定它们的顺序。

2.非线性排序：不依赖于元素之间的比较，而是直接对元素进行操作。

比较类排序：

- 通过比较来确定元素间的相对顺序，时间复杂度通常不能突破O(nlogn)。- 非线性排序： - 基于比较的排序：如快速排序、归并排序等。 - 非基于比较的排序：如计数排序、基数排序等。

一、算法概述

1.1 算法分类

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。

• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

1.2 算法复杂度

1.3 相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

二、冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2.1 算法描述

• 1、比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 3、针对所有的元素重复以上的步骤，除了最后一个；
• 4、重复步骤1~3，直到排序完成。

2.2 动图演示

2.3 排序过程

下面以数列{20,40,30,10,60,50}为例，演示它的冒泡排序过程(如下图)。

我们先分析第1趟排序

• 当i=5,j=0时，a[0]<a[1]。此时，不做任何处理！
• 当i=5,j=1时，a[1]>a[2]。此时，交换a[1]和a[2]的值；交换之后，a[1]=30，a[2]=40。
• 当i=5,j=2时，a[2]>a[3]。此时，交换a[2]和a[3]的值；交换之后，a[2]=10，a[3]=40。
• 当i=5,j=3时，a[3]<a[4]。此时，不做任何处理！
• 当i=5,j=4时，a[4]>a[5]。此时，交换a[4]和a[5]的值；交换之后，a[4]=50，a[3]=60。

于是，第1趟排序完之后，数列{20,40,30,10,60,50}变成了{20,30,10,40,50,60}。此时，数列末尾的值最大。

根据这种方法：

• 第2趟排序完之后，数列中a[5...6]是有序的。
• 第3趟排序完之后，数列中a[4...6]是有序的。
• 第4趟排序完之后，数列中a[3...6]是有序的。
• 第5趟排序完之后，数列中a[1...6]是有序的。

第5趟排序之后，整个数列也就是有序的了。

2.4 代码实现

2.4.1 冒泡排序——常规版

/** * @Author: huangyibo * @Date: 2022/2/19 22:37 * @Description: 冒泡排序 常规版 * 文字描述(以升序为例) * 1、依次比较数组中相邻两个元素大小，若 arr[j] > arr[j + 1], 则交换两个元素, * 两两都比较一遍则称为一轮冒泡，结果是让最大的元素排到最后 * 2、重复以上步骤, 直到整个数组有序 */ public class BubbleSort { public static <E extends Comparable<E>> void bubbleSort(E[] arr){ for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if(arr[j].compareTo(arr[j + 1]) > 0){ swap(arr, j,j + 1); } } } } /** * 交换数组元素 * @param arr * @param i * @param j * @param <E> */ private static <E> void swap(E[] arr, int i, int j) { E temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

2.4.2 冒泡排序——优化版1

• 用boolean变量isSwapped记录是否发生位置交换，没有发生元素交换，则证明数组有序，直接跳出循环。

/** * @Author: huangyibo * @Date: 2022/2/19 22:37 * @Description: 冒泡排序 优化版1 * 用boolean变量isSwapped记录是否发生位置交换， * 没有发生元素交换，则证明数组有序，直接跳出循环 * * 有利于有序数组排序，完全有序数组直接变为O(n) */ public class BubbleSort { public static <E extends Comparable<E>> void bubbleSort(E[] arr){ for (int i = 0; i < arr.length - 1; i++) { //是否发生了交换 boolean isSwapped = false; for (int j = 0; j < arr.length - 1 - i; j++) { if(arr[j].compareTo(arr[j + 1]) > 0){ swap(arr, j,j + 1); isSwapped = true; } } //没有发生元素交换，则证明数组有序 if(!isSwapped){ break; } } } /** * 交换数组元素 * @param arr * @param i * @param j * @param <E> */ private static <E> void swap(E[] arr, int i, int j) { E temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

2.4.3 冒泡排序——优化版2

• 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可。

/** * @Author: huangyibo * @Date: 2022/2/19 22:37 * @Description: 冒泡排序 优化版2 * 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数， * 如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可 * * 有利于有序数组排序，完全有序数组直接变为O(n) */ public class BubbleSort { public static <E extends Comparable<E>> void bubbleSort(E[] arr){ for (int i = 0; i < arr.length - 1; ) { //最后一次发生元素交换的索引位置 int lastSwappedIndex = 0; for (int j = 0; j < arr.length - 1 - i; j++) { if(arr[j].compareTo(arr[j + 1]) > 0){ swap(arr, j,j + 1); lastSwappedIndex = j + 1; } } //外层循环遍历赋值, // 如果是有序数组的话，i = arr.length - 1 则直接终止了外层循环 i = arr.length - 1 - lastSwappedIndex; } } /** * 交换数组元素 * @param arr * @param i * @param j * @param <E> */ private static <E> void swap(E[] arr, int i, int j) { E temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

2.4.4 冒泡排序——优化版3(外层for无限循环写法)

• 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可。

/** * @Author: huangyibo * @Date: 2022/2/19 22:37 * @Description: 冒泡排序 优化版3(外层for无限循环写法) * 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数， * 如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可 * * 有利于有序数组排序，完全有序数组直接变为O(n) */ public class BubbleSort { public static <E extends Comparable<E>> void bubbleSort(E[] arr){ //循环比较次数 int cycles = arr.length - 1; for ( ; ; ) { //最后一次发生元素交换的索引位置 int lastSwappedIndex = 0; for (int j = 0; j < cycles; j++) { if(arr[j].compareTo(arr[j + 1]) > 0){ swap(arr, j,j + 1); lastSwappedIndex = j; } } //最后一次元素交换位置的索引为下一轮循环的最大次数 cycles = lastSwappedIndex; //循环比较次数小于等于0，则证明数组有序 if(cycles <= 0){ break; } } } /** * 交换数组元素 * @param arr * @param i * @param j * @param <E> */ private static <E> void swap(E[] arr, int i, int j) { E temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

2.4.5 冒泡排序——优化版4(外层while循环写法)

• 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可。

/** * @Author: huangyibo * @Date: 2022/2/19 22:37 * @Description: 冒泡排序 优化版4(外层while循环写法) * 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数， * 如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可 * * 有利于有序数组排序，完全有序数组直接变为O(n) */ public class BubbleSort { public static <E extends Comparable<E>> void bubbleSort(E[] arr){ //循环比较次数 int cycles = arr.length - 1; while (cycles > 0){ //最后一次发生元素交换的索引位置 int lastSwappedIndex = 0; for (int j = 0; j < cycles; j++) { if(arr[j].compareTo(arr[j + 1]) > 0){ swap(arr, j,j + 1); lastSwappedIndex = j; } } //最后一次元素交换位置的索引为下一轮循环的最大次数 cycles = lastSwappedIndex; } } /** * 交换数组元素 * @param arr * @param i * @param j * @param <E> */ private static <E> void swap(E[] arr, int i, int j) { E temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

参考： www.cnblogs.com/onepixel/articles/7674659.html

www.cnblogs.com/skywang12345/p/3596232.html