使用 Java 的 DSA - 冒泡排序

概述

冒泡排序是一种简单的排序算法。此排序算法是基于比较的算法，其中比较每对相邻元素，如果元素顺序不正确，则交换元素。此算法不适用于大型数据集，因为其平均和最坏情况复杂度为 O(n²)，其中 n 为项目数。

伪代码

procedure bubbleSort( A : array of items )
   for i = 1 to length(A) - 1 inclusive do:
      swapped = false
      for j = 1 to length(A) - 1 inclusive do:
         /* 比较相邻元素 */   
         if A[i-1] > A[i] then
            /* 交换它们 */
            swap( A[i-1], A[i] )		 
            swapped = true
         end if
      end for
      /*如果没有交换数字，则意味着 
      数组现在已排序，打破循环。*/
      if(!swapped) then
         break	 
   end for
end procedure

演示程序

package com.tutorialspoint.simplesort;

import java.util.Arrays;

public class BubbleSortDemo {
    
   public static void main(String[] args){
      int[] sourceArray = {4,6,3,2,1,9,7};
      System.out.println("Input Array: " 
      + Arrays.toString(sourceArray));
      printline(50);
      System.out.println("Output Array: " 
      + Arrays.toString(bubbleSort(sourceArray)));
      printline(50);
   }    

   public static void printline(int count){
      for(int i=0;i <count-1;i++){
         System.out.print("=");
      }
      System.out.println("=");
   }

   public static int[] bubbleSort(int[] intArray){

      int temp;
      boolean swapped = false;       
      // 循环遍历所有数字
      for(int i=0; i < intArray.length-1; i++){ 
         swapped = false;
         // 循环遍历前面的数字
         for(int j=1; j < intArray.length-i; j++){
            System.out.println("     Items compared: [ " 
            + intArray[j-1] + ", " + intArray[j] +" ]" ); 
            // 检查下一个数字是否小于当前数字
            // 交换数字。
            //(将最高的数字向上冒泡)
            if(intArray[j-1] > intArray[j]){
               temp=intArray[j-1];
               intArray[j-1] = intArray[j];
               intArray[j] = temp;
               swapped = true;
            }           
         }
         // 如果没有交换数字，则意味着
         // 数组现在已排序，打破循环。
         if(!swapped){
            break;
         }
         System.out.println("Iteration "+(i+1) +"#: " 
                            + Arrays.toString(intArray));
         }            
      return intArray;
   }    
}

如果我们编译并运行上述程序，则会产生以下结果 −

Input Array: [4, 6, 3, 2, 1, 9, 7]
==================================================
     Items compared: [ 4, 6 ]
     Items compared: [ 6, 3 ]
     Items compared: [ 6, 2 ]
     Items compared: [ 6, 1 ]
     Items compared: [ 6, 9 ]
     Items compared: [ 9, 7 ]
Iteration 1#: [4, 3, 2, 1, 6, 7, 9]
     Items compared: [ 4, 3 ]
     Items compared: [ 4, 2 ]
     Items compared: [ 4, 1 ]
     Items compared: [ 4, 6 ]
     Items compared: [ 6, 7 ]
Iteration 2#: [3, 2, 1, 4, 6, 7, 9]
     Items compared: [ 3, 2 ]
     Items compared: [ 3, 1 ]
     Items compared: [ 3, 4 ]
     Items compared: [ 4, 6 ]
Iteration 3#: [2, 1, 3, 4, 6, 7, 9]
     Items compared: [ 2, 1 ]
     Items compared: [ 2, 3 ]
     Items compared: [ 3, 4 ]
Iteration 4#: [1, 2, 3, 4, 6, 7, 9]
     Items compared: [ 1, 2 ]
     Items compared: [ 2, 3 ]
Output Array: [1, 2, 3, 4, 6, 7, 9]
==================================================