public class Merge {
    public static void main(String[] args) {
        int[] arr = { 5, 2, 8, 4, 7, 1, 3, 6 };
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 拆分
     * @param arr 數(shù)組
     * @param left 數(shù)組第一個元素
     * @param right 數(shù)組最后一個元素
     */
    public static void mergeSort(int[] arr,int left,int right){
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    /**
     * 合并
     * @param arr 數(shù)組
     * @param left 數(shù)組第一個元素
     * @param mid 數(shù)組分割的元素
     * @param right 數(shù)組最后一個元素
     */
    public static void merge(int[] arr,int left,int mid,int right){
        //創(chuàng)建臨時數(shù)組，用于存放合并后的數(shù)組
        int[] temp = new int[right - left + 1];
        //左面數(shù)組的起始指針
        int i = left;
        //右面數(shù)組的起始指針
        int j = mid + 1;
        //臨時數(shù)組的下標(biāo)
        int k = 0;
        //數(shù)組左面和數(shù)組右面都還有值就去遍歷比較賦值
        while (i <= mid && j <= right) {
            //數(shù)組左面的值小于或者等于數(shù)組右面的值就把左面的值賦值到臨時數(shù)組中
            //并且把左面的指針和臨時數(shù)組的指針+1
            //否則相反
            if (arr[i] <= arr[j]) {
                temp[k] = arr[i];
                k++;
                i++;
            } else {
                temp[k] = arr[j];
                k++;
                j++;
            }
        }
        //把剩余數(shù)組塞進(jìn)去
        while (i <= mid) {
            temp[k] = arr[i];
            k++;
            i++;
        }
        while (j <= right) {
            temp[k] = arr[j];
            k++;
            j++;
        }
        //講臨時數(shù)組中的元素拷貝會回原數(shù)組中
        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
    }
}

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = { 5, 2, 8, 4, 7, 1, 3, 6 };
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int left,int right){
        if(left<right){
            int pivotIndex  = partition(arr, left, right);
            quickSort(arr,left,pivotIndex-1);
            quickSort(arr,pivotIndex+1,right);
        }
    }
    public static int partition(int[] arr,int left,int right){
        //取第一個元素為基準(zhǔn)元素
        int pivot = arr[left];
        int i = left+1;
        int j = right;
        while (i<=j){
            //當(dāng)前指針位置數(shù)小于基準(zhǔn)元素就繼續(xù)移動指針直到遇到大的
            while (i<=j && arr[i] < pivot){
                i++;
            }
            //當(dāng)前指針位置數(shù)大于基準(zhǔn)元素就繼續(xù)移動指針直到遇到小的
            while (i<=j && arr[j] > pivot){
                j--;
            }
            if(i<j){
                //交換元素位置
                swap(arr,i,j);
                i++;
                j--;
            }
        }
        //跳出循環(huán)說明i和j相遇,j的值一定是大于基準(zhǔn)元素,要和基準(zhǔn)元素進(jìn)行交換
        swap(arr,left,j);
        //返回基準(zhǔn)元素位置
        return j;
    }
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

public class SumTask extends RecursiveTask<Integer> {
    private static final int THRESHOLD = 1000;
    private int[] array;
    private int start;
    private int end;
    public SumTask(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }
    @Override
    protected Integer compute() {
        if (end - start <= THRESHOLD) {
            int sum = 0;
            for (int i = start; i < end; i++) {
                sum += array[i];
            }
            return sum;
        } else {
            int mid = (start + end) / 2;
            SumTask leftTask = new SumTask(array, start, mid);
            SumTask rightTask = new SumTask(array, mid, end);
            leftTask.fork();
            rightTask.fork();
            int leftResult = leftTask.join();
            int rightResult = rightTask.join();
            return leftResult + rightResult;
        }
    }
    public static void main(String[] args) {
        int[] array = new int[10000];
        for (int i = 0; i < array.length; i++) {
            array[i] = i + 1;
        }
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        SumTask task = new SumTask(array, 0, array.length);
        int result = forkJoinPool.invoke(task);
        System.out.println(result);
    }
}