数据结构与算法 冒泡排序

起因：冒泡排序，之前看听极客上面的课有听过，之前总会觉得算法会很高深莫测，其实也是我们平常也有在用，起了一些比较高大上的名字，比如说容器，缓存，大多也是维护了一个map，或者list 存储相关内容；学习并使用他，不仅仅是在面试有用（一部分），更多的是自我的提高吧。

---

1 冒泡排序

冒泡排序的定义：
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2 冒泡排序 概述

冒泡排序算法的原理如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

算法稳定性:

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。
所以，如果两个元素相等，是不会再交换的；
如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，
所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

算法复杂度:

最佳情况：T(n) = O(n)
最差情况：T(n) = O(n2)
平均情况：T(n) = O(n2)

动图演示:

2 冒泡排序 代码实现

package com.algorithm;

import java.util.Arrays;

/**
 * @ClassName BubbleSort
 * @Description TODO
 * @Author dylan
 * @Date 2020/11/20 13:54
 * @Version 1.0
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        // 只需要修改成对应的方法名就可以了
        bubbleSort(array);

        System.out.println(Arrays.toString(array));
    }

    /**
     * Description:冒泡排序
     *
     * @param array 需要排序的数组
     * @author dylan
     * @date 2019/7/11 9:54
     */
    public static void bubbleSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int length = array.length;

        // 外层循环控制比较轮数i
        for (int i = 0; i < length; i++) {
            // 内层循环控制每一轮比较次数，每进行一轮排序都会找出一个较大值
            // (array.length - 1)防止索引越界，(array.length - 1 - i)减少比较次数
            for (int j = 0; j < length - 1 - i; j++) {
                // 前面的数大于后面的数就进行交换
                if (array[j] > array[j + 1]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }

    }

}

---

不要以为每天把功能完成了就行了，这种思想是要不得的，互勉~！