package com.harrison.Class01;
import java.util.Arrays;
public class Code02_BubbleSort {
  /**
   * 在arr[0 ~ N-1]范围上:
   * arr[0]和arr[1]，谁大谁来到1位置;
   * arr[1]和arr[2]，谁大谁来到2位置;
   * arr[N-2]和arr[N-1]，谁大谁来到N-1位置
   * 
   * 在arr[0~N-2]范围上，重复上面的过程，
   * 但最后一步是arr[N-3]和arr[N-2]，谁大谁来到N-2位置
   * 
   * 在arr[0~N-3]范围上，重复上面的过程，
   * 但最后一步是arr[N-4]和arr[N-3]，谁大谁来到N-3位置
   * 
   * 最后在arr[0~ 1]范围上，重复上面的过程，
   * 但最后一步是arr[0]和arr[1]，谁大谁来到1位置
   */
  public static void bubbleSort(int[] arr) {
    if(arr==null || arr.length<2) {
      return;
    }
    //0~N-1
    //0~N-2
    //0~N-3
    //...
    //N-2~N-1
    for(int e=arr.length-1; e>0; e--) {//0~e
      //0~1
      //1~2
      //2~3
      //e-1~e
      for(int i=0; i<e; i++) {
        if(arr[i]>arr[i+1]) {
          swap(arr, i, i+1);
        }
      }
    }
  }
  public static void swap(int[] arr,int i,int j) {
    int t=arr[i];
    arr[i]=arr[j];
    arr[j]=t;
  }
  public static void comparator(int[] arr) {
    Arrays.sort(arr);
  }
  public static int[] generateRandomArray(int maxSize,int maxValue) {
    int[] arr=new int[(int)(Math.random()*(maxSize+1))];
    for(int i=0; i<arr.length; i++) {
      arr[i]=(int)(Math.random()*(maxValue+1))-(int)(Math.random()*maxValue);
    }
    return arr;
  }
  public static int[] copyArray(int[] arr) {
    if(arr==null) {
      return null;
    }
    int[] res=new int[arr.length];
    for(int i=0; i<arr.length; i++) {
      res[i]=arr[i];
    }
    return res;
  }
  public static void printArray(int[] arr) {
    if(arr==null) {
      return;
    }
    for(int i=0; i<arr.length; i++) {
      System.out.print(arr[i]+" ");
    }
    System.out.println();
  }
  public static boolean isEqual(int[] arr1,int[] arr2) {
    if(arr1==null && arr2==null) {
      return true;
    }
    if((arr1!=null && arr2==null) || (arr1==null && arr2!=null)) {
      return false;
    }
    if(arr1.length!=arr2.length) {
      return false;
    }
    for(int i=0; i<arr1.length; i++) {
      if(arr1[i]!=arr2[i]) {
        return false;
      }
    }
    return true;
  }
  public static void main(String[] args) {
    int testTimes=1000000;
    int maxSize=100;
    int maxValue=100;
    boolean succeed=true;
    for(int i=0; i<testTimes; i++) {
      int[]arr1=generateRandomArray(maxSize, maxValue);
      int[]arr2=copyArray(arr1);
      bubbleSort(arr1);
      comparator(arr2);
      if(!isEqual(arr1,arr2)) {
        succeed=false;
        printArray(arr1);
        printArray(arr2);
        break;
      }
    }
    System.out.println(succeed?"Nice":"Fucking fucked");
    int[]arr3=generateRandomArray(maxSize, maxValue);
    printArray(arr3);
    bubbleSort(arr3);
    printArray(arr3);
  }
}