算法--冒泡排序

1、概述

冒泡排序思想：对一组乱序的数据，从前向后依次比较相邻的俩个元素的值，如果前一个值大于后一个值就交换位置，最后就会将最大的值放到末尾；然后再从前向后开始进行第二轮的比较，将第二大的值排在倒数第二位。就这样循环下去，就会得到一组有序的数据。

2、图解示例

观察可得：

1. 对数组排序需要进行 length - 1 轮遍历。
2. 每轮遍历中的数据比较都在依次减少。
3. 优化，当发现某一轮遍历中没有进行数据交换，即表示已经排好序，可以直接结束冒泡排序。

3、代码

package com.ld.algorithm.sort;

import java.util.Arrays;

/**
 * @author ld
 * @date 2020/8/5 16:26
 *
 * 排序算法--冒泡排序
 *
 * 冒泡排序思想：
 * 对一组乱序的数据，从前向后依次比较相邻的俩个元素的值，如果前一个值大于后一个值就交换位置，最后就会将最大的值放到末尾；
 * 然后再从前向后开始进行第二轮的比较，将第二大的值排在倒数第二位。
 * 就这样循环下去，就会得到一组有序的数据。
 */
public class BubbleSort {

    public static void main(String[] args){
        //测试数据
        int[] array = {4,1,7,-3};

        System.out.println("排序前的数据：" + Arrays.toString(array));

        //进行冒泡排序
        int[] sortArray = sort(array);

        System.out.println("排序后的数据：" + Arrays.toString(sortArray));
}

    /**
     * 进行冒泡排序
     * @param array 要被排序的数据
     * @return 返回排序后有序的数据
     */
    public static int[] sort(int[] array){

        //临时变量，用于交换数据时使用
        int temp = 0;
        //用于优化冒泡排序，即如果一轮遍历中，没有进行交换，说明已经排好序
        boolean flag = false;

        //本层循环表示要对array进行多少轮遍历
        for(int i = 0;i < array.length - 1;i++) {
            //本层循环用于两两比较
            for (int j = 0; j < array.length - 1 - i; j++) {
                //判断前一个值是否大于后一个值,如果大于就交换
                if (array[j] > array[j + 1]) {
                    //如果进行了交换，就设置为true
                    flag = true;
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }

            //判断一轮遍历后，是否进行了交换
            if(!flag){
                //未交换，直接跳出循环
                break;
            }else{
                //重置
                flag = false;
            }
        }
        return array;
    }
}