package cn.ljm.arrays;

import java.util.Arrays;

/**
 * 测试冒泡排序及其优化
 * @author LJM
 *
 */
public class TestBubbleSort {

    public static void main(String[] args) {
        int [] values = {3, 1, 6, 2, 9, 0, 7, 4, 5, 8};
        int cnt1 = bubbleSort(values);
        int cnt2 = improvedBubbleSort(values);
        System.out.println("未改进的冒泡排序比较次数为：" + cnt1);
        System.out.println("改进后的冒泡排序比较次数为：" + cnt2);
    }

    //未改进的冒泡排序
    public static int bubbleSort(int values[]) {
        //array数组暂存values数组中的值
        int array[] = new int [10];
        System.arraycopy(values, 0, array, 0, values.length);

        int cnt = 0;
//      System.out.println("==========未改进的冒泡排序==========");
        for(int i = 0; i < values.length - 1; i ++) {
            for(int j = 0; j < values.length - 1; j ++) {
                if(values[j] > values[j + 1]) {
                    cnt ++;
                    int temp = values[j];
                    values[j] = values[j + 1];
                    values[j + 1] = temp;
                }
//              System.out.println("当前比较次数为：" + cnt);
//              System.out.println(Arrays.toString(values));
            }
        }
        //恢复values数组中的值
        System.arraycopy(array, 0, values, 0, values.length);

        return cnt;
    }

    //改进后的冒泡排序
    public static int improvedBubbleSort(int values[]) {
        int cnt = 0;
//      System.out.println("==========改进后的冒泡排序==========");
        for(int i = 0; i < values.length - 1; i ++) {
            boolean flag = true;
            for(int j = 0; j < values.length - 1; j ++) {
                if(values[j] > values[j + 1]) {
                    cnt ++;
                    int temp = values[j];
                    values[j] = values[j + 1];
                    values[j + 1] = temp;
                    flag = false;
                }
                if(flag) break;
//              System.out.println("当前比较次数为：" + cnt);
//              System.out.println(Arrays.toString(values));
            }
        }
        return cnt;
    }

}