排序算法

Merge Sort

通过把大的list不断切分成小的list，然后可以方便的merge起来。

要素：

• base-case: size == 1
• 传参： mergeSort(int[] arr, int start, int end);
• 切分： mid = (start + end) / 2

TopDownSplitMerge(B[], iBegin, iEnd, A[]) {
    if(iEnd - iBegin < 2)                       // if run size == 1
        return;                                 //   consider it sorted
    // split the run longer than 1 item into halves
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // sort the left  run
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // sort the right run
    // merge the resulting runs from array B[] into A[]
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}

merge sort 不是inplace的，需要O(n)的空间复杂度来帮助merge

Copy the smallest values from either the left or the right side back to the original array。

Sory Element by Frequency and alphabetical order

3，1，5，2，2，4，4 -> 2，2，4，4，1，3，5

1）统计词频 2）用一个wrapper class把词频和对应的element 关联到一起 3）新建一个comparator来排序，如果freq相同就按照alphabetical 来排序，否则就按照freq大小来排序 4）输出结果

public class SortElementByFrequency {
    // bucket sort
    // 3,1,5,2,2,4,4 -> 2,2,4,4,1,3,5

    static class Pair implements Comparable<Pair> {
        int num;
        int count;
        public Pair(int num, int count) {
            this.num = num;
            this.count = count;
        }

        // if they have same freq, sort by num
        // otherwise, sort by freq
        public int compareTo(Pair p1) {
            if (p1.count == this.count) {
                return this.num - p1.num;
            } else {
                return p1.count - this.count;
            }
        }
    }

    public static List<Integer> bucketSort(List<Integer> nums) {
        // check input
        // ...

        HashMap<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.putIfAbsent(num, 0);
            count.put(num, count.get(num) + 1);
        }

        List<Pair> pairs = new ArrayList<>();
        for (int num : count.keySet()) {
            Pair pair = new Pair(num, count.get(num));
            pairs.add(pair);
        }

        Collections.sort(pairs);

        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < pairs.size(); i++) {
            int size = pairs.get(i).count;
            for (int j = 0; j < size; j++) {
                result.add(pairs.get(i).num);
            }
        }

        return result;


    }

    public static void main(String[] args) {
        Integer[] array = new Integer[]{3,1,5,2,2,4,4};
        List<Integer> nums = Arrays.asList(array);

        for (int num : bucketSort(nums)) {
            System.out.println(num);
        }
    }

}