public class MergeSort {
    public static void main(String[] args) {
        int[] ans = {6, 8, 4, 4, 6, 36, 673, 13, 6, 7, 3, 4, 6, 8, 3, 7, 5, 7, 9, 5};
        System.out.print("原數組：");
        for (int i = 0; i < ans.length; i++) {
            System.out.print(ans[i]+",");
        }
        System.out.println();
        mergeSort(ans);
        System.out.print("歸并排序之后的數組：");
        for (int i = 0; i < ans.length; i++) {
            System.out.print(ans[i]+",");
        }
    }

    //sort方法的驅動程序
    private static void mergeSort(int[] ans) {
        sort(ans, 0, ans.length - 1);
    }

    //將tmp和Cctr當做參數傳入，方便調用merge方法時獲得這兩個參數
    private static void sort(int[] ans, int left, int right) {
        int mid = (left + right) / 2;
        //當分到只剩下一個元素的情況,則退出遞歸程序
        if (left >= right) {
            return;
        }
        sort(ans, left, mid);
        sort(ans, mid + 1, right);
        merge(ans, left, mid, right);
    }

    private static void merge(int[] ans, int left, int mid, int right) {
        //聲明三個計時器
        int Actr = left;
        int Bctr = mid + 1;
        int Cctr = 0;
        int lenA = mid - left + 1;
        int lenB = right - mid;
        //創建臨時數組,長度為A，B數組長度之和
        int[] tmp = new int[right - left + 1];
        //循環A，B中長度較短的長度次數的二倍的次數
        while (Actr <= mid && Bctr <= right) {
            if (ans[Actr] <= ans[Bctr]) {
                tmp[Cctr++] = ans[Actr];
                Actr++;
            } else {
                tmp[Cctr++] = ans[Bctr];
                Bctr++;
            }
        }
        //如果左邊的還有剩余，將左邊剩余的歸并
        while (Actr <= mid){
            tmp[Cctr ++] = ans[Actr ++];
        }
        //如果右邊的還有剩余，將右邊剩余的歸并
        while (Bctr <= right){
            tmp[Cctr ++] = ans[Bctr ++];
        }
        //將臨時數組更新到原數組
        for (int i = 0; i < tmp.length; i++) {
            ans[left++] = tmp[i];
        }
    }
}

public class QuickSort {

    

    /**

     * 根據下標交換數組的兩個元素

     * @param arr 數組

     * @param index1  下標1

     * @param index2  下標2

     */

    public static void swap(int[] arr, int index1, int index2) {

        int temp = arr[index1];

        arr[index1] = arr[index2];

        arr[index2] = temp;

    }

    

    /**

     * 遞歸循環實現快排

     * @param arr 數組

     * @param startIndex 快排的開始下標

     * @param endIndex 快排的結束下標

     */

    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        if(arr != null && arr.length > 0) {

            int start = startIndex, end = endIndex;

            //target是本次循環要排序的元素，每次循環都是確定一個元素的排序位置，這個元素都是開始下標對應的元素

            int target = arr[startIndex];

            //開始循環，從兩頭往中間循環，相遇后循環結束

            while(start<end) {

                //從右向左循環比較，如果比target小，就和target交換位置，讓所有比target小的元素到target的左邊去

                while(start < end) {

                    if(arr[end] < target) {

                        swap(arr, start, end);

                        break;

                    }else {

                        end--;

                    }

                }

                

                //從左向右循環比較，如果比target大，就和target交換位置，讓所有比target大的元素到target的右邊去

                while(start < end) {

                    if(arr[start] > target) {

                        swap(arr, start, end);

                        break;

                    }else {

                        start++;

                    }

                }

            }

            //確定target的排序后，如果target左邊還有元素，繼續遞歸排序

            if((start-1)>startIndex) {

                quickSort(arr, startIndex, start-1);

            }

            //確定target的排序后，如果target右邊還有元素，繼續遞歸排序

            if((end+1)<endIndex) {

                quickSort(arr, end+1, endIndex);

            }

        }

    }

    

    public static void main(String[] args) {

        int[] arr = new int[]{4,1,8,5,3,2,9,10,6,7};

        quickSort(arr,0,9);

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

            System.out.print(arr[i]+",");

        }

    }

}