冒泡排序法——Java实现

算法描述

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。（百度百科）

算法原理

1. 两个相邻的元素相比较，若第一个比第二个大，就进行交换
2. 第二个和第三个元素重复第一步的工作，直到与最后一个元素比较完，完成后最后一个元素就是最大的那个
3. 重复上述两个步骤，直到全部元素比较完。

算法实现

这里我以Java中的数组为例，来具体实现下冒泡排序

假设数组为 arr={34,42,78,12,3}，利用冒泡排序法將数组进行排序。

第一步

1. 数组第一个数与第二数进行比较，即 arr[0]=34 与 arr[1]=42 比较，42大于34，所以不交换。数组为arr={34,42,78,12,3}
2. 数组第二个数与第三数进行比较，即 arr[1]=42 与 arr[2]=78 比较，78大于42，所以不交换。数组为arr={34,42,78,12,3}
3. 数组第三个数与第四数进行比较，即 arr[2]=78 与 arr[3]=12 比较，78大于12，所以进行交换。数组为arr={34,42,12,78,3}
4. 数组第四个数与第五数进行比较，即 arr[3]=78 与 arr[4]=3 比较，78大于3，所以进行交换。数组为arr={34,42,12,3,78}

代码实现

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

注意：代码实现时容易造成数组越界，所以 for 循环的判断条件是 x < arr.length - 1

第二步

重复第一步工作，但最后不需要与前面比较过的元素在进行比较，所以需要比较的次数逐渐减少。

代码实现

for (int x = 0; x < arr.length - 2; x++) {
        if (arr[x] > arr[x + 1]) {
            int temp = arr[x];
            arr[x] = arr[x + 1];
            arr[x + 1] = temp;
        }
    }

注意：第二次比较时，不需要与第一步比较的元素再进行比较，所以 for 循环的判断条件是 x < arr.length - 2

重复上述两个步骤，直到数组比较完成。

代码优化

由上述实现代码发现，比较的过程都是相同的，只是后一步所需比较的步数比前一步少一。所以可以用 for 循环將代码优化，具体代码如下：

for (int x = 0; x < arr.length; x++) {
        for (int y = 0; y < arr.length - 1 - x; y++) {
            if (arr[y] > arr[y + 1]) {
                int temp = arr[y];
                arr[y] = arr[y + 1];
                arr[y + 1] = temp;
            }
        }
    }

完整代码请访问：https://github.com/xieys 欢迎Follow和star