重学数据结构和算法（五）之归并排序、快速排序

递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件：
p >= r 不用再继续分解

public class MergeSort {
    public void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(a, left, middle);//左边归并排序，使得左子序列有序
            mergeSort(a, middle + 1, right);//右边归并排序，使得右子序列有序
            merge(a, left, middle, right);//将两个有序子数组合并操作
        }
    }

    private void merge(int[] a, int left, int middle, int right) {//left0,mid0,right1
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int[] tmpArray = new int[a.length];
        int rightStart = middle + 1;//右序列指针
        int leftStart = left;//左序列指针
        int temp = left;//临时数组指针
        //比较两个小数组相应下标位置的数组大小，小的先放进新数组
        while (left <= middle && rightStart <= right) {
            if (a[left] <= a[rightStart]) {
                //相当于tmpArray[third]=a[left];third++;left++三步合一步
                tmpArray[temp++] = a[left++];
            } else {
                tmpArray[temp++] = a[rightStart++];
            }
        }
        //如果左边还有数据需要拷贝，把左边数组剩下的拷贝到新数组
        while (left <= middle) {
            tmpArray[temp++] = a[left++];
        }
        //如果右边还有数据......
        while (rightStart <= right) {
            tmpArray[temp++] = a[rightStart++];
        }
        //将temp中的元素全部拷贝到原数组中
        while (leftStart <= right) {
            a[leftStart] = tmpArray[leftStart++];
        }
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] a = new int[]{9, 7, 6, 5, 4, 3, 2, 1};
        mergeSort.mergeSort(a, 0, a.length - 1);
        for (int n : a) {
            System.out.print(" " + n);
        }
    }
}

public class QuickSort {

    public void quick(int[] a) {
        if (a.length > 0) {
            quickSort(a, 0, a.length - 1);
        }
    }

    /**
     * 快速排序
     * @param a
     * @param low  低位
     * @param high 高位
     */
    private void quickSort(int[] a, int low, int high) {
        if (low < high) {
            int middle = getMiddle(a, low, high);
            //递归排比第一个基数小的数和大的数
            quickSort(a, 0, middle - 1);
            quickSort(a, middle + 1, high);
        }
    }

    /**
     *
     * @param a
     * @param low
     * @param high
     * @return
     */
    private int getMiddle(int[] a, int low, int high) {
        int temp = a[low];//基准元素
        while (low < high) {//第二次3，9
            while (low < high && a[high] >= temp) {
                high--;
            }
            a[low] = a[high];//将比基数小的数放到基数前面///用个数字想一下就明白了
            while (low < high && a[low] <= temp) {
                low++;
            }
            a[high] = a[low];//将比基数大的数放到基数后面
        }
        a[low] = temp;//插入到排序后正确的位置，low就是基数应该在的位置
        return low;
    }
}

int kthLargest = leetCode.findKthLargest(new int[]{4, 2, 5, 12, 3}, 3);
//倒数
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0, right = len - 1;
        int pivot = 0;
        while (len - k != (pivot = partition(nums, left, right))) {
        //4所在的问题就是2，那就找到了
        //第k大应该在第K位，找每个数字应该在的位置，正好第0个4就是第K位，就找到了
            if (pivot < len - k) {//在后面
                left = pivot + 1;
                right = len - 1;
            } else {
                left = 0;
                right = pivot - 1;
            }
        }
        return nums[pivot];
    }
    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot)
                right--;
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot)
                left++;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }
}