冒泡排序(简述)

老师说，学习不能急躁。学习排序的整体章节在后面有，这儿只是个简单介绍。

排序是什么

排序是将多个数据，依指定的顺序进行排列的过程。

排序的分类:

1.内部排序:

指将需要处理的所有数据都加载到内部存储器中进行排序。包括(交换式排序法、选择式排序法和插入式排序法);

2.外部排序法:

数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。包括(合并排序法和直接合并排序法)。

冒泡排序

冒泡排序很简单，给你一个数组，你需要将它以从小到大的顺序排序，这时候就可以使用冒泡排序了。

目前，为从左到右进行比较，左边大的数字与右边小的数字交换位置，直到无法交换为止。

// 数组的大小：
int[] a = {45,24,69,80,57,13};

接下来，对整个排序进行模拟：

第1次排序
    交换第1次 {24,45,69,80,57,13}; => 24和15进行交换
    交换第2次 {24,45,69,80,57,13}; => 45<69,不交换
    交换第3次 {24,45,69,80,57,13}; => 69<80,不交换
    交换第4次 {24,45,69,57,80,13}; => 80和57进行交换
    交换第5次 {24,45,69,57,13,80}; => 13和80进行交换
第2次排序
    交换第1次 {24,45,69,57,13,80};
    交换第2次 {24,45,69,57,13,80};
    交换第3次 {24,45,57,69,13,80};
    交换第4次 {24,45,57,13,69,80};
第3次排序
    交换第1次 {24,45,57,13,69,80};
    交换第2次 {24,45,57,13,69,80};
    交换第3次 {24,45,13,57,69,80};
第4次排序
    交换第1次 {24,45,13,57,69,80};
    交换第2次 {24,13,45,57,69,80};
第5次排序
    交换第1次 {13,24,45,57,69,80};

相信细心的人已经瞧见规律了，下面就简单的总结下：

规律1 外层排序次数最多有5层，相当于：6-1=5(6为数组的大小)
规律2 内层交换的次数最大有5次，也是相当于6-1=5，不过略有不同：
    第1次排序  6-1=5次 
    第2次排序  6-2=4次 
    第3次排序  6-3=3次 
    第4次排序  6-4=2次 
    第5次排序  6-5=1次  =>这么明显的for循环……
    ==> 整体上外层依次递增，内层依次递减
规律3 递减和递增的范围都不会超出[1,数组大小/数组长度-1]。
规律4 每一次外循环确定一个最大数，导致每次内层循环的次数减少。
规律5 前面大于后面则两数交换。

最终的冒排序Java版本代码如下：

public class BubbleSort{
    public static void main(String[] args) {
        // 目的：实现冒泡排序算法，为了效果，写个数组进行排序
        int[] arr = {557,45,24,69,80,57,13,-333,451,-90,8741,9999};
        System.out.println("the length:"+arr.length);
        // 外循环，[1,5)
        for (int i=1;i<arr.length;i++ ) {
            // 交换印记：负责记录是否交换
            int flag = 0;
            // 内循环，[1,5-i+1)
            for (int j=1;j<arr.length-i+1 ;j++ ) {
                if (arr[j-1]>arr[j]) {
                    int num = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = num;
                    flag += 1;
                }
            }
            System.out.print("\r\n");
            for (int ix=0;ix<arr.length ;ix++ ) {
            System.out.print(arr[ix]+" ");
            }
            System.out.print("\t "+i+"\r\n");
            // 如果交换印记生效，证明交换已经停止，退出当前循环。
            if (flag<=0) {
                break;
            }
        }

        System.out.println("输出最终冒泡排序结果:");
        for (int i=0;i<arr.length ;i++ ) {
            System.out.print(arr[i]+" ");
        }
    }
}