Java常见排序算法详解——冒泡排序

Demo_Yang

发布于 2019-04-18 15:45:09

6690

发布于 2019-04-18 15:45:09

文章被收录于专栏：yang0rangeyang0range

转载请注明出处：[https://cloud.tencent.com/developer/article/1415066

我们在面试的时候时常会问到我们算法题，而算法题当中排序算法题是问到最多的。应广大同学的建议，我特意整理了一下Java常见的排序算法，我尽量从概念，原理，代码这几方面详细阐述旨在让大家知道、理解、应用。

冒泡排序Bubble Sort

概念：冒泡排序是一种交换排序，它的基本思想是：

两两比较相邻记录，如果反序则交换，直到没有反序的记录为止。

原理：

例如我们有一个数组，我们如果需要把较大的元素排在前面，把小的元素排在后面，那么需要从尾部到头开始比较操作：

从尾部开始比较相邻的两个元素，如果尾部的元素比前面的大，就交换两个元素的位置。
往前对每个相邻的元素都做这样的比较、交换操作，这样到数组头部时，第 1 个元素会成为最大的元素。
重新从尾部开始第 1、2 步的操作，除了在这之前头部已经排好的元素。
继续对越来越少的数据进行比较、交换操作，直到没有可比较的数据为止，排序完成。

可能看到这，有的同学还不是很明白，那么我们假如，现在有这么几个数字 11 10 5 7 4 29 这么几个数字运用冒泡排序从大到小排序。

我们可以看到目前，我们的数组起始状态如下：

位置	数字
0	11
1	10
2	5
3	7
4	4
5	29

29和4比较，29比4大，那么29和4进行交换

那么交换之后，数组状态如下：

位置	数字
0	11
1	10
2	5
3	7
4	29
5	4

29和7比较，29比7大，那么29和7进行交换

那么交换之后，数组状态如下：

位置	数字
0	11
1	10
2	5
3	29
4	7
5	4

29和5比较，29比5大，那么29和5进行交换

那么交换之后，数组状态如下：

位置	数字
0	11
1	10
2	29
3	5
4	7
5	4

29和10比较，29比10大，那么29和10进行交换

那么交换之后，数组状态如下：

位置	数字
0	11
1	29
2	10
3	5
4	7
5	4

29和11比较，29比11大，那么29和11进行交换

那么交换之后，数组状态如下：

位置	数字
0	29
1	11
2	10
3	5
4	7
5	4

我们可以看到，经过第一趟的排序之后。我们已经找到了最大的元素，并且把最大的数字29排到了0位置，这个表象就像水气泡从水底冒上来一样，所以形象的成为“冒泡排序”

接下来，我们再看看第二趟数组是怎么变化的

第二趟初始化的数组

位置	数字
0	29
1	11
2	10
3	5
4	7
5	4

4和7比较，4没有7大，那么不变

7和5比较，7比5大，那么7和5进行交换

位置	数字
0	29
1	11
2	10
3	7
4	5
5	4

7和10比较，7没有10大，那么不变

10和11比较，10没有11大，那么不变

那么经过第二趟结束之后，数组最后为

位置	数字
0	29
1	11
2	10
3	7
4	5
5	4

我们可以看到经过两趟之后，我们的数组就按照我们的要求从大到小排好了。

因此，假如有N个元素，最好的情况我们仅仅需要N-1次比较和交换，最坏的情况下需要N（N-1）/2次比较和交换才能完成。

代码实现：

Java实现

/**
 * @author yangzc
 * @data 2019/4/8 22:21
 * @desc 冒泡排序
 */
public class BubbleSort {
    private int[] array;

    public BubbleSort(int[] array) {
        this.array = array;
    }

    /**
     * 从小到大
     */
    public void sort() {
        int length = array.length;
        if (length > 0) {
            for (int i = 1; i < length; i++) {
                for (int j = 0; j < length - i; j++) {
                    if (array[j] > array[j + 1]) {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
        }
    }

    /**
     * 从大到小
     */
    public void sort2() {
        int length = array.length;
        if (length > 0) {
            for (int i = length - 1; i > 0; i--) {
                for (int j = length - 1; j > length - 1 - i; j--) {
                    if (array[j] > array[j - 1]) {
                        int temp = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = temp;
                    }
                }
            }
        }
    }
}