/** |
* 冒泡排序:执行完一次内for循环后,最小的一个数放到了数组的最前面。相邻位置之间交换 |
* |
* 两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。 |
* 设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡 |
* ,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上 |
* "漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。 |
*/ |
public class BubbleSort { |
/** |
* 排序算法的实现,对数组中指定的元素进行排序 |
* |
* @param array |
* 待排序的数组 |
* @param from |
* 从哪里开始排序 |
* @param end |
* 排到哪里 |
* @param c |
* 比较器 |
*/ |
public void bubble(Integer[] array, int from, int end) { |
// 需array.length - 1轮比较 |
for ( int k = 1 ; k < end - from + 1 ; k++) { |
// 每轮循环中从最后一个元素开始向前起泡,直到i=k止,即i等于轮次止 |
for ( int i = end - from; i >= k; i--) { |
// 按照一种规则(后面元素不能小于前面元素)排序 |
if ((array[i].compareTo(array[i - 1 ])) < 0 ) { |
// 如果后面元素小于了(当然是大于还是小于要看比较器实现了)前面的元素,则前后交换 |
swap(array, i, i - 1 ); |
} |
} |
} |
} |
/** |
* 交换数组中的两个元素的位置 |
* |
* @param array |
* 待交换的数组 |
* @param i |
* 第一个元素 |
* @param j |
* 第二个元素 |
*/ |
public void swap(Integer[] array, int i, int j) { |
if (i != j) { // 只有不是同一位置时才需交换 |
Integer tmp = array[i]; |
array[i] = array[j]; |
array[j] = tmp; |
} |
} |
/** |
* 测试 |
* |
* @param args |
*/ |
public static void main(String[] args) { |
Integer[] intgArr = { 7 , 2 , 4 , 3 , 12 , 1 , 9 , 6 , 8 , 5 , 11 , 10 , 53 , 28 , |
19 , - 4 , - 9 , - 1 , 0 , - 7 , 8 , 7 , 8 , 1 }; |
BubbleSort bubblesort = new BubbleSort(); |
bubblesort.bubble(intgArr, 0 , intgArr.length - 1 ); |
for (Integer intObj : intgArr) { |
System.out.print(intObj + " " ); |
} |
} |
} |