一、初始排序（Sorting）

排序：把一串没有按照顺序排列的数按照升序或降序排列。

排序前：1、6、2、7、8、3、9、5、4
升序：1、2、3、4、5、6、7、8、9
降序：9、8、7、6、5、4、3、2、1

二、十大排序算法

01、冒泡排序（Bubble Sort）
02、选择排序（Selection Sort）
03、插入排序（Insertion Sort）
04、归并排序（Merge Sort）
05、快速排序（Quick Sort）
06、希尔排序（Shell Sort）
07、堆排序（Heap Sort）
08、基数排序（Radix Sort）
09、桶排序（Bucket Sort）
10、计数排序（Counting Sort）

三、冒泡排序（Bubble Sort）介绍

数据结构可视化 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

思想：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。

① 从头开始比较每一对相邻的元素，如果第1个比第2个大就交换它们的位置。

② 执行完一轮后，最末尾的那个元素是整个数列中最大的元素。

③ 忽略 ① 中找到的最大元素，重复执行步骤 ①，直到全部元素有序。

四、Java 代码实现

/**
 * 冒泡排序
 */
public class BubbleSort {

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

        for (int end = nums.length; end > 0; end--) {
            for (int begin = 1; begin < end; begin++) {
                if (nums[begin] < nums[begin - 1]) {
                    int temp;
                    temp = nums[begin];
                    nums[begin] = nums[begin - 1];
                    nums[begin - 1] = temp;
                }
            }
        }
    }

}

五、问题讨论

(1) 如果数列本身已经完全有序

如果数列本身已经完全有序，可提前终止冒泡排序。

/**
 * 冒泡排序
 */
public class BubbleSort {

    public static void main(String[] args) {  
        for (int end = nums.length; end > 0; end--) {
            boolean noSwap = true;
            for (int begin = 1; begin < end; begin++) {
                if (nums[begin] < nums[begin - 1]) { // true: 执行交换
                    int temp;
                    temp = nums[begin];
                    nums[begin] = nums[begin - 1];
                    nums[begin - 1] = temp;
                    noSwap = false;
                }
            }
            if (noSwap) break;
        } 
    }
 
}

(2) 如果数列尾部已经局部有序

如果数列尾部已经局部有序，可记录最后一次交换的位置，减少比较次数。

    public static Integer[] bubble3(Integer[] nums) {
       for (int end = nums.length; end > 0; end--) {
           // lastSwapIdx 的初始值在数组完全有序的时候有用
           int lastSwapIdx = 1; // 最后一次交换的位置
           for (int begin = 1; begin < end; begin++) {
               if (nums[begin] < nums[begin - 1]) {
                   int temp;
                   temp = nums[begin];
                   nums[begin] = nums[begin - 1];
                   nums[begin - 1] = temp;
                   lastSwapIdx = begin;
               }
           }
           end = lastSwapIdx;
       }
       return nums;
   }

六、相关工具类

public class QYIntegers {

    /**
     * 生成任意范围内的任意个随机正整数
     *
     * @param number 随机数个数
     * @param start  起始范围
     * @param end    结束范围
     * @return 随机数数组
     */
    public static Integer[] createRandom(Integer number, Integer start, Integer end) {
        if (number == null || number < 2) number = 8;
        if (start == null || start < 0) start = 0;
        if (end == null || end < 3) end = 3;

        Integer[] randoms = new Integer[number];

        for (Integer i = 0; i < number; i++) {
            randoms[i] = new Random().nextInt(end - start) + start;
        }

        return randoms;
    }

    /**
     * 打印整数数组
     *
     * @param numArr  要打印的数组
     * @param delimit 每个数之间的分隔符
     */
    public static void printIntArr(Integer[] numArr, String delimit) {
        StringBuilder sBuilder = new StringBuilder();
        for (Integer num : numArr) {
            sBuilder.append(num).append(delimit);
        }
        System.out.println(sBuilder.toString());
    }

    public static void printIntArr(Integer[] numArr) {
        printIntArr(numArr, "_");
    }

    /**
     * 拷贝整型数组
     */
    public static Integer[] copyInt(Integer[] ints) {
        Integer[] newInts = new Integer[ints.length];
        for (int i = 0; i < ints.length; i++) {
            newInts[i] = ints[i];
        }
        return newInts;
    }

}

/**
 * 测试某段代码的执行花费了多少时间
 */
public class Times {
    private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");

    public interface Task {
        void execute();
    }

    public static void test(String title, Task task) {
        if (task == null) return;
        title = (title == null) ? "" : ("【" + title + "】");
        System.out.println(title);
        System.out.println("开始：" + fmt.format(new Date()));
        long begin = System.currentTimeMillis();
        task.execute();
        long end = System.currentTimeMillis();
        System.out.println("结束：" + fmt.format(new Date()));
        double delta = (end - begin) / 1000.0;
        System.out.println("耗时：" + delta + "秒");
        System.out.println("-------------------------------------");
    }
}