排序算法之冒泡排序(Bubble Sort)

排序算法之冒泡排序(Bubble Sort)

Scroll Down

基本思想

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

算法描述

1)比较相邻的元素。如果前一个比后一个大,就交换它们两个;
2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
3)针对所有的元素重复以上的步骤,除了最后一个;
4)重复步骤1~3,直到排序完成。为了优化算法,可以设立一个布尔标识,每趟排序开始前设为false,如果该趟排序发生了交换就置为true,如果一趟排序结束标识仍为false表示该趟排序没有发生交换,即数组已经有序,可以提前结束排序。

动图演示

2510824-641d29be81792220

代码实现

public static int[] bubbleSort(int[] array){
   if(array.length == 0){
      return array;
   }
   //外层循环一次为一趟排序
   for(int i=0;i<array.length;i++){
      boolean isSwap = false;
      //内层循环一次为一次相邻比较
      for(int j=0;j<array.length-1-i;j++){
         if(array[j+1]<array[j]){
             int temp = array[j+1];
             array[j+1] = array[j];
             array[j] = temp;
             isSwap = true;
         }
         if(!isSwap){
           break;
         }
      }
      return array;
   }
}

时间复杂度

冒泡排序平均时间复杂度为O(n^2),
最好时间复杂度为O(n)
最坏时间复杂度O(n^2)

空间复杂度

冒泡排序使用了常数空间,空间复杂度为O(1)

稳定性

array[j]==array[j+1]的时候,我们不交换array[i]和array[j],所以冒泡排序是稳定的

作者:Steven1997
链接:https://www.jianshu.com/p/47170b1ced23
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。