你的位置:首页 > Java教程

[Java教程]排序—冒泡排序


        在面试的时候偶尔会被问到排序的算法,有时候也会被要求把排序算法写出来,可一直也没当回事。直到前天面试的时候被要求当场写出一个程序对给定的数组进行排序。当时本来想写一个冒泡排序算法,写到最后才发现写了一个不伦不类的排序程序,冒泡不冒泡、插入不插入,回来之后想着是需要好好研究一些这些排序算法了,于是就决定把这几种常用的排序算法总结一下。

    排序要求:把长度为n的数组a按照从小到大的顺序进行排序。

    冒泡排序思路:给定一个长度为n的数组a,循环n-1次,每次循环找出a[0]到a[n-i-1]中最大数的数,然后把该数放在a[n-1]的位置。

    如何找出a[0]到a[n-i-1]中的最大数?:循环一遍,比较a[i]和a[i+1]的大小,如a[i]<a[i+1],两数交换位置,然后继续判断a[i+1]和a[i+2]的大小,以此循环结束。

排序示例:       

原数组:                2、0、3、6、8、4、9、5、1、7、
第1次循环排序结果: 0、2、3、6、4、8、5、1、7、9、
第2次循环排序结果: 0、2、3、4、6、5、1、7、8、9、
第3次循环排序结果: 0、2、3、4、5、1、6、7、8、9、
第4次循环排序结果: 0、2、3、4、1、5、6、7、8、9、
第5次循环排序结果: 0、2、3、1、4、5、6、7、8、9、
第6次循环排序结果: 0、2、1、3、4、5、6、7、8、9、
第7次循环排序结果: 0、1、2、3、4、5、6、7、8、9、
第8次循环排序结果: 0、1、2、3、4、5、6、7、8、9、
第9次循环排序结果: 0、1、2、3、4、5、6、7、8、9、

 

public void myBubbleSort(int[] array) {    for (int i = 0; i < array.length-1; i++) {      for (int j = 0; j < array.length - i - 1; j++) {        if (array[j] > array[j + 1]) {          int num = array[j];          array[j] = array[j + 1];          array[j + 1] = num;        }      }    }  }

 

注意两次循环的范围:

     外循环次数: n-1次,固定不变的,即使在n-m(0<m<n)之前已经完成排序(注意排序示例中的7.8.9次循环),程序仍要循环n-m 到n-1。

     内循环次数: 根据外循环变化而变化,次数为  (n-i-1)+……+2++1