冒泡排序算法（基于Java实现）

2020-12-14

字数统计: 1k字 | 阅读时长≈ 4分

冒泡排序算法（基于Java实现）

冒泡算法原理及代码实现：

一、冒泡算法的原理

冒泡算法只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。这样一来，一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

例如，我们要对一组数据4，5，6，3，2，1从小到大进行排序。第一次的冒泡操作的详细过程就是这样：

可以看出，经过一次冒泡操作之后，6个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行6次这样的冒泡操作就行了。

实际上，上述的冒泡过程是可以优化的。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。再比如下面这个例子，这里面给6个元素排序，只需要4次冒泡操作就行了。

二、冒泡排序算法的代码实现

package com.company;

import java.util.Arrays;

public class BubbleSort {

    //冒泡算法，a表示需要排序的数组
    public static int[] bubbleSort(int[] a){
       int len = a.length;
       if(len == 0 || len == 1){
           return a;
       }

        for(int i=0; i<len; i++){
            for(int j = 0; j < len-i-1; ++j){
                if(a[j] > a[j+1]){
                    //交换
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
        return a;
    }

    public static void main(String[] args) {
        int[] a = new int[]{3,5, 4, 1, 2, 6};
        for(int i=0; i<a.length; i++){
            System.out.println(a[i]);
        }

        BubbleSort b = new BubbleSort();
        b.bubbleSort(a);
        for(int i=0; i<a.length; i++){
            System.out.println(a[i]);
        }
        System.out.println(Arrays.toString(a));
    }
}

输出的结果：

3
5
4
1
2
6
1
2
3
4
5
6
[1, 2, 3, 4, 5, 6]

改进的冒泡算法代码：

package Sort;

import java.util.Arrays;

public class BubbleSort {

    //冒泡算法，a表示需要排序的数组
    public static int[] bubbleSort(int[] a){
       int len = a.length;

       boolean flag = false;
        for(int i=0; i<len-1; i++){
            for(int j = 0; j < len-i-1; ++j){
                if(a[j] > a[j+1]){
                    //交换
                    flag = true;
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
            System.out.println("第"+(i+1)+"趟排序后的数组");
            System.out.println(Arrays.toString(a));
            if(!flag){
                break;
            }else{
                flag = false;
            }
        }
        return a;
    }

    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 7, 6};
//        for(int i=0; i<a.length; i++){
//            System.out.println(a[i]);
//        }

        BubbleSort b = new BubbleSort();
        b.bubbleSort(a);
//        for(int i=0; i<a.length; i++){
//            System.out.println(a[i]);
//        }
        System.out.println(Arrays.toString(a));
    }
}

输出的结果为：

第1趟排序后的数组
[1, 2, 3, 6, 7]
第2趟排序后的数组
[1, 2, 3, 6, 7]
[1, 2, 3, 6, 7]

冒泡的过程只涉及到相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)**，是一个原地排序算法**；

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡算法是稳定的排序算法；

冒泡算法的时间复杂度是多少呢？

在最好的情况下，要排序的数据已经有序了，我们只需要进行一次冒泡操作，就可以结束了，所以最好的情况时间复杂复杂度是O(n)。而最坏的情况是，要排序的数据刚好是逆序排列的，则我们需要进行n次的冒泡操作，所以最坏的时间复杂度为O(n^2) 。根据平均复杂度分析，所以冒泡算法的时间复杂度为O(n^2) 。

本文作者： feng之锋
本文链接： http://example.com/2020/12/14/冒泡排序算法/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！