归并

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
• 重复步骤 3 直到某一指针达到序列尾；
• 将另一序列剩下的所有元素直接复制到合并序列尾。

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        mergeSort(arr, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left == right) return;
        int mid = left + ((right - left) >> 1);
        // left
        mergeSort(arr, left, mid);
        // right
        mergeSort(arr, mid + 1, right);
        // merge
        merge(arr, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int i = 0;
        int p1 = left;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while(p2 <= right) {
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[left + j] = help[j];
        }
    }
}

快排

• 从数列中挑出一个元素，称为”基准”；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以放到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
• 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序；

public class QuickSort {
    public static int[] quickSort(int[] arr) {
        return quickSort(arr, 0, arr.length - 1);
    }

    public static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            // 左半部分递归
            quickSort(arr, left, partitionIndex - 1);
            // 右半部分递归
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index++);
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

1、最小的k个数

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组

>输入
>[4,5,1,6,2,7,3,8],4
>返回值
>[1,2,3,4]

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || input.length == 0 || k > input.length) return list;
        Arrays.sort(input);
        // 犯规就犯规
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }
}

2. 数组中的第K个最大元素(855)

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

>输入: [3,2,1,5,6,4] 和 k = 2
>输出: 5
>输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
>输出: 4

排序 ：时间复杂度 O(NlogN)，空间复杂度 O(1)

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

堆 ：时间复杂度 O(NlogK)，空间复杂度 O(K)。

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
    for (int val : nums) {
        pq.add(val);
        if (pq.size() > k)  // 维护堆的大小为 K
            pq.poll();
    }
    return pq.peek();
}

快排

public int findKthLargest(int[] nums, int k) {
    // 注意k
    k = nums.length - k;
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int j = partition(nums, l, h);
        if (j == k) {
            break;
        } else if (j < k) {
            l = j + 1;
        } else {
            h = j - 1;
        }
    }
    return nums[k];
}

private int partition(int[] a, int l, int h) {
    int pivot = l;
    int index = pivot + 1;
    for (int i = index; i <= h; i++) {
        if (a[i] < a[pivot])
            swap(a, i, index++);
    }
    swap(a, pivot, index - 1);
    return index - 1;
}

private void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

3. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

>输入：nums1 = [1,3], nums2 = [2]
>输出：2.00000
>解释：合并数组 = [1,2,3] ，中位数 2

>输入：nums1 = [1,2], nums2 = [3,4]
>输出：2.50000
>解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

>输入：nums1 = [], nums2 = [1]
>输出：1.00000

>输入：nums1 = [0,0], nums2 = [0,0]
>输出：0.00000

// 归并

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] temp = new int[nums1.length + nums2.length];
        // 归并，三个指针，走起
        int i = 0;
        int j = 0;
        int t = 0;
        while (i < nums1.length && j < nums2.length) {
            temp[t++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];
        }

        while (i < nums1.length) {
            temp[t++] = nums1[i++];
        }

        while (j < nums2.length) {
            temp[t++]  = nums2[j++];
        }
        // 加起来，取中位数
        double b = (temp[(temp.length - 1) / 2] + temp[temp.length / 2]) * 1.0 / 2;
        return b;
    }
}

4. 根据字符出现频率排序

// 注意list的sort
class Solution {
    public String frequencySort(String s) {
        if (s == null || s.length() == 0)
            return s;
        // 先map统计
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        // 然后map.entrySet传进来
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        // 按照value排序
        Collections.sort(list, (o1, o2) -> {
            return o2.getValue() - o1.getValue();
        });
        // list
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : list){
            int cnt = entry.getValue();
            char key = entry.getKey();
            while (cnt-- > 0)
                sb.append(key);
        }
        return sb.toString();
    }
}