Simple example analysis of bubble sort in Java

This article mainly introduces Java simple bubble sorting examples in detail, which has certain reference value. Interested friends can refer to it

1. Algorithm principle

Compare adjacent elements. If the first one is bigger than the second one, swap them both.

Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. At this point, the last element should be the largest number.

Repeat the above steps for all elements except the last one.

Continue to repeat the above steps for fewer and fewer elements each time until there are no pairs of numbers to compare.

2. Implementation ideas

Use a double loop to implement, with the outer loop variable set to i and the inner loop variable set to j. If there are n numbers that need to be sorted, the outer loop is repeated n-1 times, and the inner loop is repeated n-1, n-2,..., 1 time. The two elements compared each time are related to the inner loop j. They can be identified by a[j] and a[j+1] respectively. The values ​​of i are 1, 2,..., n-1. , for each i, the value of j is 0,1,2,...n-i.

Suppose the array length is N:

1． Compare the two adjacent data before and after. If the former data is greater than the latter data, the two data will be exchanged.
2. In this way, after traversing the 0th data to the N-1th data of the array, the largest data will "sink" to the N-1th position of the array.
3. N=N-1, if N is not 0, repeat the previous two steps, otherwise the sorting is completed.

3. Code implementation

##

package sort;
import java.util.Arrays;
/**
 * 冒泡排序
 * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 * 针对所有的元素重复以上的步骤，除了最后一个。
 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

4. Performance analysis

If recorded If the initial state of the sequence is "positive order", then the bubble sort process only needs to perform one sorting, and only needs to perform n-1 comparisons during the sorting process, without moving the records; conversely, if the initial state of the record sequence is " "Reverse order", you need to perform n (n-1)/2 comparisons and record moves. Therefore, the total time complexity of bubble sort is O(n*n).

5. Algorithm Optimization

The shortcomings of bubble sorting method and improvement methods:

First, during the sorting process, after executing the last After sorting, although the data has been sorted completely, the program cannot determine whether the sorting is completed. In order to solve this problem, a flag can be set and its initial value is set to true, indicating that the sorted table is an unordered table. table, set the flag value to true before each sorting starts, and change the flag to false during data exchange. At the beginning of a new round of sorting, check this flag. If this flag is false, it means that no data has been exchanged last time, and the sorting will end; otherwise, the sorting will be performed;

Second, in bubble sorting, There may be no data exchange in one scan, or there may be one or more data exchanges. In the traditional bubble sort algorithm and some improved algorithms in recent years, only the information about whether there is data exchange in one scan is recorded, and the data is Location information where the exchange occurs is not processed. In order to make full use of this information, local bubble sorting can be performed on each reverse-order data pair in a global scan, which is called local bubble sorting. Local bubble sort has the same time complexity as the bubble sort algorithm, and the number of comparisons and moves of the required keywords is exactly the same in both forward and reverse order. Since the number of data moves between local bubble sort and bubble sort is always the same, and the number of key comparisons required by local bubble sort is often less than that of bubble sort, this means that local bubble sort is likely to have a lower average number of comparisons. Bubble sort has been improved on. When the advantage of fewer comparisons is not enough to offset the additional overhead caused by its program complexity, and when the amount of data is large, the time performance of local bubble sort is significantly better than that of bubble sort. Bubble sort. For N unordered data, when we perform a bubble sort, if the k-th data and the k+1-th data are in reverse order, then a forward bubble sort is performed on the k+1-th data, so that Move it to the appropriate position, that is to say, adjust the previous k+1 data to the positive sequence. Because this bubbling method only bubbles the first k+1 data, we call it - local bubbling

package sort;

import java.util.Arrays;

public class BubbleSort {
  public static void bubbleSort(int[] arr) {
    boolean flag=true;
    while (flag) {
      flag=false;
      int temp = 0;
      for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
          if (arr[j] > arr[j + 1]) {   //交换两数位置
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag=true;
          }
        }
        if (!flag){
          break;
        }
        }
      }
    }
  public static void main(String[] args){
    int a[]=new int[]{345,22,43,12,65,335,124,636,3};
    BubbleSort.bubbleSort(a);
    System.out.print(Arrays.toString(a));
  }
}

The above is the detailed content of Simple example analysis of bubble sort in Java. For more information, please follow other related articles on the PHP Chinese website!