Java冒泡排序的细致引见（代码示例）【JAVA教程】,数据结构和算法,java

本篇文章给人人带来的内容是关于Java冒泡排序的细致引见（代码示例），有肯定的参考价值，有须要的朋侪可以参考一下，愿望对你有所协助。

1、导言

由于这是排序算法系列的第一篇文章，所以多烦琐几句。

排序是很罕见的算法之一，如今许多编程言语都集成了一些排序算法，比方Java 的Arrays.sort()要领，这类体式格局让我们可以不在乎内部完成细节而直接挪用，在现实的软件开发当中也会常常使用到。然则站在开发者的角度而言，知其然必须知其所以然。多练练排序算法，不仅可以让我们晓得一些排序要领的底层完成细节，更可以磨炼我们的头脑，提拔编程才。如今许多手艺口试也会涉及到基础的排序算法，所以多演习是有优点的。（引荐：Java视频教程）

文中涉及到的代码都是Java完成的，然则不会涉及到太多的Java言语特征，而且我会加上细致的解释，协助你邃晓代码而且转换成你熟习的编程言语。

罕见的排序算法有以下10种：

冒泡排序、挑选排序、插入排序，均匀时刻复杂度都是O(n²)
希尔排序、合并排序、疾速排序、堆排序，均匀时刻复杂度都是O(nlogn)
计数排序、基数排序、桶排序，均匀时刻复杂度都是O(n + k)

在最先详细的排序算法解说之前，先得邃晓两个观点：

原地排序：指的是在排序的历程当中不会占用分外的存储空间，空间复杂度为O(1)。
排序算法的稳固性：一个稳固的排序，指的是在排序以后，雷同元素的前后递次不会被转变，反之就称为不稳固。举个例子：一个数组 [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]，第一次冒泡的操纵如下图所示：

反复举行这个操纵，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;
        }
    }
}

好了，冒泡排序的基础思绪和代码都已完成，末了总结一下：