import java.util.Arrays;

public class BubbleSort {

    private BubbleSort(){}

    public static <E extends Comparable<E>> void sort(E[] data){

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

            // arr[ n - i , n] 已经排好序
            // 通过冒泡在 arr[n - i - 1 ] 位置放上合适的元素
            for(int j = 0 ;  j  < data.length - i - 1; j ++ )
                // j , j + 1
                if(data[j].compareTo(data[j + 1])> 0)
                    swap(data, j , j +1);
        }
    }

    private static <E> void swap(E[] arr, int i , int j ){

        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {

        int n = 100000;
        Integer[] arr1 = ArrayGenerator.generateRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr1, arr1.length);
        sort(arr2);
        for(int i = 0 ; i < n ; i ++)
            System.out.println(arr2[i]);
        SortingHelper.sortTest("BubbleSort",arr1);

    }
}

public class SortingHelper {

    private SortingHelper(){} //私有类

    public static <E extends Comparable<E>> boolean isSorted(E[] arr){

        for(int i = 1; i< arr.length; i++)
            if (arr[i - 1].compareTo(arr[i]) > 0)
            return false;
        return true;
    }

    public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
        long startTime = System.nanoTime();
        if(sortname.equals("SelectionSort")) {
            SelectionSort.sort(arr);
        } else if(sortname.equals("InsertionSort"))
            InsertionSort.sort(arr);
        else if(sortname.equals("InsertionSort2"))
            InsertionSort.sort2(arr);
        else if(sortname.equals("MergeSort"))
            MergeSort.sort(arr);
        else if(sortname.equals("MergeSort2"))
            MergeSort.sort2(arr);
        else if(sortname.equals("MergeSort3"))
            MergeSort.sort3(arr);
        else if(sortname.equals("MergeSort4"))
            MergeSort.sort4(arr);
        else if(sortname.equals("MergeSortBU"))
            MergeSort.sortBU(arr);
        else if(sortname.equals("QuickSort"))
            QuickSort.sort(arr);
        else if(sortname.equals("QuickSort2"))
            QuickSort.sort2ways(arr);
        else if(sortname.equals("QuickSort3"))
            QuickSort.sort3ways(arr);
        else if(sortname.equals("HeapSort"))
            HeapSort.sort(arr);
        else if(sortname.equals("BubbleSort"))
            BubbleSort.sort(arr);
        long endTime = System.nanoTime();

        double time = (endTime - startTime) / 1000000000.0; //纳米要/9个零

        if(!SortingHelper.isSorted(arr))
            throw new RuntimeException(sortname + "failed");
        System.out.println(String.format("%s , n = %d : %f s ", sortname, arr.length, time));
    }
}

import java.util.Random;

public class ArrayGenerator {

    private ArrayGenerator(){}

    public static Integer[] generateOrderedArray(int n){

       Integer[] arr = new Integer[n];
       for(int i = 0; i < n ; i++)
           arr[i] = i;
       return arr;
    }

    // 生成一个长度为 n 的随机数组， 每个数字的范围是[ 0 , bound)
    public static Integer[] generateRandomArray(int n, int bound){

        Integer[] arr = new Integer[n];
        Random rnd = new Random();
        for(int i = 0 ; i < n; i++)
            arr[i] = rnd.nextInt(bound); //从0到bound前闭后开
        return arr;
    }
}