Algorithm - Bubble Sort（Java）

悠悠 2022-05-24 07:20 141阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

package chimomo.learning.java.algorithm.sort;
 
 import java.util.Arrays;
 
 /**
 * @author Chimomo
 *
 * 
 * Basic Thought:
 *
 * Bubble Sort is a kind of simple sort algorithm in computer science.
 * It repeatedly visits the sequence to be sorted,
 * compare two elements each time,
 * swap them if their order is wrong,
 * until no elements need to be swapped.
 * The bigger element will rise to top by swapping like bubble,
 * so it names.
 * 
 *
 * 
 * Algorithm:
 *
 * The Bubble Sort algorithm is designed as following:
 * 1. Compare the two adjacent elements as a pair,
 * from the first pair to last pair,
 * swap the two if the first one is bigger than the second one.
 * Then, the last element must be the biggest,
 * remove the biggest one from unordered region.
 * 2. Repeat step1 on the elements in the unordered region
 * until no element pair need to be compared.
 * 
 *
 * 
 * Complexity:
 *
 * The time complexity of Bubble Sort is O(n^2).
 * 
 *
 * 
 * Stability:
 *
 * Bubble sort is swapping bigger element backward.
 * Comparing is comparing the adjacent two elements,
 * swapping also takes place in the adjacent two elements.
 * So, if the two adjacent elements equal,
 * you will not need swap them.
 * And if the two equal elements are not adjacent,
 * even though they are adjacent by swapping the front other elements,
 * you still will not need swap them.
 * The equal elements order are not changed in sorting,
 * so Bubble Sort is stable.
 * 
 */
 public class BubbleSort {
 
 /**
 * Bubble sort
 * @param a The array to be sorted
 */
 private static void bubbleSort(int[] a) {
 
 // The outer loop:
 // Limit the count of elements in each bubble sort comparison
 for (int i = a.length - 1; i >= 1; i--) {
 
 // The inner loop:
 // Comparing the elements whose subscript is from 0 to i-1
 for (int j = 0; j <= i - 1; j++) {
 
 // The sorting process
 if (a[j] > a[j + 1]) {
 int t = a[j];
 a[j] = a[j + 1];
 a[j + 1] = t;
 }
 }
 
 // Print each round of sorting
 System.out.println(Arrays.toString(a));
 }
 }
 
 /**
 * Test program
 *
 * @param args The arguments
 */
 public static void main(String[] args) {
 int[] arr = {11, 16, 22, -3, 99, 0, 16, 6, -1, 99};
 
 System.out.println("Before bubble sort:");
 System.out.println(Arrays.toString(arr));
 
 System.out.println("In bubble sort:");
 BubbleSort.bubbleSort(arr);
 
 System.out.println("After bubble sort:");
 System.out.println(Arrays.toString(arr));
 }
 
 }
 
 /* ------ Running Results ------
 Before bubble sort:
 [11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
 In bubble sort:
 [11, 16, -3, 22, 0, 16, 6, -1, 99, 99]
 [11, -3, 16, 0, 16, 6, -1, 22, 99, 99]
 [-3, 11, 0, 16, 6, -1, 16, 22, 99, 99]
 [-3, 0, 11, 6, -1, 16, 16, 22, 99, 99]
 [-3, 0, 6, -1, 11, 16, 16, 22, 99, 99]
 [-3, 0, -1, 6, 11, 16, 16, 22, 99, 99]
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 After bubble sort:
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 
 */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter