详解冒泡排序算法

code随笔

发布于 2020-04-14 14:42:36

4950

发布于 2020-04-14 14:42:36

基本思想

冒泡排序的基本思想是：通过对待排序的序列从前向后依次比较相邻元素的值，如果发现逆序则交换。逆序的含义：如果想把序列从小到大排序，那么两个数中前面的比后面的大就是逆序。若需求是将序列从小到大排序，那么每一趟比较都会把值较大的逐渐从前面移动到后面。就像水底的泡泡一样：（如下图，图片来源于网络）

水底冒泡图片

例子

给定一个数组如下: [ 5 , 8 , -2 , 20 -6 ] 定义两个变量 i 和 j，初始状态 i 存第一个元素的索引，j存i代表元素的下一个元素的索引；

如下图：

初始状态

第一趟排序

(1) 5 < 8不用发生交换

第一趟排序1 然后 i ,j 均向后移动；

第一趟排序2 (2) 8 > -2 需要发生交换

第一趟排序2 然后 i ,j 均向后移动；

第一趟排序3

(3) 8 < 20 不需要发生交换

第一趟排序4 然后 i ,j 均向后移动；

第一趟排序5

(4) 20 > -6 需要发生交换

第一趟排序6

此时 j已经不能向后移动，第一趟排序结束，将当前最大的元素 20 移动到了最后的位置。

第一趟排序7

第二趟排序

将 i ,j重新赋值如下：

第二趟排序初始状态

第二趟排序

第三趟排序

将 i ,j重新赋值如下：

第三趟排序初始状态

第三趟排序

第四趟排序

将 i ,j重新赋值如下：

第四趟排序初始状态

第四趟排序

四个数组均到达该到的位置，排序完毕。由此可见，每一趟排序都会减少比较次数。会有数组长度-1趟排序。

代码

使用双重循环来完成：

int temp;//用于交换的临时变量
for(int i=0;i<arr.length - 1;i++){
        for(int j = 0;j<arr.length - 1 - i ; j++){
            if(arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
       }
}

优化

如果一趟排序都没有发生交换，表示已经有序了，没必要进行接下来的排序了。可以定义一个 flag ，初始值为false，如果发生交换，就赋值为true，否则一直是false直接退出循环。代码如下：

import java.lang.reflect.Array;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        bubbleSort(new int[]{5,8,-2,20,-6});
    }
    public static void bubbleSort(int[] arr) {

        int temp;//用于交换的临时变量
        boolean flag = false;//表示是否进行交换
        for(int i=0;i<arr.length - 1;i++){
            for(int j = 0;j<arr.length - 1 - i ; j++){
                if(arr[j] > arr[j + 1]){
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if(!flag){
                break;
            }else{
                flag = false;//将flag重新置为false
            }
        }

        System.out.println(Arrays.toString(arr));
    }
}