关于排序:程序员必知的排序算法一-冒泡排序

冒泡排序简介

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

算法原理

将邻近的两个数字两两进行比拟，依照从小到大或者从大到小的程序进行替换。

算法原理示意图

数组冒泡排序前↓↓↓

冒泡排序执行过程 [gif 动图]↓↓↓

数组冒泡排序后↓↓↓

代码实现

public class Sort {public static void main(String[] args) {int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        bubbleSort(arr);
        //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 冒泡排序
     * @param arr   想要排序的数组
     */
    public static void bubbleSort(int[] arr){
        // 管制比拟轮数
        for (int i = 0; i < arr.length; i++) {
            // 每轮比拟多少次
            for (int j = 0; j < arr.length - i -1; j++) {if (arr[j] > arr[j + 1]) {
                    // temp 为一个长期变量，为了存储替换时的长期值
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

这里须要思考几个问题

• 外层的循环起到什么作用 / 外层循环代表什么？
• 外层循环中的 -1 是做什么的？
• 内层的循环起到什么作用 / 内层循环代表什么？
• 内层循环中的 -1 是做什么的？
• 内层循环中的 -i 是做什么的？
• 长期变量 temp 起到什么作用？

首先须要了解的是冒泡排序是从头开始，两两比拟，将最大的数放到开端。而后再次从头开始，以此类推……。

• 外层的循环起到什么作用 / 外层循环代表什么？

  总共循环了多少轮, 或者能够了解为将最大值放在开端的次数

• 外层循环中的 -1 是做什么的？

  因为咱们每次都是从头开始比拟, 并且每次都会将最大的数顺次放在开端, 当只剩最初一个数时, 它曾经是咱们的最小的数了, 而且就在第一位, 咱们再将它与其它的数进行比拟就曾经没有意义了, 所以咱们用到了 -1

• 内层的循环起到什么作用？

  每轮比拟多少次, 或者能够了解为两两替换的次数

• 内层循环中的 -1 是做什么的？

  因为咱们是两两进行比拟，arr[j] > arr[j+1]，咱们在做每轮比拟的最初时，咱们只须要比拟倒数第二位和倒数第一位即可，因为咱们 arr[n] 中的 n 示意的是咱们数组的下标，不 -1 会呈现数组下标越界异样 arr.length – 1

• 内层循环中的 -i 是做什么的？

  i 是咱们外层循环的变量，能够了解为将最大值放在开端的次数，或者开端曾经排序好了几个值，所以为了晋升效率不去做过多运算，咱们将内层循环的次数改为 arr.length – i

• 长期变量 temp 起到什么作用？

  长期变量是为了存储替换过程中的长期值，使之在替换过程中值能够不被笼罩掉，得到原来的值