Rumah >Java >javaTutorial >Java冒泡排序的详细介绍(代码示例)

Java冒泡排序的详细介绍(代码示例)

不言
不言ke hadapan
2019-03-19 10:10:583626semak imbas

本篇文章给大家带来的内容是关于Java冒泡排序的详细介绍(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

1、 导言

因为这是排序算法系列的第一篇文章,所以多啰嗦几句。

排序是很常见的算法之一,现在很多编程语言都集成了一些排序算法,比如Java 的Arrays.sort()方法,这种方式让我们可以不在乎内部实现细节而直接调用,在实际的软件开发当中也会经常使用到。但是站在开发者的角度而言,知其然必须知其所以然。多练练排序算法,不仅能够让我们知道一些排序方法的底层实现细节,更能够锻炼我们的思维,提升编程能力。现在很多技术面试也会涉及到基本的排序算法,所以多练习是有好处的。(推荐:Java视频教程

文中涉及到的代码都是Java实现的,但是不会涉及到太多的Java语言特性,并且我会加上详细的注释,帮助你理解代码并且转换成你熟悉的编程语言。

常见的排序算法有以下10种:

  • 冒泡排序、选择排序、插入排序,平均时间复杂度都是O(n2)
  • 希尔排序、归并排序、快速排序、堆排序,平均时间复杂度都是O(nlogn)
  • 计数排序、基数排序、桶排序,平均时间复杂度都是O(n + k)

在开始具体的排序算法讲解之前,先得明白两个概念:

  1. 原地排序:指的是在排序的过程当中不会占用额外的存储空间,空间复杂度为O(1)。
  2. 排序算法的稳定性:一个稳定的排序,指的是在排序之后,相同元素的前后顺序不会被改变,反之就称为不稳定。举个例子:一个数组 [3,5,1,4,9,6,6,12] 有两个6(为了区分,我把其中一个 6 加粗),如果排序之后是这样的:[1,3,4,5,6,6,9,12](加粗的 6 仍然在前面),就说明这是一个稳定的排序算法。
2. 言归正传

冒泡排序的思路其实很简单,一个数据跟它相邻的数据进行大小的比较,如果满足大小关系,就将这两个数据交换位置。一直重复这个操作,就能将数据排序。

举个例子,假如有数组 a[3,5,1,4,9,6],第一次冒泡的操作如下图所示:

1345100190-5c8f40d24f1de_articlex.png

重复进行这个操作,6次冒泡之后,数据排序完成。

根据这个思路,应该能很容易能够写出下面的代码实现冒泡排序:

public class BubbleSort {

    //data表示整型数组,n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1,无须排序
        if (n <= 1) return;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                //如果data[j] > data[j + 1],交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

但是这个排序算法还可以进行优化,当冒泡操作已经没有数据交换的时候,说明排序已经完成,就不用在进行冒泡操作了。例如上面的例子,第一次冒泡之后,数据为 [3,1,4,5,6,9],再进行一次冒泡,数据变为 [1,3,4,5,6,9],此时已经完成了排序,就可以结束循环了。

所以针对这个数组的排序,上面的代码需要6次冒泡才能完成,其中有4次都是不需要的。所以可以对代码进行优化:

public class BubbleSort {

    //优化后的冒泡排序
    //data表示整型数组,n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1,无须排序,返回空
        if (n <= 1) return;
        for (int i = 0; i < n; i++) {
            boolean flag = false;//判断是否有数据交换

            for (int j = 0; j < n - i - 1; j++) {
                //如果data[j] > data[j + 1],交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;

                    flag = true;//表示有数据交换
                }
            }
            //如果没有数据交换,则直接退出循环
            if (!flag) break;
        }
    }
}

好了,冒泡排序的基本思路和代码都已经实现,最后总结一下:

  1. 冒泡排序是基于数据比较的
  2. 最好情况时间复杂度是O(n),最坏情况时间复杂度是O(n2),平均时间复杂度是O(n2)
  3. 冒泡排序是原地排序算法,并且是稳定的。



Atas ialah kandungan terperinci Java冒泡排序的详细介绍(代码示例). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Artikel ini dikembalikan pada:segmentfault.com. Jika ada pelanggaran, sila hubungi admin@php.cn Padam