冒泡排序-java实现

冒泡排序是一种常用的排序算法，它的核心部分是双重嵌套循环，因而冒泡排序的时间复杂度是O(N²)。其基本思想是：每次将相邻的两个元素进行比较，如果他们的顺序错误就把他们交换过来（这里顺序是我们预先设定的按从大到小或者按从小到大）。

例如，我们需要将一组数按照从大到小进行排序。既然是从大到小排序，即越小的越靠后。每次通过比较相邻的两个数，如果后面的数比前面的数大，则交换这两个数的位置。一直比较下去直到最后两个数比较完毕后，最小的数就在最后一个了，这样我们就确定了最小一个数的位置，说明“一趟”完成了，每一趟只能确定一个数的位置。由于整个过程非常类似气泡一步一步往上“冒”，因而得名“冒泡排序”算法。

总结扩展一下：如果有n个数进行排序，我们只需要确定n-1个数的位置，也就是要进行n-1趟操作。而“每一趟”都需要从第1位开始进行相邻两个数的比较，将较小的一个数放在后面，比较完后向后移动一位并继续比较下面两个相邻数的大小，如此重复下去，直到最后一个未确定位置的数。冒泡排序的优点显而易见是每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较小值，从而下一趟也就不需要再与该数进行比较。

下面用java代码实现一下冒泡排序：

package test;

public class test5 {
	public static void main(String[] args) {
		int a[] = {12,23,24,11,66,43,98,70,1,2};
		System.out.println("sort before:");
		printArray(a);
		System.out.println("after bubbleSort:");
		bubbleSort(a);
		printArray(a);
	}
	
	public static void bubbleSort(int[] a) {
		int temp = 0;
		int n = a.length;
		//外层循环控制排序趟数，n个数排序，只用进行n-1趟
		for(int i = 0; i < n-1; i++) {
			//内层循环控制每一趟排序多少次，从第1位开始比较直到最后一个尚未归位的数
			for(int j = 0; j < n-i-1; j++) {
				//比较大小并交换
				if (a[j] < a[j+1]) {
					temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
				}
			}
		}
	}
	
	public static void printArray(int[] numbers) {
        for (int i = 0 ; i < numbers.length ; i ++ ) {
        	System.out.print(numbers[i] + ",");
        }
        System.out.println("");
    }
}

排序结果：
sort before:
12,23,24,11,66,43,98,70,1,2,
after bubbleSort:
98,70,66,43,24,23,12,11,2,1,