Java常见排序算法之冒泡排序、选择排序、插入排序、快速排序_java冒泡排序

一、冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序可以说是最简单的排序算法，想必大多数人都已经熟练掌握，这里分享自己在学习过程中觉得挺不错的两种实现。
写法一：基于常规冒泡写法，加了是否发生交换的判断，来减少冒泡次数

	/**
     * 冒泡排序 升序
     * 优化冒泡次数：通过标记是否发生交换来判断目前数组是否有序
     * @param array 待排序数组
     */
    public static void bubbleSort(int[] array) {
   
        for (int i = array.length - 1; i > 0; i--) {
   
            // 是否发生交换
            boolean swapped = false;
            for (int j = 0; j < i; j++) {
   
                if (array[j] > array[j + 1]) {
   
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
   
                // 没有发生交换，则说明数组已有序,停止冒泡
                break;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

写法二：通过上一次冒泡中最后一次发生交换的下标，来决定下一次冒泡结束的索引位置；同时也进行是否发生交换的判断，更好的优化排序效率（这个思路本人也第一次接触，感觉非常妙）

    /**
     * 冒泡排序 升序 较优法
     * 优化冒泡次数：冒泡结束的索引位置为0则直接结束
     * 优化比较次数：通过上一次冒泡中最后一次发生交换的下标，来决定下一次冒泡结束的索引位置
     * @param array 待排序数组
     */
    public static void bubbleSort2(int[] array) {
   
        // 冒泡结束的索引位置
        int end = array.length - 
1
2
3
4
5
6
7
8
9