冒泡排序

冒泡排序

基本思想

冒泡排序（bubble sort）, 基本思想是两两比较相邻的记录，如果顺序不对则进行交换。

代码实现

时间复杂度O(\(n^2\))

可以从低的index两两交换，将大的元素挪到数组尾部(如上图所示)。

也可以从高的index两两交换，每次将第n小的提升到数组前端。

for (int i = 0; i< length; i++) {
  int j = length - 1;
  for (; j > i ; j --) {
    if (arrays[j] < arrays[j -1 ]) {
      swap(arrays, j, j-1);
    }
  }
}

优化

如果是一个基本有序的数组，可能几次冒泡后就已经完成排序，可提前退出。

public static void sort(int[] arrays) {
  int length = arrays.length;
  boolean sorted = true;
  for (int i = 0; i< length; i++) {
    int j = length - 1;
    for (; j > i ; j --) {
      if (arrays[j] < arrays[j -1 ]) {
        swap(arrays, j, j-1);
        sorted = false;  // 如果发生交换，说明数组还没有完成最终排序
      }
    }
    if(sorted) {
      break;
    }
  }
}