Java数据结构及算法实例:冒泡排序 Bubble Sort

时间:2022-08-22 13:59:50
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 冒泡排序估计是每本算法书籍都会提到的排序方法。
 * 它的基本思路是对长度为N的序列,用N趟来将其排成有序序列。
 * 第1趟将最大的元素排在序列尾部,第2趟将第2大的元素排在倒数第二的位置,
 * 即每次把未排好的最大元素冒泡到序列最后端。
 * 该排序方法实际上分为两重循环,外层循环:待排元素从数组的第1个元素开始。
 * 内层循环:待排元素从数组的第1个元素开始,直到数组尾端未排过的元素。
 * 在内循环中,如果遇到前面元素比其后的元素大就交换这两个元素的位置。
 * 由此可见冒泡排序的复杂度是O(n^2)
 */
package al;
public class BubbleSort {
  /*
   * 冒泡排序 Java语言编写,可以直接运行 输入:n个数<a1,a2,,an>
   * 输出:输入序列的一个排列<a1',a2',,an'>,其中a1'<=a2'<=<=an' 待排的数也称为key 复杂度:O(n^2) 输出结果:9
   * 10 14 14 21 43 50 77 例子:高矮个站队
   */
  public static void main(String[] args) {
    BubbleSort bubbleSort = new BubbleSort();
    int[] elements = { 14, 77, 21, 9, 10, 50, 43, 14 };
    // sort the array
    bubbleSort.sort(elements);
    // print the sorted array
    for (int i = 0; i < elements.length; i++) {
      System.out.print(elements[i]);
      System.out.print(" ");
    }
  }
  /**
   * @author
   * @param array
   *      待排数组
   * @return void
   */
  public void sort(int[] array) {
    int i, j;
    int tmp;
    for (i = 0; i <= (array.length - 1); i++) { // outer loop
      for (j = 0; j < (array.length - 1 - i); j++) { // inner loop
        if (array[j] > array[j + 1]) {
          tmp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = tmp;
        }
      }
    }
  }
}