好程序员Java学习路线分享冒泡排序及优化

​ 好程序员Java学习路线分享冒泡排序及优化，冒泡排序是一定典型的交换排序，如排序规则是升序，有如下数列：

成都创新互联公司专注于康保网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供康保营销型网站建设，康保网站制作、康保网页设计、康保网站官网定制、小程序定制开发服务，打造康保网络公司原创品牌,更为您提供康保网站排名全网营销落地服务。

  A[0] A[1] A[2] A[3] ...... A[n]

​ 将A[0]和A[1]比较，如果A[0]>A[1] ，则交换两个元素的位置，否则不变， 再继续比较A[1]和A[2]，直到A[n-1]和A[n]。即比较相邻的两个元素，如果前一个大，就交换（否则不交换），再继续比较后面的元素，每一轮比较之后，最大的元素会移动到最后（完成一轮冒泡）；再开始第二轮冒泡，本次会选出第二大的元素。重复冒泡的过程，直到没有相邻的元素需要交换，则排序完成，像碳酸饮料中的气泡，故而称为冒泡排序。

简化过程，设置一个简单的数组，在编程中，元素的索引从0开始：

[5, 3, 1, 4, 2]

    int[] nums = {5, 3, 1, 4, 2};

    //要比较n次，n是数组中数字的个数

    for (int i = 0; i < nums.length; i++) {

        //比较j和j+1位置的元素，每比较完一次，最大的元素会移动到末尾

        for (int j = 0; j < nums.length - 1; j++) {

            if (nums[j] > nums[j + 1]) {

                int temp = nums[j + 1];

                nums[j + 1] = nums[j];

                nums[j] = temp;

            }

        }

    }

第一轮比较，经过这一轮比较，最大的元素在末尾

[5, 3, 1, 4, 2] 比较第0和1个元素 ,交换[3, 5, 1, 4, 2]

[3, 5, 1, 4, 2] 比较第1和2个元素 ,交换[3, 1, 5, 4, 2]

[3, 1, 5, 4, 2] 比较第2和3个元素 ,交换[3,1, 4, 5, 2]

[3, 1, 4, 5, 2] 比较第3和4个元素 ,交换[3, 1, 4, 2, 5] 最大的元素在末尾

第二轮比较，经过这轮比较，最大的两个元素在末尾

[3, 1, 4, 2, 5] 比较第0和1个元素 ,交换[1, 3, 4, 2, 5]

[1, 3, 4, 2, 5] 比较第1和2个元素 ,不动 [1, 3, 4, 2, 5]

[1, 3, 4, 2, 5] 比较第2和3个元素 ,交换[1, 3, 2, 4, 5]

[1, 3, 2, 4, 5] 比较第3和4个元素 ,不动 [1, 3, 2, 4, 5]  这次比较是多余的，因为第1轮过后，最大的元素在末尾

第三轮比较，经过这轮比较，最大的三个元素在末尾

[1, 3, 2, 4, 5] 比较第0和1个元素 ,不动 [1, 3, 2, 4, 5]

[1, 3, 2, 4, 5] 比较第1和2个元素 ,交换[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5] 比较第2和3个元素 ,不动 [1, 2, 3, 4, 5]  这次比较多余的

[1, 2, 3, 4, 5] 比较第3和4个元素 ,不动 [1, 2, 3, 4, 5]  这次比较是多余的

第四轮比较，经过这轮比较，最大的四个元素在末尾

[1, 2, 3, 4, 5] 比较第0和1个元素 ,不动 [1, 2, 3, 4, 5]

[1, 2, 3, 4, 5] 比较第1和2个元素 ,不动 [1, 2, 3, 4, 5]  这次比较是多余的

[1, 2, 3, 4, 5] 比较第2和3个元素 ,不动 [1, 2, 3, 4, 5]  这次比较是多余的

[1, 2, 3, 4, 5] 比较第3和4个元素 ,不动 [1, 2, 3, 4, 5]  这次比较是多余的

第五轮比较，经过这轮比较，排序完成

[1, 2, 3, 4, 5] 比较第0和1个元素 ,不动 [1, 2, 3, 4, 5]  这次比较是多余的

[1, 2, 3, 4, 5] 比较第1和2个元素 ,不动 [1, 2, 3, 4, 5]  这次比较是多余的

[1, 2, 3, 4, 5] 比较第2和3个元素 ,不动 [1, 2, 3, 4, 5]  这次比较是多余的

[1, 2, 3, 4, 5] 比较第3和4个元素 ,不动 [1, 2, 3, 4, 5]  这次比较是多余的

可以看到冒泡排序每次都从头比较，比较到末尾，但实际

第一轮比较后，最后1个数是最大的，下一轮不需要参与比较

第二轮比较后，最后2个数是最大的，下一轮不需要参与比较

第三轮比较后，最后3个数是最大的...

所以第n轮比较的时候，可以排除掉末尾已经排序好的元素，即末尾n-1个元素

int[] nums = {5, 3, 1, 4, 2};

        //要比较n次，n是数组中数字的个数

        for (int i = 0; i < nums.length; i++) {

            //比较j和j+1位置的元素，每比较完一次，最大的元素会移动到末尾

            //最后i个元素不参与本次比较

            for (int j = 0; j < nums.length - 1 - i; j++) {

                if (nums[j] > nums[j + 1]) {

                    int temp = nums[j + 1];

                    nums[j + 1] = nums[j];

                    nums[j] = temp;

                }

            }

        }

运行结果：

第一轮比较，经过这一轮比较，最大的元素在末尾

[5, 3, 1, 4, 2] 比较第0和1个元素 ,交换[3, 5, 1, 4, 2]

[3, 5, 1, 4, 2] 比较第1和2个元素 ,交换[3, 1, 5, 4, 2]

[3, 1, 5, 4, 2] 比较第2和3个元素 ,交换[3,1, 4, 5, 2]

[3, 1, 4, 5, 2] 比较第3和4个元素 ,交换[3, 1, 4, 2, 5] 最大的元素在末尾

第二轮比较，经过这轮比较，最大的两个元素在末尾

[3, 1, 4, 2, 5] 比较第0和1个元素 ,交换[1, 3, 4, 2, 5]

[1, 3, 4, 2, 5] 比较第1和2个元素 ,不动 [1, 3, 4, 2, 5]

[1, 3, 4, 2, 5] 比较第2和3个元素 ,交换[1, 3, 2, 4, 5]

第三轮比较，经过这轮比较，最大的三个元素在末尾

[1, 3, 2, 4, 5] 比较第0和1个元素 ,不动 [1, 3, 2, 4, 5]

[1, 3, 2, 4, 5] 比较第1和2个元素 ,交换[1, 2, 3, 4, 5]

第四轮比较，经过这轮比较，最大的四个元素在末尾

[1, 2, 3, 4, 5] 比较第0和1个元素 ,不动 [1, 2, 3, 4, 5]

上面的算法，可以减少重复比较的次数，比较的次数是固定的。但如果本来数组中的元素就相对有序，则会出现如下状况：

初始数组是：[3, 1, 2, 4, 5]

第一轮

[3, 1, 2, 4, 5]比较第0和1个元素,交换[1, 3, 2, 4, 5]

[1, 3, 2, 4, 5]比较第1和2个元素,交换[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]比较第2和3个元素,不动[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]比较第3和4个元素,不动[1, 2, 3, 4, 5]

第二轮

[1, 2, 3, 4, 5]比较第0和1个元素,不动[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]比较第1和2个元素,不动[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]比较第2和3个元素,不动[1, 2, 3, 4, 5]

第三轮

[1, 2, 3, 4, 5]比较第0和1个元素,不动[1, 2, 3, 4, 5]

[1,2, 3, 4, 5]比较第1和2个元素,不动[1, 2, 3, 4, 5]

第四轮

[1, 2, 3, 4, 5]比较第0和1个元素,不动[1, 2, 3, 4, 5]

实际上数组中的元素，开始的时候只有数字3的位置需要移动，其它元素相对都是有序的。当3移动完成后，其它的元素不需要一定。所以在第二轮发现没有任何元素交换之后，就表示排序已经完成，第三轮和第四轮是多余的。

对于冒泡排序的优化，如果某一轮比较中没有发生任何交换，则代表排序已经完成，不需要再进行排序了：

        int[] nums = {3, 1, 2, 4, 5};

        boolean flag;//是否交换的标志

        //要比较n次，n是数组中数字的个数

        for (int i = 0; i < nums.length; i++) {

            // 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换

            flag = false;

            //比较j和j+1位置的元素，每比较完一次，最大的元素会移动到末尾

            //最后i个元素不参与本次比较

            for (int j = 0; j < nums.length - 1 - i; j++) {

                if (nums[j] > nums[j + 1]) {

                    int temp = nums[j + 1];

                    nums[j + 1] = nums[j];

                    nums[j] = temp;

                    flag = true;    //表示本轮发生了交换

                }

            }

            // 如果为false，代表本轮没有交换，元素已经有序

            if(!flag) break;

        }

    }

初始数组是：[3, 1, 2, 4, 5]

第一轮

[3, 1, 2, 4, 5]比较第0和1个元素,交换[1, 3, 2, 4, 5]

[1, 3, 2, 4, 5]比较第1和2个元素,交换[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]比较第2和3个元素,不动[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]比较第3和4个元素,不动[1, 2, 3, 4, 5]

第二轮

[1, 2, 3, 4, 5]比较第0和1个元素,不动[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]比较第1和2个元素,不动[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]比较第2和3个元素,不动[1, 2, 3, 4, 5]

在上面的排序中，3是最后一个移动的元素。3之后的元素都是有序的。所以只要比较3之前的元素即可。最后一次发生交换的元素，它后面的元素都是有序的，不需要再参与比较

int[] nums = {3, 1, 2, 4, 5};

        boolean flag;//是否交换的标志

        int lastExchangeIndex =0;//最后一次交换的位置

        int sortBorder = nums.length - 1;

        //要比较n次，n是数组中数字的个数

        for (int i = 0; i < nums.length; i++) {

            // 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换

            flag = false;

            //比较j和j+1位置的元素，每比较完一次，最大的元素会移动到末尾

            //最后i个元素不参与本次比较

            for (int j = 0; j < sortBorder ; j++) {

                if (nums[j] > nums[j + 1]) {

                    int temp = nums[j + 1];

                    nums[j + 1] = nums[j];

                    nums[j] = temp;

                    flag = true;    //表示本轮发生了交换

                    lastExchangeIndex =j;//记录最后一次发生交换的位置

                }

            }

            // 如果为false，代表本轮没有交换，元素已经有序

            sortBorder = lastExchangeIndex;

            if(!flag) break;

        }

运行结果：

第一轮

[3, 1, 2, 4, 5]比较第0和1个元素,交换[1, 3, 2, 4, 5]

[1, 3, 2, 4, 5]比较第1和2个元素,交换[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]比较第2和3个元素,不动[1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]比较第3和4个元素,不动[1, 2, 3, 4, 5]

第二轮

[1, 2, 3, 4, 5]比较第0和1个元素,不动[1, 2, 3, 4, 5]