排序算法 -- 冒泡排序

冒泡排序

将需要排序的列表，从第一位开始，每相临两个元素比较，如果某一位大于（或小于）他的下一位，则交换两个元素位置，直至不能交换。

 

这种排序的平均时间复杂度是平方级的，效率不高，容易实现。

/**
 * BubbleSort.java
 * 
 * @author   xieyan
 * @date     2013/06/20
 * @version  1.0
 */
package sort;


/**
 * BubbleSort.java
 */
public class BubbleSort {

	/*
	 * 冒泡排序：
	 * 将需要排序的列表，从第一位开始，每相临两个元素比较，如果某一位大于（或小于）他的下一位，则交换两个元素位置。
	 * 直至不能交换。
	 * 
	 * 这种排序的平均时间复杂度是平方级的，效率不高，容易实现
	 */

	/**
	 * bubbleSortAsc
	 * 
	 * <PRE>
	 * 升序
	 * </PRE>
	 * 
	 * @param arr
	 */
	public static int[] bubbleSortAsc(int[] arr) {
		if(arr == null) {
			return null;
		}

		int temp = 0;
		for (int i = arr.length - 1; i > -1; i--) {
			for(int j = 0; j < i; j++) {
				if(arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
		return arr;
	}

	/**
	 * bubbleSortDesc
	 * 
	 * <PRE>
	 * 降序
	 * </PRE>
	 * 
	 * @param arr
	 */
	public static int[] bubbleSortDesc(int[] arr) {
		if(arr == null) {
			return null;
		}

		int temp = 0;
		for (int i = arr.length - 1; i > -1; i--) {
			for(int j = 0; j < i; j++) {
				if(arr[j] < arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
		return arr;
	}

	public static void main(String[] args) {
		int[] a = new int[] { 5, 7, 8, 3, 4, 2, 9, 1, 6 };

		int[] b = bubbleSortAsc(a);
		for (int i = 0; i < b.length; i++) {
			System.out.println(b[i]);
		}

		b = bubbleSortDesc(a);
		for (int i = 0; i <  b.length; i++) {
			System.out.println(b[i]);
		}
	}
}