时间复杂度 O(N)

冒泡排序的时间复杂度不会随着样本的改变而改变

流程说明

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html 此网站以动图的形式非常清楚的展示了冒泡排序的过程 [3, 5, 2, 7, 6] idx 0 1 2 3 4 第一次: 0…N-1的位置上 [0]和 [1]对比大的往后交换，[1]和[2]对比大的往后交换 一共进行n-1 次 第一次: 0…N-2的位置上 [0]和 [1]对比大的往后交换，[1]和[2]对比大的往后交换 一共进行n-2 次 第一次: 0…N-3的位置上 [0]和 [1]对比大的往后交换，[1]和[2]对比大的往后交换 一共进行n-3 次 如此一直循环直到0…1位置，即n-m=0就停止了

代码示例

  1. package com.ss;
  3. import java.util.Arrays;
  4. import java.util.Random;
  6. /**
  7.  * <p>
  8.  * 冒泡排序
  9.  * </P>
  10.  *
  11.  * @author: zhangss
  12.  * @since: 2021-01-04
  13.  **/
  14. public class BubbleSort {
  15.     /**
  16.      * 冒泡排序
  17.      * @param arr
  18.      */
  19.     public static void bubbleSort(int[] arr){
  21.         for (int i = arr.length - 1; i > 0; i--) {
  22.             for (int j = 0; j <= i - 1; j++) {
  23.                 if (arr[j] > arr[j + 1]) {
  24.                     swap(arr, j, j + 1);
  25.                 }
  26.             }
  27.         }
  28.     }
  30.     /**
  31.      * 交换两个位置的值
  32.      * @param arr
  33.      * @param i
  34.      * @param j
  35.      */
  36.     public static void swap(int[] arr, int i, int j) {
  37.         int temp = arr[i];
  38.         arr[i] = arr[j];
  39.         arr[j] = temp;
  40.     }
  42.     /**
  43.      * 对数器
  44.      * 用来比较上述冒泡排序以后的顺序是否正确
  45.      * @param arr1
  46.      * @param arr2
  47.      * @return
  48.      */
  49.     public static boolean comparator(int[] arr1, int[] arr2){
  50.         if(arr1.length != arr2.length){
  51.             return false;
  52.         }
  53.         Arrays.sort(arr1);
  54.         for (int i = 0; i < arr1.length; i++) {
  55.             if(arr1[i] != arr2[i]){
  56.                 System.out.println(i + "..." + arr1[i]);
  57.                 System.out.println(i + "..." + arr2[i]);
  58.                 return false;
  59.             }
  60.         }
  61.         return true;
  62.     }
  64.     /**
  65.      * 产生数组用来测试冒泡排序方法
  66.      * @return
  67.      */
  68.     public static int[] getArr(){
  69.         Random random = new Random();
  71.         // 若电脑性能有限，生成的数组可以降低长度
  72.         int length = random.nextInt(1000);
  73.         int[] arr = new int[length];
  74.         for(int i = 0; i < length; i++){
  75.             arr[i] = random.nextInt();
  76.         }
  77.         return arr;
  78.     }
  80.     public static void main(String[] args) {
  82.         // 循环测试5万次后，确定刚才写的排序没问题
  83.         for (int i = 0; i < 50000; i++) {
  84.             int arr1[] = getArr();
  86.             int arr2[] =  Arrays.copyOf(arr1, arr1.length);
  87.             bubbleSort(arr2);
  88.             boolean comparator = comparator(arr1, arr2);
  89.             if(!comparator){
  90.                 System.out.println("排序失败");
  91.             }
  92.         }
  93.         System.out.println("排序成功");
  94.     }
  95. }