Classical algorithm (1) : bubble sort and its optimization

(reproduced) Original link: blog.csdn.net/weixin_4357…

Bubble sort

Bubble sort is used in ordinary learning. This blog has carried out a detailed code implementation of bubble sort algorithm, and has been optimized twice for reference and learning.

directory

What is bubble sort

Second, the idea of bubble sort algorithm

Three, code implementation

1. First optimization

2. Second optimization

What is bubble sort

Bubble sort is the most basic commutative sort. Bubbling sort is like water bubbling, with small (large) elements slowly rising to the top of the water through constant exchange from the bottom.

Second, the idea of bubble sort algorithm

We compare two adjacent numbers from the left in pairs, and when one element is larger than its neighbor on the right, we swap them, and vice versa. Bubble sort is a stable sorting algorithm.

Time complexity	Spatial complexity
O(n^2)	O(1)

Three, code implementation

public class BubbleSort1 {
    public static void main(String[] args) {
        System.out.println("Enter the values to be sorted, separated by commas :"); Scanner input = new Scanner(System.in); String str = input.nextLine(); // Set the string to","[] strArray = str.split(","); Int [] array = new int[strarray.length]; // Assign to the array loopfor (int i = 0; i < strArray.length; i++) {
            array[i] = Integer.parseInt(strArray[i]);
        }

        System.out.println("Array before sort:"+ Arrays.toString(array)); / / sort sort (array); System.out.println("Sorted array:"+ Arrays.toString(array)); } @param array */ private static void sort(int[] array) {// array.length - 1for (int i = 0; i < array.length - 1; i++) {
            System.out.println("The first" + (i + 1) + "Trip"); // array.length -i because each round can determine a number of sortedfor (int j = 0; j < array.length - 1 - i; j++) {
                int temp = 0;
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
                System.out.println("The first" + (j + 1) + "Time."+ Arrays.toString(array)); }}}}Copy the code

Algorithm execution results:

Enter the values to be sorted, separated by commas: 6,9,8,3,2,11,15,16,18,19: [6, 9,8,3,2,11,15,16, 16,18,19] [6, 8, 9, 3, 2, 11, 15, 16, 18, 19] The 3rd time: [6, 8, 3, 9, 2, 11, 15, 16, 18, 19] the 4th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] the 5th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] The 6th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] the 7th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] the 8th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] 1st run 2nd run 1st run [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] The 2nd time: [6, 3, 8, 2, 9, 11, 15, 16, 18, 19] the 3rd time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] the 4th time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] The 5th time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] the 6th time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] the 7th time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] 8th run: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] 3rd run 1st run: [3, 6, 2, 8, 9, 11, 15, 16, 18, 19] The 2nd time: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] the 3rd time: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] the 4th time: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] The 5th: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] the 6th: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] the 7th: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] 1st run: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] 2nd run: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 3rd time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 4th time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 5th time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] The 1st run of the 5th run: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] The 2nd time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 3rd time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 4th time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] The 2nd time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 3rd time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 4th time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] 7th run 1st run: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] 1st run of 8th run: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] 1st run 9th run 1st run: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] Sorted array: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19]Copy the code

As can be seen from the running results in the figure above, it is already ordered after the fifth sorting, but the algorithm is still sorted later, so the algorithm is optimized for the first time as follows.

1. First optimization

Add a flag (flag), each time the exchange occurs, the flag, if a loop is not marked, it indicates that the sorting has been completed, the array is in order, the remaining several sorts do not need to perform, you can end the sorting in advance.

public class BubbleSort2 {
    public static void main(String[] args) {
        System.out.println("Enter the values to be sorted, separated by commas :"); Scanner input = new Scanner(System.in); String str = input.nextLine(); // Set the string to","[] strArray = str.split(","); Int [] array = new int[strarray.length]; // Assign to the array loopfor (int i = 0; i < strArray.length; i++) {
            array[i] = Integer.parseInt(strArray[i]);
        }

        System.out.println("Array before sort:"+ Arrays.toString(array)); / / sort sort (array); System.out.println("Sorted array:"+ Arrays.toString(array)); Private static void sort(int[] array) {private static void sort(int[] array) {for (int i = 0; i < array.length - 1; i++) {
            System.out.println("The first" + (i + 1) + "Trip"); // Optimize bubble sort, add judgment bit, order mark, the initial of each round istrue
            boolean flag = true;
            for(int j = 0; j < array.length - 1 - i; Int temp = 0; int temp = 0; int temp = 0;if(array[j] > array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; // There are elements exchanged, so it is not ordered, the flag becomesfalse
                    flag = false;
                }
                System.out.println("The first" + (j + 1) + "Time."+ Arrays.toString(array)); } // Specify the upper inner layerforIn the loop, no elements are exchanged and the outer loop is brokenif (flag) {
                break; }}}}Copy the code

Algorithm execution results:

Enter the values to be sorted, separated by commas: 6,9,8,3,2,11,15,16,18,19: [6, 9,8,3,2,11,15,16, 16,18,19] [6, 8, 9, 3, 2, 11, 15, 16, 18, 19] The 3rd time: [6, 8, 3, 9, 2, 11, 15, 16, 18, 19] the 4th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] the 5th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] The 6th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] the 7th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] the 8th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] 1st run 2nd run 1st run [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] The 2nd time: [6, 3, 8, 2, 9, 11, 15, 16, 18, 19] the 3rd time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] the 4th time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] The 5th time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] the 6th time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] the 7th time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] 8th run: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] 3rd run 1st run: [3, 6, 2, 8, 9, 11, 15, 16, 18, 19] The 2nd time: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] the 3rd time: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] the 4th time: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] The 5th: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] the 6th: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] the 7th: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] 1st run: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] 2nd run: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 3rd time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 4th time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 5th time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] The 1st run of the 5th run: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] The 2nd time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 3rd time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] the 4th time: [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] [2, 3, 6, 8, 9, 11, 15, 16, 18, 19]Copy the code

From the result after the first optimization, it can be seen that in each sequence, many elements on the right are already ordered results, but the algorithm is still sorting the following values, so the second optimization is carried out.

2. Second optimization

The arrBoundary is defined as an unordered array boundary, so there is no need to do any sorting at this point.

public class BubbleSort3 {
    public static void main(String[] args) {
        System.out.println("Enter the values to be sorted, separated by commas :"); Scanner input = new Scanner(System.in); String str = input.nextLine(); // Set the string to[] strArray = str.split(","); Int [] array = new int[strarray.length]; // Assign for (int I = 0; i < strArray.length; i++) { array[i] = Integer.parseInt(strArray[i]); } system.out. println(" Array: "+ array.toString (array)); / / sort sort (array); System.out.println(" Array: "+ array.toString (array)); Private static void sort(int[] array) {private static void sort(int[] array) {private static void sort(int[] array) {private static void sort(int[] array) { // Last swap subscript int lastSwapIndex = 0; Int arrBoundary = array.length - 1; for (int i = 0; i < array.length - 1; I ++) {system.out.println (" "+ (I + 1) + "); Boolean flag = true; Boolean flag = true; for (int j = 0; j < arrBoundary; If (array[j] > array[j + 1]) {temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; // There is an element exchange, so it is not ordered, the flag changes to false flag = false; // lastSwapIndex = j; } system.out. println(" tH "+ (j + 1) +" : "+ array.toString (array)); } // Assign the position of the last swap element to the unordered array boundary. If (flag) {break; if (flag) {break; }}}}Copy the code

Algorithm execution results:

Enter the values to be sorted, separated by commas: 6,9,8,3,2,11,15,16,18,19: [6, 9,8,3,2,11,15,16, 16,18,19] [6, 8, 9, 3, 2, 11, 15, 16, 18, 19] The 3rd time: [6, 8, 3, 9, 2, 11, 15, 16, 18, 19] the 4th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] the 5th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] The 6th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] the 7th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] the 8th time: [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] 1st run 2nd run 1st run [6, 8, 3, 2, 9, 11, 15, 16, 18, 19] The 2nd time: [6, 3, 8, 2, 9, 11, 15, 16, 18, 19] the 3rd time: [6, 3, 2, 8, 9, 11, 15, 16, 18, 19] 1st run: [3, 6, 2, 8, 9, 11, 15, 16, 18, 19] 2nd run: [3, 2, 6, 8, 9, 11, 15, 16, 18, 19] [2, 3, 6, 8, 9, 11, 15, 16, 18, 19] [2, 3, 6, 8, 9, 11, 15, 16, 18, 19]Copy the code

Note: Bubble sort requires swapping the positions of two elements. Swapping two elements can be done with an Xor operation, which eliminates the need to create a third variable and reduces memory overhead.

We can change the way in which two elements are swapped during sorting as follows:

if (array[j] > array[j + 1]) {
                    array[j + 1] ^= array[j];
                    array[j] ^= array[j + 1];
                    array[j + 1] ^= array[j];
                }
Copy the code

Original link: blog.csdn.net/weixin_4357…

END

---