LeetCode两个经典的排序算法

LeetCode两个经典的排序算法

这回是标题党， 记录下两个分而治之的排序算法（手写），分而治之的算法很容易改造成并行算法，肯定是未来的潮流， leetcode已通过， 两个算法都使用了原地(inplace)更新。

class Solution {
    public List<Integer> sortArray(int[] nums) {
        // merge(nums, 0, nums.length - 1);
        sort(nums, 0, nums.length - 1);
        return IntStream.of(nums).boxed().collect(Collectors.toList());
    }

	//-------------------归并排序-------------------//
    private void merge(int[] nums, int start, int end) {
        if (start >= end) return;
        int midIdx = start + (end - start) / 2;
        merge(nums, start, midIdx);
        merge(nums, midIdx+1, end);
        concat(nums, start, midIdx, end);
    }

    private void concat(int[] nums, int start, int midIdx, int end) {
        int[] tmp = new int[end - start + 1];
        int lp = start, rp = midIdx + 1, i = 0;

        while (lp <= midIdx && rp <= end) {
            tmp[i++] = nums[lp] < nums[rp] ? nums[lp++] : nums[rp++];
        }

        while (lp <= midIdx) {
            tmp[i++] = nums[lp++];
        }

        while (rp <= end) {
            tmp[i++] = nums[rp++];
        }

        System.arraycopy(tmp, 0, nums, start, tmp.length);
    }

    // -------------------  归并排序 链表 ---------------------//

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) return null;
            return merge(lists, 0 , lists.length - 1);
        }

        private ListNode merge(ListNode[] lists, int low, int high) {
            if (low == high) return lists[low];

            int mid = (high - low) / 2 + low;

            return mergeLists( merge(lists, low, mid), merge(lists, mid+1, high));
        }

        public ListNode mergeLists(ListNode node1, ListNode node2) {
            if (node1 == null) return node2;
            if (node2 == null) return node1;

            if (node1.val < node2.val) {
                node1.next = mergeLists(node1.next, node2);
                return node1;
                
            } else {
                node2.next = mergeLists(node1, node2.next);
                return node2;
            }
        }
    }
    
    //-------------------快速排序-------------------//

    private void sort(int[] nums, int start, int end) {
        if (start >= end) return;

        int bIdx = partition(nums, start, end);
        sort(nums, start, bIdx - 1);
        sort(nums, bIdx + 1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int idx = start, base = nums[end];

        for (int i = start; i < end; i++) {
            if (nums[i] < base) {
                swap(nums, idx++, i);
            }
        }
        swap(nums, idx, end);
        return idx;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}