01-冒泡排序

冒泡排序 - 最简单

• 相邻的两个数值比较大小，互换位置
• 记忆：外层0 ~ <length-1，内层0 ~ <length-1-i

/**
 * 冒泡排序：相邻两两比较，互换位置
 * 总共轮次：数组长度-1
 * 单轮次数：(数组长度-1)基础上逐级递减
 * @arr 传入int类型数组
 */
public static void bubbleSort (int[] arr) {
    // 外层轮次：需比较0~length-1次，因为最后一位不用比较
    for (int i = 0; i < arr.length-1; i++) {
        // 内层单轮次数：arr[j+1] 最大下标4，逐层递减
        for (int j = 0; j < arr.length-1-i; j++) {
            //if (arr[j] < arr[j+1]) { // 降序
            if (arr[j] > arr[j+1]) { // 升序
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

（1）比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。
（2）这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
（3）N=N-1，如果 N 不为 0 就重复前面二步，否则排序完成。

【逻辑】外层0 ~ <length-1，内层0 ~ <length-1-i。相邻元素，比较大小，互换位置
【优点】稳定
【缺点】慢，每次只能移动相邻两个数据

public class TestArraySort{
	public static void main(String[] args) {
		// Test 冒泡
		int[] nums = {1, 8, 3, 6, 2, 9, 7, 4, 5};
		bubbleSort(nums);
		for (int i = 0; i < nums.length; i++) {
			System.out.print(nums[i] + " "); // 1 2 3 4 5 6 7 8 9
		}
	}
	
	/**
	 * Java排序：冒泡排序
	 * 说明：相邻元素，比较大小，互换位置
	 * @param array 需要排序的无序整数类型数组
	 */
	public static void bubbleSort(int[] array) {
		// 1. 参数合法性判断
		if (null == array || array.length == 0) {
			return;
		}
		
		// 2. 冒泡排序主逻辑
		for (int i = 0; i < array.length-1; i++) {
			for (int j = 0; j < array.length-1 - i; j++) {
				if (array[j] > array[j+1]) { // 相邻元素，升序
				//if (array[j] < array[j+1]) { // 相邻元素，降序
					int tmp = array[j];
					array[j] = array[j+1];
					array[j+1] = tmp;
				}
			}
		}
	}
}