Bubble Sort

冒泡排序实现思路

1. 将序列中所有元素两两比较，将最大的放在最后面。
2. 将剩余序列中所有元素两两比较，将最大的放在最后面。
3. 重复第二步，直到只剩下一个数。

代码实现

public static void bubbleSort(int[] arr) {
    int tmp;
    int length = arr.length;
    for (int i=0; i<length-1; i++) {
        for (int j=0; j<length - i -1; j++) {
            if (arr[j] > arr[j+1]) {
                tmp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

public void bubbleSort(int[] arr) {
  boolean swapped = true;
  int j = 0;
  int tmp;
  while (swapped) {
        swapped = false;
        j++;
        for (int i = 0; i < arr.length - j; i++) {                                       
              if (arr[i] > arr[i + 1]) {                          
                    tmp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = tmp;
                    swapped = true;
              }
        }                
  }
}

动画演示

复杂度分析

最好的情况下（完全正序）复杂度是 O(1)；最糟糕的情况下（完全倒序），复杂度是 O(n^2)

参阅文档

http://www.algolist.net/Algorithms/Sorting/Bubble_sort