This is the first day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Bubble sort

  1. Starting with the array header, compare adjacent elements. If the first is larger (smaller) than the second, swap them both
  2. Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end, so that the last element should be the largest (smallest) number
  3. Repeat steps 1 and 2 as many times as the length of the array until the sorting is complete

Code implementation

Implement sort for the following arrays: {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}

Dynamic graph demonstration

Code implementation

public class BubbleSort { public static final int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}; public static void main(String[] args) { print(ARRAY); System.out.println("============================================"); print(sort(ARRAY)); } public static int[] sort(int[] array) { if (array.length == 0) { return array; } for (int i = 0; i < array.length; For (int j = 0; int j = 0; int j = 0; j < array.length - 1 -i; If (array[j + 1] < array[j]) {int temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; } } } return array; } public static void print(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); }}Copy the code

Time complexity

For the above 12 data items, starting from the first element, comparisons are made for 11 times in the first trip, 10 times in the second trip, and so on until the last trip, which is:

11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 66 timesCopy the code

If there are n elements, the first comparison will be (n-1) times, the second comparison will be (n-2) times, and so on:

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n * (n-1)/2Copy the code

In the big O notation, the time complexity of the sorting method is O(n2), after removing the constant coefficients and low-order terms.

Algorithm stability

Assuming that there are multiple records with the same keywords in the record sequence to be sorted, if the relative order of these records remains unchanged after sorting, that is, in the original sequence, r[I]=r[j], and r[I] is before r[j], while in the sorted sequence, r[I] is still before r[j], then the sorting algorithm is said to be stable. Otherwise it is called unstable. — Baidu Encyclopedia

Array [j] = array[j] = array[j] = array[j] = array[j] = array[j]