package com.wang.sort;


/**
 * 冒泡排序
 * 注意数组位置从0开始。
 * 外层循环从0开始，内存循环从1开始，内层两两元素相比较，
 * 内层循环一轮，总是能把最大或者最小元素排到最后，以此实现冒泡。
 * 冒泡排序：记得一个最重要的点，就是总是把最大的数据元素或者最小的数据元素放在最后面。这样，如果进行优化的时候，我们可以将后面看做已经排好序的，然后指针往前移动，继续比较未排序的。
 * @author wxe
 * @since 0.0.1
 */
public class BubbleSort {
    public static int count = 0;
    
    public static void main(String[] args){
        int[] array = {2,3,7,3,9,4,5};
        sort(array, array.length);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ",");
        }
        System.out.println();
        System.out.println("总的排序次数" + count);
    }

    public static void sort(int[] array,int length){
        for (int i = 0; i < length-1; i++) {
            for (int j = 1; j < length; j++) {
                if (array[j-1]>array[j]) {
                    int temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                }
                count++;
            }
        }
    }
    /**
     * 优化后的排序算法
     * 有一个疑问：就是为什么k是从最后面往前面移动呢？这里主要是因为冒泡排序的思想就是把最大或者最小元素往最后面放。后面相当于是有顺序的元素集合。继续排序的时候只管前面数据顺序即可。
     * @param array
     * @param length
     */
    public static void anotherSort(int[] array,int length){
        boolean flag = true;
        int k = length;
        while (flag) {
            flag = false;
            //如果循环遍历数组，发现数组进行了交换，则表示这趟循环比较还需要进行。如果这一趟循环已经不需要比较，则说明排序结束
            for (int i = 1; i < k; i++) {
                if (array[i-1] > array[i]) {
                    int temp = array[i-1];
                    array[i-1] = array[i];
                    array[i] = temp;
                    flag = true;
                }
                count++;
            }
            k--;
        }
    }
}

根据第一种冒泡排序思路和第二种冒泡排序思路，可以看到对于相同的数据实例，第一种冒泡排序思路进行了36次循环，而第二种冒泡排序思路进行了15次循环。

冒泡排序的时间效率为：O（n²）,所以对于数据规模较小时，可以使用。不适应数据规模较大的排序。