package com.diyo.sort;

import java.text.SimpleDateFormat;

import java.util.Arrays;

import java.util.Date;

/**

 * BubbleSort冒泡排序 时间复杂度O(n^2)

 *

 * @author DengZY

 *

 */

public class BubbleSort {

    public static void main(String[] args) {

        int arr[] = { 3, 9, -1, 10, -2 };

        // 测试冒牌排序的速度O(n^2),给80000个数据测试

//        int[] arr2 = new int[80000];

//        for (int i = 0; i < 80000; i++) {

//            arr2[i] = (int) (Math.random() * 999999); // 生成一个[0,999999)的数

//        }

//        Date date1 = new Date();

//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

//        String date1Str = simpleDateFormat.format(date1);

//        System.out.println("排序前的时间是="+date1Str);

        System.out.println("-----排序前-----");

        System.out.println(Arrays.toString(arr));

        System.out.println("-----开始排序-----");

        bubbleSort(arr);

        System.out.println("-----结束排序-----");

        System.out.println("-----排序后-----");

        System.out.println(Arrays.toString(arr));

//        Date date2 = new Date();

//        String date2Str =simpleDateFormat.format(date2);

//        System.out.println("排序后的时间是="+date2Str);

        /*

         * // 第一趟排序，将第一大的数排在倒数第一位 
　　　　　　for (int j = 0; j < arr.length - 1 - 0; j++) { //如果前面的数比后面的数大，则交换 
　　　　　　　　if (arr[j] > arr[j + 1]) { 
　　　　　　　　　　temp = arr[j]; 
　　　　　　　　　　arr[j] = arr[j +1];
　　　　　　　　　　 arr[j + 1] = temp; 
　　　　　　　　} 
　　　　　　} 
　　　　　　System.out.println("第一趟排序后的数组");

          System.out.println(Arrays.toString(arr));

         *

         * // 第二趟排序，将第二大的数排在倒数第二位 for (int j = 0; j < arr.length - 1 - 1; j++) { //

         * 如果前面的数比后面的数大，则交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j +

         * 1]; arr[j + 1] = temp; } } System.out.println("第二趟排序后的数组");

         * System.out.println(Arrays.toString(arr));

         *

         * // 第三趟排序，将第三大的数排在倒数第三位 for (int j = 0; j < arr.length - 1 - 2; j++) { //

         * 如果前面的数比后面的数大，则交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j +

         * 1]; arr[j + 1] = temp; } } System.out.println("第三趟排序后的数组");

         * System.out.println(Arrays.toString(arr));

         *

         * // 第四趟排序，将第四大的数排在倒数第四位 for (int j = 0; j < arr.length - 1 - 3; j++) { //

         * 如果前面的数比后面的数大，则交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j +

         * 1]; arr[j + 1] = temp; } } System.out.println("第四趟排序后的数组");

         * System.out.println(Arrays.toString(arr));

         */

    }

    // 冒泡排序

    public static void bubbleSort(int[] arr) {

        int temp = 0; // 临时变量，用于交换

        boolean flag = false; // 标识变量，表示是否进行过交换,用于减少重复排序次数

        for (int i = 0; i < arr.length - 1; i++) {

            // 第(i+1)趟排序，将最大的数排在最后

            for (int j = 0; j < arr.length - 1 - i; j++) {

                // 如果前面的数比后面的数大，则交换

                if (arr[j] > arr[j + 1]) {

                    flag = true;

                    temp = arr[j];

                    arr[j] = arr[j + 1];

                    arr[j + 1] = temp;

                }

            }

            System.out.println("第" + (i + 1) + "趟排序后的数组");

            System.out.println(Arrays.toString(arr));

            if (!flag) { // 在一趟排序过程中，一次交换都没有发生过

                break;

            } else {

                flag = false; // 重置flag，进行下次判断

            }

        }

    }

}