冒泡排序(第1版)

首先要分清有序区和无序区

外层for控制有序区，内层for控制无序区

大数下沉，小数上升

temp不参与值大小比较，只是个中介而已，所以放哪里初始化都一样。

package chapter4.part1; import java.util.Arrays; import org.junit.Test; public class BubbleSort { @Test public void testBS1() { int[] array = new int[] {5, 8, 6, 3, 9, 2, 1, 7}; System.out.println("数组排序前： " + Arrays.toString(array)); int leng = array.length; for(int i=0; i<leng-1; i++) {//控制有序区的下标（也可以理解为轮数） for(int j=0; j<leng-i-1; j++) { int temp = 0;//temp放在哪里初始化都行，因为temp不参与值大小比较 if(array[j]>array[j+1]) { temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } System.out.println("数组排序后： " +Arrays.toString(array)); } }

测试用例：

小结：

因为冒泡排序中如果前后元素的值相等，那么它不会进行调换位置，所以属于稳定排序。

由于该排序算法的每一轮都要遍历所有的元素，总共遍历（元素数量-1）轮，

所以平均时间复杂度是O(n^2)。

参考思路：O(n*n+(n-1)*(n-1)+...+1*1)=O(n*n)=O(n^2)。