【排序】冒泡排序及优化

以下介绍来自百度百科：

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序算法的原理如下：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度

冒泡排序总的平均时间复杂度为  。

冒泡排序最好的时间复杂度为。 

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

以下是Java实现：

package com.jandmin.demo.leetcode.sort;

import java.util.Random;

/**
 * @description: 冒泡排序
 * @author: JandMin
 **/
public class BubbleSort {
    private static int countInner = 0;
    private static int countOut = 0;
    private static int countInner1 = 0;
    private static int countOut1 = 0;
    private static int countInner2 = 0;
    private static int countOut2 = 0;
    private static int countInner3 = 0;
    private static int countOut3 = 0;
    private static int countInner4 = 0;
    private static int countOut4 = 0;
    /**
     * 初始化数组
     * @param len 数组长度
     * @return
     */
    private static int[] initArray(int len){
        if(len <= 0){
            return new int[0];
        }
        int[] array = new int[len];
        Random random = new Random();
        int ordinal = 0;
        if (len > 100){ // 为了让后面100个位顺序的数字
            ordinal = len;
            len = len -100;
        }
        for(int i=0; i<len; i++){
            array[i] = random.nextInt(len);
        }
        for(int i=len; i<ordinal; i++){ // 最后 100 个是顺序的
            array[i] = i + 1;
        }
//        System.out.println("原数组： "+ JSONObject.toJSONString(array));
        return array;
    }

    public static void main(String[] args) {
        int len = 10000;
        int[] array = initArray(len);
        // 方案0
        int[] array0 = array.clone();
        long start = System.currentTimeMillis();
        bubbleSort(array0);
        System.out.println(" 0耗时："+(System.currentTimeMillis()-start)+" ms,countInner:"+countInner+",countOut:"+countOut);
//        System.out.println("方案零： "+ JSONObject.toJSONString(array0));
        // 方案一
        int[] array1 = array.clone();
        start = System.currentTimeMillis();
        bubbleSort1(array1);
        System.out.println(" 1耗时："+(System.currentTimeMillis()-start)+" ms,countInner:"+countInner1+",countOut:"+countOut1);
//        System.out.println("方案一： "+ JSONObject.toJSONString(array1));
        // 方案2
        int[] array2 = array.clone();
        start = System.currentTimeMillis();
        bubbleSort2(array2);
        System.out.println(" 2耗时："+(System.currentTimeMillis()-start)+" ms,countInner:"+countInner2+",countOut:"+countOut2);
//        System.out.println("方案二： "+ JSONObject.toJSONString(array2));
        // 方案3
        int[] array3 = array.clone();
        start = System.currentTimeMillis();
        bubbleSort3(array3);
        System.out.println(" 3耗时："+(System.currentTimeMillis()-start)+" ms,countInner:"+countInner3+",countOut:"+countOut3);
//        System.out.println("方案三： "+ JSONObject.toJSONString(array3));
        // 方案4
        int[] array4 = array.clone();
        start = System.currentTimeMillis();
        bubbleSort4(array4);
        System.out.println(" 4耗时："+(System.currentTimeMillis()-start)+" ms,countInner:"+countInner4+",countOut:"+countOut4);
//        System.out.println("方案四： "+ JSONObject.toJSONString(array4));
    }

    /**
     * @Description: 冒泡排序方案：每一个元素和后面每一个元素比较，大就换到后面去
     * @param array 数组
     * @return: void
     */
    private static void bubbleSort(int[] array) {
        int len = array.length;
        for(int i=0; i<len-1; i++){ // 遍历每一个元素
            for(int j=i+1; j<len; j++){ // 每一个元素跟后面的每一个数进行对比
                // 大就往后移
                if(array[i] > array[j]){
                    exchange(array,i,j);
                }
                countInner++;
            }
            countOut++;
        }
    }

    /**
     * @Description: 冒泡排序方案一:每两个相邻的元素一一比较，大的往后移
     * @param array 数组
     * @return: void
     */
    private static void bubbleSort1(int[] array) {
        int len = array.length;
        for(int i=0; i<len-1; i++){ // 遍历每一个元素
            for(int j=0; j<len-i-1; j++){ // 后面的每两个元素进行比较，大的往后移
                // 大的往后移
                if(array[j] > array[j+1]){
                    exchange(array,j,j+1);
                }
                countInner1++;
            }
            countOut1++;
        }
    }

    /**
     * @Description: 冒泡排序方案二：每两个相邻的元素一一比较，大的往后移，当没有出现移动时，说明已经是顺序，结束循环
     * @param array 数组
     * @return: void
     */
    private static void bubbleSort2(int[] array) {
        int len = array.length;
        boolean hasChange;
        for(int i=0; i<len-1; i++){ // 遍历每一个元素
            hasChange = false;
            for(int j=0; j<len-i-1; j++){ // 后面的数两两进行对比，后面顺序的数据不需要再比较
                // 大的往后移
                if(array[j] > array[j+1]){
                    exchange(array,j,j+1);
                    hasChange = true;
                }
                countInner2++;
            }
            if(!hasChange){ // 如果没有交换，说明是顺序，结束遍历
                break;
            }
            countOut2++;
        }
    }
    /**
     * @Description: 冒泡排序方案三：每两个相邻的元素一一比较，大的往后移，当后面一部分是顺序时，每次都不在跟后面的比较，只比较前半部分
     * @param array 数组
     * @return: void
     */
    private static void bubbleSort3(int[] array) {
        int len = array.length;
        boolean hasChange;
        int maxIndexStart = len - 1; // 初始最值的位置
        int maxIndex; // 移动过程中记录最大值的位置
        for(int i=0; i<len-1; i++){ // 遍历每一个元素
            hasChange = false;
            maxIndex = i;
            for(int j=0; j<maxIndexStart; j++){ // 后面的数两两进行对比，后面移好的数据不需要再比较
                // 大的往后移
                if(array[j] > array[j+1]){
                    exchange(array,j,j+1);
                    hasChange = true;
                    maxIndex = j;
                }
                countInner3++;
            }
            if(!hasChange){ // 如果没有交换，说明是顺序，结束遍历
                break;
            }
            maxIndexStart = maxIndex;
            countOut3++;
        }
    }
    /**
     * @Description: 冒泡排序方案四：每两个相邻的元素一一比较，前后同时循环，大的往后移，小的往前移，当前一部分(和后一部分)已经是顺序时，每次都不在跟前面（后面)的比较，只比较中间部分
     * @param array 数组
     * @return: void
     */
    private static void bubbleSort4(int[] array) {
        int len = array.length;
        boolean hasChange;
        int maxIndexStart = len - 1; // 初始最值的位置
        int maxIndex; // 移动过程中记录最大值的位置
        for(int i=0; i<len-1; i++){ // 遍历每一个元素
            hasChange = false;
            maxIndex = i;
            // 正向比较
            for(int j=0; j<maxIndexStart; j++){ // 后面的数两两进行对比，后面移好的数据不需要再比较
                // 大的往后移
                if(array[j] > array[j+1]){
                    exchange(array,j,j+1);
                    maxIndex = j;
                    hasChange = true;
                }
                countInner4++;
            }
            if(!hasChange){ // 如果没有交换，说明是顺序，结束遍历
                break;
            }
            maxIndexStart = maxIndex;
            for(int j=maxIndexStart; j>0; j--){
                if(array[j] < array[j-1]){
                    exchange(array,j-1,j);
                    hasChange = true;
                }
            }
            if(!hasChange){ // 如果没有交换，说明是顺序，结束遍历
                break;
            }
            countOut4++;
        }
    }
    /**
     * @Description: 数组两个位置上的数互换
     * @param array 数组
     * @param i 小的值下标
     * @param j 大的值小标
     * @return: void
     */
    private static void exchange(int[] array, int i, int j) {
        if(i == j){
            return;
        }
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

执行结果：

 0耗时：222 ms,countInner:49995000,countOut:9999
 1耗时：218 ms,countInner:49995000,countOut:9999
 2耗时：193 ms,countInner:49983675,countOut:9848
 3耗时：353 ms,countInner:48972670,countOut:9848
 4耗时：164 ms,countInner:20549226,countOut:2501

len = 10时，执行结果如下：
原数组： [6,5,6,2,1,2,0,7,8,9]
 0耗时：0 ms,countInner:45,countOut:9
方案零： [0,1,2,2,5,6,6,7,8,9]
 1耗时：0 ms,countInner:45,countOut:9
方案一： [0,1,2,2,5,6,6,7,8,9]
 2耗时：0 ms,countInner:42,countOut:6
方案二： [0,1,2,2,5,6,6,7,8,9]
 3耗时：0 ms,countInner:24,countOut:6
方案三： [0,1,2,2,5,6,6,7,8,9]
 4耗时：0 ms,countInner:21,countOut:3
方案四： [0,1,2,2,5,6,6,7,8,9]

最后

以上就是无聊蚂蚁为你收集整理的【排序】冒泡排序及优化的全部内容，希望文章能够帮你解决【排序】冒泡排序及优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。