冒泡排序示范-从小到大 关键操作“自上而下前后比较”

冒泡分析：1.第i趟沉（存）第i大的数    2.  n个数比较n-1次

假设数组array有array.length个元素

第1趟：将最大（小）的元素沉下（即‘在数组最后的下标位置存下最大（小）值’）。之前沉下的元素为0个，剩下的比较的元素有array.length个，因此从上到下前后比较，让后数存较大（小）值，之后后数变前数再与它后面的数做比较，直到后数是最后一个数比较完毕后,这样下来数组最后的下标位置就存的是最大（小）值了，一共需要比较array.length-1次

....................

第i趟：将第i大（小）的元素沉下。之前沉下的元素为i-1个，此时要做的事是在数组倒数第i个位置存第i大（小）的元素，剩下的需要比较的元素有array.length-(i-1)个，因此此时从上到下前后比较array.length-(i-1)-1次，即比较array.length-i次

.....................

最后1趟：将倒数第二大（小）的元素沉下。之前沉下的元素为array.length-2个，此时要做的事是在正数第二个位置存倒数第二大的数，此时从上到下剩余两数没处理，前后比较，因此比较1次，结束。

结论：array.length个元素排序走array.length-1趟，第i趟比较array.length-i次

假设问题规模为n，即n个元素的排序问题。那么，

第1趟需要比较：n-1次

第2趟需要比较：n-2次

.......

第n-1趟需要比较:1次

总计：(n-1)+(n-2)+...+1=(n-1)(n-1+1)/2次，即时间复杂度O(n^2)，前后比较，交换数值需要一个额外空间O(1)。

我个人示例代码：

public class BubbleSort {

public static void bubbleSort(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 temp=array[j];

array[j]=array[j+1];

array[j+1]=temp;

}

}

public static void main(String[] args) {

int[] array= {6,5,3,2,4,8,9,1};// TODO Auto-generated method stub

System.out.println("排序前：");

for(int i=0;i<array.length;i++)

System.out.print(array[i]+" ");

System.out.println();

bubbleSort(array);

System.out.println("排序后:");

for(int i=0;i<array.length;i++)

System.out.print(array[i]+" ");

}

}

代码输出结果：

排序前：

6 5 3 2 4 8 9 1

排序后:

1 2 3 4 5 6 8 9