十大排序算法 -- 冒泡排序

阿粤Ayue

关注

发布于: 25 分钟前

冒泡排序

从数组头开始，比较相邻的元素。如果第一个比第二个大(小)，就交换它们两个
对每一对相邻元素作同样的工作，从开始第一对到尾部的最后一对，这样在最后的元素应该会是最大(小)的数
重复步骤 1~2，重复次数等于数组的长度，直到排序完成

代码实现

对下面数组实现排序：{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}

动图演示

代码实现

public class BubbleSort {
    public static final int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};
    public static void main(String[] args) {        print(ARRAY);        System.out.println("============================================");        print(sort(ARRAY));    }
    public static int[] sort(int[] array) {        if (array.length == 0) {            return array;        }        for (int i = 0; i < array.length; i++) {            //array.length - 1 -i 已经冒泡到合适位置无需在进行排序，减少比较次数            for (int j = 0; j < array.length - 1 -i; j++) {                //前面的数大于后面的数交换                if (array[j + 1] < array[j]) {                    int temp = array[j + 1];                    array[j + 1] = array[j];                    array[j] = temp;                }            }        }        return array;    }
    public static void print(int[] array) {        for (int i : array) {            System.out.print(i + "  ");        }        System.out.println("");    }}

复制代码

时间复杂度

对于上面 12 个数据项，从第一个元素开始，第一趟比较了 11 次，第二趟比较了 10 次，依次类推，一直到最后一趟，就是：

11 + 10 + 9 + 8 + 7 + 6 + 5  + 4 + 3  + 2 + 1  =  66次

复制代码

若有 n 个元素，则第一趟比较为(n-1)次，第二趟比较为(n-2)次，依次类推：

(n-1) + (n-2) + (n-3) + ...+ 2 + 1 = n * (n-1)/2

复制代码

在大 O 表示法中，去掉常数系数和低阶项，该排序方式的时间复杂度为：O(n<sup>2</sup>)

算法稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。——百度百科

在代码中可以看到，array[j + 1] = array[j]的时候，我们可以不移动array[i]和array[j]，所以冒泡排序是稳定的。

发布于: 25 分钟前阅读数: 4

原文链接:【http://xie.infoq.cn/article/90e9009be722932b808740c8a】。文章转载请联系作者。

阿粤Ayue

关注

微信搜：Javatv 2019.10.16 加入

秘密基地：javatv.net

发布

暂无评论

创作场景

十大排序算法 -- 冒泡排序

冒泡排序

代码实现

时间复杂度

算法稳定性

阿粤Ayue

评论