/*
 * 排序算法
 */
class Solution {
    public void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    // 直接插入排序, O(n^2), 稳定
    public void directInsert(int[] arr) {
        for (int i = 0; i < arr.length; i ++) {
            for (int j = 0; j < i; j ++) {
                if (arr[j] > arr[i]) {
                    int temp = arr[i];
                    System.arraycopy(arr, j, arr, j + 1, i - j);
                    arr[j] = temp;
                }
            }
        }
    }

    // 折半插入排序，O(nlogn)，稳定
    public void binaryInsert(int[] arr) {
        for (int i = 0; i < arr.length; i ++) {
            int left = 0, right = i - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] < arr[i]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            int temp = arr[i];
            System.arraycopy(arr, left, arr, left + 1, i - left);
            arr[left] = temp;
        }
    }

    // 选择排序， O(n^2)，不稳定
    public void directSelect(int[] arr) {
        for (int i = 0; i < arr.length - 1; i ++) {
            for (int j = i + 1; j < arr.length; j ++) {
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
    }
    
    // 堆排序， O(nlogn)，不稳定，最大堆
    public int[] sortArray(int[] nums) {
        // 建堆
        int n = nums.length;
        for (int i = n/2 - 1; i >= 0; i --) {
            heap(nums, n, i);
        }
        
        // 排序
        for (int i = n - 1; i >= 0; i --) {
            swap(nums, 0, i);
            for (int j = i / 2 - 1; j >= 0; j --) {
                heap(nums, i, j);
            }
        }
        return nums;
    }
    
    private void heap(int[] nums, int n, int i) {
        while (true) {
            int maxIndex = i;
            if (2*i + 1 < n && nums[2*i + 1] > nums[i]) {
                maxIndex = 2*i + 1;
            }
            
            if (2*i + 2 < n && nums[2*i + 2] > nums[maxIndex]) {
                maxIndex = 2*i + 2;
            }
            
            if (maxIndex == i) {
                break;
            }
            swap(nums, i, maxIndex);
            i = maxIndex;
        }
    }

    // 冒泡排序，O(n^2), 稳定
    public void bubble(int[] arr) {
        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, j + 1);
                }
            }
        }
    }

    // 快排，O(nlogn)，不稳定
    public void quick(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    private void quickSort(int[] arr, int left, int right) {
        if (arr == null || left >= right || arr.length <= 1) {
            return;
        }
        int mid = partition(arr, left, right);
        quickSort(arr, left, mid);
        quickSort(arr, mid + 1, right);
    }
    private int partition(int[] arr, int left, int right) {
        int temp = arr[left];
        while (left < right) {
            while (left < right && temp <= arr[right]) {
                right --;
            }
            if (left < right) {
                arr[left] = arr[right];
                left ++;
            }
            while (left < right && temp >= arr[left]) {
                left ++;
            }
            if (left < right) {
                arr[right] = arr[left];
                right --;
            }
        }
        arr[left] = temp;
        return left;
    }

    // 归并排序， O(nlogn)， 稳定
    public int[] sortArray(int[] nums) {
        if (nums.length <= 1) {
            return nums;
        }
        
        int mid = nums.length / 2;
        int[] leftArray = sortArray(Arrays.copyOfRange(nums, 0, mid));
        int[] rightArray = sortArray(Arrays.copyOfRange(nums, mid, nums.length));
        return merge(leftArray, rightArray);
    }
    
    private int[] merge(int[] leftArray, int[] rightArray) {
        int[] res = new int[leftArray.length + rightArray.length];
        int i = 0, j = 0, k = 0;
        
        while (i < leftArray.length && j < rightArray.length) {
            if (leftArray[i] < rightArray[j]) {
                res[k ++] = leftArray[i ++];
            } else {
                res[k ++] = rightArray[j ++];
            }
        }
        
        while (i < leftArray.length) {
            res[k ++] = leftArray[i ++];
        }
        
        while (j < rightArray.length) {
            res[k ++] = rightArray[j ++];
        }
        return res;
    }
}