01冒泡排序.mp4

算法思路

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

image.png
image.png

  1. public class BubbleSort{
  2.     public static void main(String[] args){
  3.         int arr = [9,8,5,4,2,0];
  4.           bubbleSort(arr);
  5.         System.out.println(Arrays.toString(arr));
  6.     }
  8.     public static void bubbleSort(int[] arr)
  9.     {    //i表示趟数
  10.         for(int i=1;i<arr.length;i++){
  11.             //i=1 j=4
  12.             //i=2 j=3
  13.             //j=arr.length-i-1
  14.             for(int j=0;j<arr.length-i-1;j++){
  15.                 if(arr[j]>arr[j+1]){
  16.                     //交换位置
  17.                     int temp;
  18.                     temp = arr[j];
  19.                     arr[j] = arr[j+1];
  20.                     arr[j+1] = temp;
  21.                 }
  22.             }
  23.         }
  25.     }
  26. }

算法稳定性︰

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的;冒泡排序是稳定的排序算法。

时间复杂度∶

对于n位的数列则有比较次数为(n-1)+ (n-2)+… + 1 = n *(n - 1)/ 2，这就得到了最大的比较次数，n(n-1)/2 =(n2- n)/ 2，计算时间复杂度的时候，忽略常数项1/2,再忽略低阶项n，得到冒泡排序的时间复杂度为O(n2)