Java常用算法1——冒泡排序

冒泡排序
时间复杂度：O(n^2)
空间复杂度：O(1)，冒泡排序空间效率很高，只需要一个附加程序单元用于交换

思路：

对于一组包含n个数据的记录，冒泡排序在最坏的情况下需要进行n-1趟排序

第1趟：依次比较0和1、1和2、2和3...（n-2）和（n-1）索引的元素，如果发现第1个数据大于第2个数据，交换他们

经过第1趟排序，最大的元素排到了最后

第2趟：依次比较0和1、1和2、2和3...（n-3）和（n-3）索引的元素，如果发现第1个数据大于第2个数据，交换他们

经过第2趟排序，第二大的元素排到了倒数第二个位置

...

第n-1趟：比较0和1索引的元素，如果发现第1个数据大于第2个数据，交换他们

经过第n-1趟排序，第二小的元素排到了第二个位置

冒泡排序是稳定的

代码：

public class BubbleSort {

    private static final int SIZE = 10;

    public static void bubbleSort(int[] nums) {
        int temp;
        for(int i = 1; i < nums.length; i++) {
            for(int j = 0; j < nums.length - i; j++) {
                if(nums[j] > nums[j+1]) {
                    temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
            System.out.print("第" + i + "次排序的结果为：");
            for(int k = 0; k < nums.length; k++) {
                System.out.print("  " + nums[k]);
            }
            System.out.println();
        }
    }

    /**
     * 优化过的冒泡排序
     * 上面的方法中，即使n个数本来就是有序的，也会进行(n-1)次排序
     * 改进：当数组已经有序后，就中断循环
     */
    public static void bubbleSortOptimize(int[] nums) {
        int temp;
        for(int i = 1; i < nums.length; i++) {
            boolean flag = true;
            for(int j = 0; j < nums.length - i; j++) {
                if(nums[j] > nums[j+1]) {
                    temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                    flag = false;
                }
            }
            if(flag) {
                // 如果某趟没有交换，说明数组已经有序
                break;
            }
            System.out.print("第" + i + "次排序的结果为：");
            System.out.println(Arrays.toString(nums));
        }
    }

    public static void main(String[] args) {
        int[] nums = ArraysUtil.makeIntArray(10, 100, SIZE);
        System.out.print("排序前的数组为：");
        System.out.println(Arrays.toString(nums));
//      bubbleSort(nums);
        bubbleSortOptimize(nums);
        System.out.print("排序后的数组为：");
        System.out.println(Arrays.toString(nums));
    }
}

生产数组的工具类：

import java.util.Random;

/**
 * 操作数组的工具类
 */
public class ArraysUtil {

    private static Random rand = new Random();

    /**
     * 返回长度为size，并且数组中元素的大小范围为[begin, end)的int数组
     */
    public static int[] makeIntArray(int begin, int end, int size) {
        int[] nums = new int[size];
        for(int i = 0; i < size; i++) {
            nums[i] = begin + rand.nextInt(end - begin);
        }
        return nums;
    }
}