目录

冒泡排序

基本介绍

依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。

排序思想

  1. 外层循环需要进行n-1次
  2. 内层循环次数逐渐减少,假设进行到第i次,则本轮内层循环次数就是n-1-i
  3. 如果某躺排序中没有发生交换说明已经排序完毕

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package com.eh.ftd.dsa.ds.impl;

import java.util.Arrays;
import java.util.Random;

/**
 * 冒泡排序
 *
 * @author David Li
 * @create 2020/06/19 09:57
 */
public class Sort {

    public static void bubbleSort(int[] arr) {
        int temp; // 临时变量用作交换
        // 对n个数进行排序,外层循环需要n-1次
        for (int i = 0; i < arr.length - 1; i++) {
            // 如果本轮没有交换则说明已经排序完毕
            boolean flag = true;
            // 内层循环需要n-1-i次
            for (int j = 0; j < arr.length - 1 - i; j++) {
                // 相邻两个数比较,大的交换的后面
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    // 说明本轮有排序
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[10];
        Random random = new Random();
        for (int i = 0; i < arr.length - 1; i++) {
            arr[i] = random.nextInt(10);
        }
        Sort.bubbleSort(arr);
        Arrays.stream(arr).forEach(x -> System.out.printf("%d\t", x));
    }
}

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200619105232.png