快速排序以及归并排序

之前一直觉得排序很难，觉得难以理解，甚至怀疑自己的智商。面试前看了排序算法觉得胸有成竹，但是等到真正面试时"突然忘了"，非常地尴尬。其实我觉得看十遍都不如写一遍代码，只要沉下心，就一定能搞定，真的没有那么复杂。
Just show me your code

package com.program;
public class Sort {
/**
     * 归并排序
     * 核心思想：分治思想，用递归实现
     * 如果需要对一个数组排序，将这个数组从中间拆成两个数组，分别对这两个数组进行排序，然后再将这两个有序的数组归并到一起，over。
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(n),归并排序没有流行，主要就是因为这个空间复杂度了，比如一万个数据就要一万个数组空间了。
     * 稳定性：稳定。
     */
    public void mergeSort(int[] data, int left, int right) {
        if (data == null || data.length == 0) {
            return;
        }
        if (left >= right) {
            return;
        }
        int middle = (left + right) / 2;
        mergeSort(data, left, middle);
        mergeSort(data, middle + 1, right);
        //将两个已经排好序的数组合并到一块
        merge(data, left, middle, middle + 1, right);
    }

    /**
     * 合并两个有序的数组，就是有两个指针分别指向两个数组首位，
     * 然后比较两个数组首位，谁小谁就移到另外一个数组里，然后改数组指针往后移动
     * 需要处理边界，一步小心就IndexOutException了
     */
    private void merge(int[] data, int firstLeft, int firstRight, int secondLeft, int secondRight) {
        //需要合并的数组长度；
        int length = secondRight - firstLeft + 1;
        int[] temp = new int[length];
        int tempFirstLft = firstLeft;
        int i = 0;
        while (firstLeft <= firstRight && secondLeft <= secondRight) {
            if (data[firstLeft] <= data[secondLeft]) {
                temp[i++] = data[firstLeft++];
            } else {
                temp[i++] = data[secondLeft++];
            }
        }
        while (firstLeft <= firstRight) {
            temp[i++] = data[firstLeft++];
        }
        while (secondLeft <= secondRight) {
            temp[i++] = data[secondLeft++];
        }
        for (int j = 0; j < (length); j++) {
            data[tempFirstLft + j] = temp[j];
        }
        for (int k = 0; k < data.length; k++) {
            System.out.print(data[k] + " ");
        }
        System.out.println();
    }

    /**
     * 经典算法：快速排序
     * 排序原理：1.从未排序的数组中挑选任意一个基准数，一般用第一个数作为基准🌲，
     * 2.然后将这个数组中比基准🌲小的放左边，大的放右边。
     * 3.递归把基准🌲左右的数组按照上面进行1、2步骤
     * 时间复杂度：平均复杂度O(nlogn),最差复杂度O(n^2)
     * 空间复杂度：O(1)
     * 扩展：如果获取一个无序数组里第K大的数？？
     * 解答：可以采用快速排序的分区方法，按照基准线分为左右两边，如果右边只有K-1个数时，那么这个基准值就是TopK值
     */
    public void quickSort(int[] data, int left, int right) {
        if (data == null || data.length == 0) {
            return;
        }
        if (left == right) {
            return;
        }
        int basic = getBasicIndex(data, left, right);
        if (basic > left) {
            quickSort(data, left, basic - 1);
        }
        if (basic < right)
            quickSort(data, basic + 1, right);
    }

    /**
     * 获取基准线的下标位置
     * 步骤如下：哨兵法
     * 1.设置两个指针分别指向首尾，
     * 2.设置第0个为基准(也可以设置最后一位为基准)
     * 3.末尾指针开始往前移动，直到移动到比基准小的数的位置停下，
     * 4.首部指针开始往后移动，直到移动到比基准大的数的位置停下，
     * 5.将首尾指针指向的数交换，
     * 6.回到第3步继续，直到首位指针相遇，然后将首位指针指向的数与基准数交换
     * 7.这样就将比基准小的都放在了左边，比基准大的都放到了右边
     * 上面这个步骤很重要
     */
    private int getBasicIndex(int[] data, int left, int right) {
        int basic = data[left];
        int i = left;
        int j = right;
        while (i != j) {
            if (data[j] < basic) {
                if (data[i] > basic) {
                    int temp = data[i];
                    data[i] = data[j];
                    data[j] = temp;
                    j--;
                } else {
                    i++;
                }
            } else {
                j--;
            }
        }
        data[left] = data[i];
        data[i] = basic;
        return i;
    }


    public static void main(String[] args) {
        //int[] data = new int[]{10, 11, 12, 13, 14, 3, 5, 6, 7, 8};
        //int[] data = new int[]{11, 24, 25, 10, 9, 11, 24, 25, 10, 9, 11, 67, 11, 67, 11, 24, 25, 11, 24, 25, 10, 9, 11, 67, 10, 9, 11, 67, 11, 24, 25, 10, 9, 11, 67, 33, 89, 11, 45, 22, 35, 56, 22, 23};
        Sort sort = new Sort();
        //int[] data = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        //sort.merge(data, 0, 4, 5, data.length - 1);
        //sort.mergeSort(data, 0, data.length - 1);
        int[] data = new int[]{6, 1, 2, 7, 9, 9, 0, 9, 2, 1, 3, 4, 5, 10, 8};
        sort.quickSort(data, 0, data.length - 1);
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
    }
}