Algorithm Bubble Sort

algorithm

Bubblesort is an elementary sorting algorithm. The idea is to imagine bubbling the smallest elements of a (vertical) array to the top; then bubble the next smallest; then so on until the entire array is sorted. Bubble sort is worse than both insertion sort and selection sort. It moves elements as many times as insertion sort (bad) and it takes as long as selection sort (bad). On the positive side, bubble sort is easy to understand. Also there are highly improved variants of bubble sort.

前言

    冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

冒泡排序介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

冒泡排序解析：


冒泡排序动图：


冒泡排序代码

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
/**
 * @Auther: Arsenal
 * @Date: 2020-03-16 22:06
 * @Description: 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        //int[] arr = {3, 9, -1, 10, -2};
        //int[] arr = {1, 3, 5, 7, 9};
        //System.out.println("原始的数组:" + Arrays.toString(arr));

        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        long start = System.currentTimeMillis();
        bubbleSort(arr);//11286毫米
        long end = System.currentTimeMillis();
        System.out.println("80000个数字排序所用时间:" + (end - start));
    }

    /**
     * 冒泡排序
     * @param arr 数组
     */
    public static void bubbleSort(int[] arr) {
        int temp = 0;
        for (int i = 0; i < arr.length - 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;
                }
            }
            //System.out.println("第" + (i + 1) + "趟排序后的数组:");
            //System.out.println(Arrays.toString(arr));
        }
    }
}

冒泡排序优化

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
47
48
/**
 * @Auther: Arsenal
 * @Date: 2020-03-16 22:06
 * @Description: 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        //int[] arr = {3, 9, -1, 10, -2};
        //int[] arr = {1, 3, 5, 7, 9};
        //System.out.println("原始的数组:" + Arrays.toString(arr));

        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        long start = System.currentTimeMillis();
        optimizeBubbleSort(arr); //10955毫米
        long end = System.currentTimeMillis();
        System.out.println("80000个数字排序所用时间:" + (end - start));
    }

    /**
     * 优化后的冒泡排序
     * @param arr 数组
     */
    public static void optimizeBubbleSort(int[] arr) {
        int temp = 0;
        boolean flag = false; //判断是否交换过的表示
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }

            }
            if (!flag) { //一趟排序过程中，一次交换都没发生过
                break;
            } else {
                flag = false;
            }
            //System.out.println("第" + (i + 1) + "趟排序后的数组:");
            //System.out.println(Arrays.toString(arr));
        }
    }
}

延伸

    冒泡排序
    排序-冒泡排序
    冒泡排序及优化详解
    Bubble Sort In Python
    韩顺平数据结构和算法

Article Title:Algorithm Bubble Sort

Article Author:Funing Ma

Release Time:2020-03-16 18:58:18

Last Update:2020-03-30 10:12:39

Original Link:https://mafuning.github.io/2020/03/16/2020-03-16-Algorithm-Bubble-Sort/

License Agreement: "CC-BY-SA-4.0"

Content
  1. 1. 前言
  2. 2. 冒泡排序介绍
    1. 2.1. 冒泡排序代码
    2. 2.2. 冒泡排序优化
  3. 3. 延伸