冒泡排序算法及优化算法

2021-03-01
halley.fang
training
 

冒泡排序算法及优化算法

冒泡排序

排序算法

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 冒泡排序
 * 和相邻的元素比较，大的往后移
 */
public class BubbleSort {

    private Logger logger = LoggerFactory.getLogger(BubbleSort.class);

    public void bubbleSort(int[] bubbleArray){
        if(bubbleArray==null || bubbleArray.length<2){
            return;
        }
        int tempValue;

        //为什么要减1，一是由于最后一次比较是倒数第二个元素进行比较，最后一位不需要进行比较，而且不减1的话会造成第一个元素比较时发生数组越界错误
        for(int i=0;i<bubbleArray.length-1;i++){
            for(int j=0;j<bubbleArray.length-1-i;j++) {
                if (bubbleArray[j] > bubbleArray[j + 1]) {
                    tempValue = bubbleArray[j];
                    bubbleArray[j] = bubbleArray[j + 1];
                    bubbleArray[j + 1] = tempValue;
                }
            }
            logger.debug("第 [{}] 次排序结果：" + showArray(bubbleArray),i);
        }
        logger.debug("冒泡排序结果：" + showArray(bubbleArray));
    }

    public String showArray(int[] array){
        if(array == null){
            return null;
        }
        String showArray = "";
        for(int a:array){
            showArray = showArray + a + ",";
        }
        showArray = showArray.substring(0,showArray.length()-1);
        return showArray;
    }

    public static void main(String args[]){
        int[] bubbleArray = {1,3,6,4,10,7,22,36,11,25,50,34};
        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.bubbleSort(bubbleArray);
    }
}

输出结果:

第 [0] 次排序结果：1,3,4,6,7,10,22,11,25,36,34,50
第 [1] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
第 [2] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
第 [3] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
第 [4] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
第 [5] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
第 [6] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
第 [7] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
第 [8] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
第 [9] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
第 [10] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
冒泡排序结果：1,3,4,6,7,10,11,22,25,34,36,50

算法优化

优化1

从输出结果可以发现排序2次后已经完成了排序结果，后续的循环排序都是多余的，所以加一个标识来判断是否发生的排序动作

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 冒泡排序
 * 和相邻的元素比较，大的往后移
 */
public class BubbleSort {

    private Logger logger = LoggerFactory.getLogger(BubbleSort.class);

    public void bubbleSort(int[] bubbleArray){
        if(bubbleArray==null || bubbleArray.length<2){
            return;
        }
        int tempValue;

        //为什么要减1，一是由于最后一次比较是倒数第二个元素进行比较，最后一位不需要进行比较，而且不减1的话会造成第一个元素比较时发生数组越界错误
        for(int i=0;i<bubbleArray.length-1;i++){
            Boolean isComplete = true;
            for(int j=0;j<bubbleArray.length-1-i;j++) {
                if (bubbleArray[j] > bubbleArray[j + 1]) {
                    tempValue = bubbleArray[j];
                    bubbleArray[j] = bubbleArray[j + 1];
                    bubbleArray[j + 1] = tempValue;
                    isComplete = false;
                }
            }
            logger.debug("第 [{}] 次排序结果：" + showArray(bubbleArray),i);
            if(isComplete){
                break;
            }
        }
        logger.debug("冒泡排序结果：" + showArray(bubbleArray));
    }

    public String showArray(int[] array){
        if(array == null){
            return null;
        }
        String showArray = "";
        for(int a:array){
            showArray = showArray + a + ",";
        }
        showArray = showArray.substring(0,showArray.length()-1);
        return showArray;
    }

    public static void main(String args[]){
        int[] bubbleArray = {1,3,6,4,10,7,22,36,11,25,50,34};
        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.bubbleSort(bubbleArray);
    }
}

输出结果为：

第 [0] 次排序结果：1,3,4,6,7,10,22,11,25,36,34,50
第 [1] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
第 [2] 次排序结果：1,3,4,6,7,10,11,22,25,34,36,50
冒泡排序结果：1,3,4,6,7,10,11,22,25,34,36,50

优化2

我们先在优化1的基础上在子循环中增加日志打印

logger.debug("第 [{}] 次排序 第 [{}] 子循环结果：" + showArray(bubbleArray),i,j);

并且增加一个数组元素方便看出效果

int[] bubbleArray = {1,3,26,6,4,10,7,22,36,11,25,50,34};

运行优化1代码程序输出结果为：

第 [0] 次排序 第 [0] 子循环结果：1,3,26,6,4,10,7,22,36,11,25,50,34
第 [0] 次排序 第 [1] 子循环结果：1,3,26,6,4,10,7,22,36,11,25,50,34
第 [0] 次排序 第 [2] 子循环结果：1,3,6,26,4,10,7,22,36,11,25,50,34
第 [0] 次排序 第 [3] 子循环结果：1,3,6,4,26,10,7,22,36,11,25,50,34
第 [0] 次排序 第 [4] 子循环结果：1,3,6,4,10,26,7,22,36,11,25,50,34
第 [0] 次排序 第 [5] 子循环结果：1,3,6,4,10,7,26,22,36,11,25,50,34
第 [0] 次排序 第 [6] 子循环结果：1,3,6,4,10,7,22,26,36,11,25,50,34
第 [0] 次排序 第 [7] 子循环结果：1,3,6,4,10,7,22,26,36,11,25,50,34
第 [0] 次排序 第 [8] 子循环结果：1,3,6,4,10,7,22,26,11,36,25,50,34
第 [0] 次排序 第 [9] 子循环结果：1,3,6,4,10,7,22,26,11,25,36,50,34
第 [0] 次排序 第 [10] 子循环结果：1,3,6,4,10,7,22,26,11,25,36,50,34
第 [0] 次排序 第 [11] 子循环结果：1,3,6,4,10,7,22,26,11,25,36,34,50
第 [0] 次排序结果：1,3,6,4,10,7,22,26,11,25,36,34,50
第 [1] 次排序 第 [0] 子循环结果：1,3,6,4,10,7,22,26,11,25,36,34,50
第 [1] 次排序 第 [1] 子循环结果：1,3,6,4,10,7,22,26,11,25,36,34,50
第 [1] 次排序 第 [2] 子循环结果：1,3,4,6,10,7,22,26,11,25,36,34,50
第 [1] 次排序 第 [3] 子循环结果：1,3,4,6,10,7,22,26,11,25,36,34,50
第 [1] 次排序 第 [4] 子循环结果：1,3,4,6,7,10,22,26,11,25,36,34,50
第 [1] 次排序 第 [5] 子循环结果：1,3,4,6,7,10,22,26,11,25,36,34,50
第 [1] 次排序 第 [6] 子循环结果：1,3,4,6,7,10,22,26,11,25,36,34,50
第 [1] 次排序 第 [7] 子循环结果：1,3,4,6,7,10,22,11,26,25,36,34,50
第 [1] 次排序 第 [8] 子循环结果：1,3,4,6,7,10,22,11,25,26,36,34,50
第 [1] 次排序 第 [9] 子循环结果：1,3,4,6,7,10,22,11,25,26,36,34,50
第 [1] 次排序 第 [10] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [1] 次排序结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [0] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [1] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [2] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [3] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [4] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [5] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [6] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [2] 次排序 第 [7] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [2] 次排序 第 [8] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [2] 次排序 第 [9] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [2] 次排序结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [0] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [1] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [2] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [3] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [4] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [5] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [6] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [7] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [8] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序结果：1,3,4,6,7,10,11,22,25,26,34,36,50
冒泡排序结果：1,3,4,6,7,10,11,22,25,26,34,36,50

从结果可以看出循环到3次的时候后面的几位数字已经不需要再进行比较，我们可以考虑记录下上一次循环最后发生排序变化的位置，在该位置后面的元素都是已经排序完成的，所以下一次排序循环的次数只需要到记录的位置即可，代码优化如下

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 冒泡排序
 * 和相邻的元素比较，大的往后移
 */
public class BubbleSort {

    private Logger logger = LoggerFactory.getLogger(BubbleSort.class);

    public void bubbleSort(int[] bubbleArray){
        if(bubbleArray==null || bubbleArray.length<2){
            return;
        }
        int tempValue;
        int tempPosition = 0;
        int forLength = bubbleArray.length-1 ;

        //为什么要减1，一是由于最后一次比较是倒数第二个元素进行比较，最后一位不需要进行比较，而且不减1的话会造成第一个元素比较时发生数组越界错误
        for(int i=0;i<bubbleArray.length-1;i++){
            Boolean isComplete = true;
            for(int j=0;j<forLength;j++) {
                if (bubbleArray[j] > bubbleArray[j + 1]) {
                    tempValue = bubbleArray[j];
                    bubbleArray[j] = bubbleArray[j + 1];
                    bubbleArray[j + 1] = tempValue;
                    isComplete = false;
                    tempPosition = j;
                }
                logger.debug("第 [{}] 次排序 第 [{}] 子循环结果：" + showArray(bubbleArray),i,j);
            }
            forLength = tempPosition;
            logger.debug("第 [{}] 次排序结果：" + showArray(bubbleArray),i);
            if(isComplete){
                break;
            }
        }
        logger.debug("冒泡排序结果：" + showArray(bubbleArray));
    }

    public String showArray(int[] array){
        if(array == null){
            return null;
        }
        String showArray = "";
        for(int a:array){
            showArray = showArray + a + ",";
        }
        showArray = showArray.substring(0,showArray.length()-1);
        return showArray;
    }

    public static void main(String args[]){
        int[] bubbleArray = {1,3,26,6,4,10,7,22,36,11,25,50,34};
        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.bubbleSort(bubbleArray);
    }
}

输出结果如下：可以看出第3次排序比优化1中的执行结果少了循环次数

第 [0] 次排序 第 [0] 子循环结果：1,3,26,6,4,10,7,22,36,11,25,50,34
第 [0] 次排序 第 [1] 子循环结果：1,3,26,6,4,10,7,22,36,11,25,50,34
第 [0] 次排序 第 [2] 子循环结果：1,3,6,26,4,10,7,22,36,11,25,50,34
第 [0] 次排序 第 [3] 子循环结果：1,3,6,4,26,10,7,22,36,11,25,50,34
第 [0] 次排序 第 [4] 子循环结果：1,3,6,4,10,26,7,22,36,11,25,50,34
第 [0] 次排序 第 [5] 子循环结果：1,3,6,4,10,7,26,22,36,11,25,50,34
第 [0] 次排序 第 [6] 子循环结果：1,3,6,4,10,7,22,26,36,11,25,50,34
第 [0] 次排序 第 [7] 子循环结果：1,3,6,4,10,7,22,26,36,11,25,50,34
第 [0] 次排序 第 [8] 子循环结果：1,3,6,4,10,7,22,26,11,36,25,50,34
第 [0] 次排序 第 [9] 子循环结果：1,3,6,4,10,7,22,26,11,25,36,50,34
第 [0] 次排序 第 [10] 子循环结果：1,3,6,4,10,7,22,26,11,25,36,50,34
第 [0] 次排序 第 [11] 子循环结果：1,3,6,4,10,7,22,26,11,25,36,34,50
第 [0] 次排序结果：1,3,6,4,10,7,22,26,11,25,36,34,50
第 [1] 次排序 第 [0] 子循环结果：1,3,6,4,10,7,22,26,11,25,36,34,50
第 [1] 次排序 第 [1] 子循环结果：1,3,6,4,10,7,22,26,11,25,36,34,50
第 [1] 次排序 第 [2] 子循环结果：1,3,4,6,10,7,22,26,11,25,36,34,50
第 [1] 次排序 第 [3] 子循环结果：1,3,4,6,10,7,22,26,11,25,36,34,50
第 [1] 次排序 第 [4] 子循环结果：1,3,4,6,7,10,22,26,11,25,36,34,50
第 [1] 次排序 第 [5] 子循环结果：1,3,4,6,7,10,22,26,11,25,36,34,50
第 [1] 次排序 第 [6] 子循环结果：1,3,4,6,7,10,22,26,11,25,36,34,50
第 [1] 次排序 第 [7] 子循环结果：1,3,4,6,7,10,22,11,26,25,36,34,50
第 [1] 次排序 第 [8] 子循环结果：1,3,4,6,7,10,22,11,25,26,36,34,50
第 [1] 次排序 第 [9] 子循环结果：1,3,4,6,7,10,22,11,25,26,36,34,50
第 [1] 次排序 第 [10] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [1] 次排序结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [0] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [1] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [2] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [3] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [4] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [5] 子循环结果：1,3,4,6,7,10,22,11,25,26,34,36,50
第 [2] 次排序 第 [6] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [2] 次排序 第 [7] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [2] 次排序 第 [8] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [2] 次排序 第 [9] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [2] 次排序结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [0] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [1] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [2] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [3] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [4] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序 第 [5] 子循环结果：1,3,4,6,7,10,11,22,25,26,34,36,50
第 [3] 次排序结果：1,3,4,6,7,10,11,22,25,26,34,36,50
冒泡排序结果：1,3,4,6,7,10,11,22,25,26,34,36,50

上一篇 Junit+mockito+powermock单元测试初探

下一篇 Selenium使用指南

Comments

Table of contents