疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

冒泡排序算法 Java实现


 

   

  基本思想

  设数组长度为N。

  比较前后两个数据,如果前面的数据大于后面的数据,就将两个数据交换。

  这样对数组的第0个数据到N - 1个数据进行遍历后,最大的一个数据就沉到了数组的第N - 1个位置。

  N = N - 1,如果N不为0就重复前面两步,否则排序完成。

  第一种实现方法

  public void sort(int[] array) {

  int tmp;

  int n = array.length;

  for (int i = 0; i < n; i++) { // 进行n - 1次循环

  for (int j = 1; j < n - i; j++) {

  if (array[j - 1] > array[j]) {

  tmp = array[j - 1];

  array[j - 1] = array[j];

  array[j] = tmp;

  }

  }

  }

  }

  第二种实现方法

  对第一种方法进行优化,设置一个标识,如果这一次发生了交换,则为true,否则为false。明显如果下一次没有发生变化,说明排序已经完成。

  public void sort(int[] array) {

  int tmp;

  int n = array.length;

  boolean flag = true;

  while (flag) {

  flag = false;

  for (int j = 1; j < n; j++) {

  if (array[j - 1] > array[j]) {

  tmp = array[j - 1];

  array[j - 1] = array[j];

  array[j] = tmp;

  flag = true; // 关键点

  }

  }

  }

  }

  第三种实现方法

  再进一步优化。如果有100个数,只有前面10个无序,那么在第一次遍历后,最后发生交换的位置肯定小于10,且这个位置后的数据肯定是有序的,记录下这个位置,第二次只要从数组头遍历到这个位置就可以了。

  public void sort(int[] array) {

  int tmp;

  int flag = array.length;

  while (flag > 0) {

  int k = flag;

  flag = 0;

  for (int j = 1; j < k; j++) {

  if (array[j - 1] > array[j]) {

  tmp = array[j - 1];

  array[j - 1] = array[j];

  array[j] = tmp;

  flag = j; // 关键点

  }

  }

  }

  }