Java基础算法–冒泡排序

时间:2020-9-8 作者:admin


冒泡排序(Bubble Sort)

1. 算法介绍

  1. 对原数组的各个数据,依次比较相邻数的大小。
  2. 如果前面的数大于(小于)后面的数,经过一轮排序便将最大(最小)的数。
  3. 循环1 – 2,步,总共需要循环数组长度减一次(每次循环都固定了最大数或者最小数的位置)。

2. 举例演示

原数组: [117, 101, 106, 155, 112]

第一次排序后:[101, 106, 117, 112, 155]

第二次排序后:[101, 106, 112, 117, 155] 已经排好序

第三次排序后:[101, 106, 112, 117, 155]

第四次排序后:[101, 106, 112, 117, 155]

3. 第一次排序图解

Java基础算法--冒泡排序

4. 代码实现(待优化)

package sort;

import java.util.Arrays;

/**
 * <p>
 *
 * </p>
 *
 * @author: D
 * @since: 2020/9/7
 * @version: 1
 */
public class BubbleSortDemo {

    public static void main(String[] args) {
        int[] arr = {117, 101, 106, 155, 112};
        bubbleSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
    }

    private static void bubbleSort(int[] arr) {
        int temp;
        for (int i = 1; i < arr.length; i++) {
            flag = false;
            for (int j = 0; j < arr.length - i; j++) {
                // 将较大的数放到后面
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            System.out.println("第" + i + "次排序后");
            System.out.println(Arrays.toString(arr));
        }
    }
}

5. 优化思路

在上面的举例演示中在第二次排序其实已经是排好序的了,但是根据冒泡排序会执行 arr.length - 1次,这里可以设置一个判断boolean flag;在没有进行一次交换的时候就认为已经排好序了,直接退出。

6. 优化代码

package sort;

import java.util.Arrays;

/**
 * <p>
 *
 * </p>
 *
 * @author: D
 * @since: 2020/9/7
 * @version: 1
 */
public class BubbleSortDemo {

    public static void main(String[] args) {
        int[] arr = {117, 101, 106, 155, 112};
        bubbleSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
    }

    private static void bubbleSort(int[] arr) {
        int temp;
        boolean flag;
        for (int i = 1; i < arr.length; i++) {
            flag = false;
            for (int j = 0; j < arr.length - i; j++) {
                // 将较大的数放到后面
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
            System.out.println("第" + i + "次排序后");
            System.out.println(Arrays.toString(arr));
        }
    }
}

7. 运行结果

未优化执行结果:

Java基础算法--冒泡排序

优化后执行结果:

Java基础算法--冒泡排序

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。