class Untitled {
    public static void main(String[] args) {
        
        Untitled a = new Untitled();
        int[] arrToSort = {2, 9 ,5, 19, 28, 99, 65, 73, 32, 53};
//      a.insertSort(arrToSort);
//      a.bubbleSort(arrToSort);
//      a.quickSort(arrToSort, 0, arrToSort.length - 1);
        int[] temp = new int[arrToSort.length];
        a.mergeSort(arrToSort, 0, arrToSort.length - 1, temp);
        a.printArr(arrToSort);
    }
    
    // 插入排序算法 最差时间复杂度为O(n^2) 最佳O(n)
    public void insertSort(int[] arr) {
        
        for (int i = 1; i < arr.length; i++) {
            int j = i - 1;
            int insertNum = arr[i];
            while (j > 0 && arr[j] > insertNum) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = insertNum;
        }
    }
    
    
    // 冒泡排序 最差时间复杂度为O(n^2) 最佳O(n)
    public void bubbleSort(int[] arr) {
        
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j+1]) {// 两两比较 保证最大数插到最后面
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    
    // 快速排序 用到了递归思想
    // 最差时间复杂度O(n^2) 为每次都划分为1个数和剩余所有数这样两组数组的情况
    // 最佳时间复杂度O(nlogn) 为每次都平分的情况
    // 平均时间复杂度O(nlogn) 
    public void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        
        int i = start;
        int j = end;
        int comNum = arr[i];// 基准数
        while(i <= j) {
            while(arr[j] > comNum && j > start) j--;
            while(arr[i] < comNum && i < end) i++;
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                //　下面两步很关键　否则会无限循环
                i++;
                j--;
            }
        }
        
        // 注意这里参数
        quickSort(arr, start, j);
        quickSort(arr, i, end);
    }
    
    
    // 归并排序 递归+合并 时间复杂度为O(nlogn)
    // 需要建立一个临时数组用来存储归并结果
    public void mergeSort(int[] arr, int start, int end, int[] temp) {
        if (start >= end || start < 0 || end > arr.length - 1) {
            return;
        }
        
        int mid = (end + start) / 2;
        mergeSort(arr, start, mid, temp);
        mergeSort(arr, mid+1, end, temp);
        merge(arr, start, mid, end, temp);
    }
    // 归并排序的辅助函数 用于合并已经排序的一段数组
    public void merge(int[] arr, int start, int mid, int end, int[] temp) {
        int i = start;
        int j = mid + 1;
        int k = start;
        while (i < mid + 1 && j < end + 1) {
            if (arr[i] < arr[j]) {
                temp[k] = arr[i];
                i++;
            } else {
                temp[k] = arr[j];
                j++;
            }
            k++;
        }
        // 考虑左右数组未合并完的情况
        while (i < mid + 1) {
            temp[k] = arr[i];
            k++;
            i++;
        }
        while (j < end + 1) {
            temp[k] = arr[j];
            k++;
            j++;
        }
        // 将临时数组填充到结果数组里
        while(start <= end) {
            arr[start] = temp[start];
            start++;
        }
    }
    
    public void printArr(int[] arr) {
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    // 反转链表
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode lastNode = head;
        ListNode currentNode = head.next;
        head.next = null;// 注意这里 否则会形成循环
        while(currentNode.next != null) {
            ListNode tempNode = currentNode.next;
            currentNode.next = lastNode;
            lastNode = currentNode;
            currentNode = tempNode;
        }
        currentNode.next = lastNode;
        return currentNode;
    }
}