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

转载请注明出处:[https://www.jianshu.com/p/df900e6ddbac

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

冒泡排序Bubble Sort

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

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

原理:

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

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

可能看到这,有的同学还不是很明白,那么我们假如,现在有这么几个数字 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;
                    }
                }
            }
        }
    }
}

算法系列:

选择排序

代码:

Java和Kotlin代码我均放在了GitHub上,欢迎Star!

GitHub地址:https://github.com/yang0range/MyAlgorithm

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券