import java.util.Arrays;

public class n2 {

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //选择排序
    public static void selectionSort(int[] arr) {
        // 选最小的放第一个
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int mindex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[mindex] > arr[j]) {
                    mindex = j;
                }
            }
            swap(arr, mindex, i);
        }
    }

    //冒泡排序
    public static void bubbleSort(int[] arr) {
        // 大的往后冒
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j + 1, j);
                }
            }
        }
    }

    //插入排序
    public static void insertionSort(int[] arr) {
        // 往前面有序序列插入
        // 最好情况O(N)
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i; j >= 0 && arr[j + 1] < arr[j]; j--) {
                swap(arr, j + 1, j);
            }
        }
    }

    public static int[] generaRandomArray(int maxSize, int maxValue) {
        // Math.random()->[0,1)所有的小数，等概率返回一个
        // Math.random()*N->[0,N)所有小数，等概率返回一个
        // (int)(Math.random()*N)->[0,N-1]所有的整数，等概率返回一个
        int[] arr = new int[(int) (Math.random() * (maxSize + 1))]; // 长度随机
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1));
            // arr[i] = (int)(Math.random()*(maxValue+1)) -
            // (int)(Math.random()*(maxValue));//需要负数用这个
        }
        return arr;
    }

    public static void main(String[] args) {
        // // 选择冒泡插入排序测试
        // int[] arr = { 4, 5, 7, 3, 2, 1, 6, 9, 8, 1, 1, 10 };
        // // selectionSort(arr);
        // // bubbleSort(arr);
        // // insertionSort(arr);
        // for (int i : arr) {
        //     System.out.println(i);
        // }

        //对数器
        int testTime = 5000;
        int maxSize = 100;
        int maxValue = 100;
        String info = "true";
        for (int i=0;i<testTime;i++){
            int[] arr1 = generaRandomArray(maxSize, maxValue);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            bubbleSort(arr1);
            insertionSort(arr2);
            if(!Arrays.equals(arr1,arr2)){
                info = "false";
                break;
            }
        }
        System.out.println(info);


    }

}

// 堆排序
public static void heapSort(int[] arr) {
    buildMaxHeap1(arr);
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        maxHeapify(arr, 0, i);
    }
}


// 向下调整，小元素下坠
public static void maxHeapify(int[] arr, int root, int heapSize) {
    int largest = root;// 初始化最大元素的位置为根节点
    while (true) {
        int left = root * 2 + 1;
        int right = root * 2 + 2;
        // 找到左、右子节点中值最大的节点的位置
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        // 如果最大元素的位置不是根节点，交换它们，并更新当前节点位置
        if (largest != root) {
            swap(arr, largest, root);
            root = largest;
        } else {
            break;
        }
    }
}

// 向上调整，大元素上升
public static void heapInsert(int[] arr, int index) {
    while (arr[index] > arr[(index - 1) / 2]) { // index/2-1作为父节点的话，在0时可能为负数
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

// 建大根堆方法1
public static void buildMaxHeap1(int[] arr) {
    // 从最后一个非叶子节点开始，依次向上调整每个节点，使得每个子树都是最大堆
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, i, arr.length);
    }
}
// 建大根堆方法2
public static void buildMaxHeap2(int[] arr) {
    //依次插入变成大根堆
    for (int i = 0; i < arr.length; i++) {
        heapInsert(arr, i);
    }
}

// 归并排序思想求小和
// 小和：[1,3,4,2,5] 左边比它小的数相加 1+3+1+1+10
public static int getSmallSum(int[] arr, int l, int r) {
    if (l >= r || arr == null) {
        return 0;
    }
    int m = l + ((r - l) >> 1);
    int a = getSmallSum(arr, l, m);
    int b = getSmallSum(arr, m + 1, r);
    int c = sumMerge(arr, l, m, r);
    return a + b + c;
}

public static int sumMerge(int[] arr, int l, int m, int r) {
    int[] temp = new int[r - l + 1];
    int sum = 0;
    int p1 = l;
    int p2 = m + 1;
    int i = 0;
    while (p1 <= m && p2 <= r) {
        if (arr[p1] < arr[p2]) {
            sum += arr[p1] * (r - p2 + 1); // 计算每次归并的小和，归并排序比较 所在的地方
            temp[i++] = arr[p1++];
        } else {
            temp[i++] = arr[p2++];
        }
    }
    /*
         * 越界后不计算小和，因为这个算法本质是利用归并排序不浪费比较次数的特点（排序必定最少要来两两比较一次）
         * 比较过的信息保存下来，所以只在每次比较的时候计算小和，这样就不会多算也不会少算
         */
    while (p1 <= m) {
        temp[i++] = arr[p1++];
    }
    while (p2 <= r) {
        temp[i++] = arr[p2++];
    }
    for (int j = 0; j < temp.length; j++) {
        arr[l + j] = temp[j];
    }
    return sum;
}

//相对有序的序列排序
//一个数离他正确顺序位置不超过k为相对有序
public static void distanceLessKSort(int []arr,int k){
    //优先级队列就是堆，默认小根堆
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    //建大小为k的堆
    for(int i=0;i<= Math.min(arr.length-1, k);i++){
        heap.add(arr[i]);
    }
    //出堆一定依次有序
    int index = 0;
    for(int j = k+1;j<arr.length;index++,j++){
        heap.add(arr[j]);
        arr[index] = heap.poll();
    }
    while (!heap.isEmpty()) {
        arr[index++] = heap.poll();
    }
}