原文地址

https://blog.csdn.net/ThinkWon/article/details/101534473
我在这个地址上进行整理和修改.

概述

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

算法描述

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

动图演示

依次循环,将大的往后移.橘色是排好序的内容.如果你数组里面有五个元素,那么就需要4趟循环排序.

1.冒泡排序（Bubble Sort） - 图1

代码实现

下面的排序算法统一使用的测试代码如下，源码GitHub链接

  1. public static void main(String[] args) {
  2.     int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
  3.     bubbleSort(array);
  5.     System.out.println(Arrays.toString(array));
  6. }
  1. public static void bubbleSort(int[] array) {
  2.     if (array == null || array.length <= 1) {
  3.         return;
  4.     }
  6.     int length = array.length;
  8.     // 外层循环控制比较轮数i
  9.     for (int i = 0; i < length; i++) {
  10.         // 内层循环控制每一轮比较次数，每进行一轮排序都会找出一个较大值
  11.         // (array.length - 1)防止索引越界，(array.length - 1 - i)减少比较次数
  12.         for (int j = 0; j < length - 1 - i; j++) {
  13.             // 前面的数大于后面的数就进行交换
  14.             if (array[j] > array[j + 1]) {
  15.                 int temp = array[j + 1];
  16.                 array[j + 1] = array[j];
  17.                 array[j] = temp;
  18.             }
  19.         }
  20.     }
  22. }

算法分析

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)