冒泡排序就这么简单

排序对我们来说是一点也不陌生了，当你打Dota的时候也有天梯分，从高往下数，这个排名是有规律的，就是一种排序。

冒泡排序的实现

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名冒泡排序。

算法描述：

• i从0开始，i与i+1比较，如果i>i+1，那么就互换
• i不断增加，直到i<n-1（n是数组元素的个数，n-1是数组已经最后一个元素） ，一趟下来，可以让数组元素中最大值排在数组的最后面

从最简单开始，首先我们创建一个数组，该数组有6位数字：

int[] arrays = {8, 3, 2, 6, 7, 9};

6位数的数组需要5躺排序的，每躺排序之后次数减1(因为前一趟已经把前一趟数的最大值确定下来了)！

于是我们可以根据for循环和变量将上面的代码进行排序：

int temp;

//外层循环是排序的趟数
for (int i = 0; i < arrays.length - 1 ; i++) {

    //内层循环是当前趟数需要比较的次数
    for (int j = 0; j < arrays.length - i - 1; j++) {

        //前一位与后一位与前一位比较，如果前一位比后一位要大，那么交换
        if (arrays[j] > arrays[j + 1]) {
            temp = arrays[j];
            arrays[j] = arrays[j + 1];
            arrays[j + 1] = temp;
        }
    }
}

冒泡排序优化

从上面的例子我们可以看出来，如果数据足够乱的情况下是需要经过5躺比较才能将数组完整排好序。但是我们在第二躺比较后就已经得到排好序的数组了。

但是，我们的程序在第二趟排序后仍会执行第三趟、第四趟排序。这是没有必要的，因此我们可以对其进行优化一下：

• 如果在某躺排序中没有发生交换位置，那么我们可以认为该数组已经排好序了
  • 因为我们每趟排序的目的就是将当前趟最大的数置换到对应的位置上，没有发生置换说明就已经排好序了

代码如下：

//装载临时变量
int temp;

//记录是否发生了置换， 0 表示没有发生置换、 1 表示发生了置换
int isChange;

//外层循环是排序的趟数
for (int i = 0; i < arrays.length - 1; i++) {

    //每比较一趟就重新初始化为0
    isChange = 0;

    //内层循环是当前趟数需要比较的次数
    for (int j = 0; j < arrays.length - i - 1; j++) {

        //前一位与后一位与前一位比较，如果前一位比后一位要大，那么交换
        if (arrays[j] > arrays[j + 1]) {
            temp = arrays[j];
            arrays[j] = arrays[j + 1];
            arrays[j + 1] = temp;

            //如果进到这里面了，说明发生置换了
            isChange = 1;

        }
    }
    //如果比较完一趟没有发生置换，那么说明已经排好序了，不需要再执行下去了
    if (isChange == 0) {
        break;
    }
}