Day60.算法训练

912. 排序数组

• 归并排序

class Solution {

    public int[] sortArray(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        int[] assist = new int[nums.length];

        sortArray(nums, assist, lo, hi);
        return nums;
    }

    private void sortArray(int[] nums, int[] assist, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        int mid = lo + (hi - lo) / 2;

        sortArray(nums, assist, lo, mid);

        sortArray(nums, assist, mid + 1, hi);

        merge(nums, assist, lo, mid, hi);
    }

    private void merge(int[] nums, int[] assist, int lo, int mid, int hi) {
        int p1 = lo;
        int p2 = mid + 1;
        int i = lo;
        while (p1 <= mid && p2 <= hi) {
            if (lessCmp(nums[p1], nums[p2])) {
                assist[i++] = nums[p1++];
            } else {
                assist[i++] = nums[p2++];
            }
        }

        while (p1 <= mid) {
            assist[i++] = nums[p1++];
        }
        while (p2 <= hi) {
            assist[i++] = nums[p2++];
        }

        for (int index = lo; index <= hi; index++) {
            nums[index] = assist[index];
        }
    }

    private boolean lessCmp(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
}

• 快速排序

class Solution {

        public int[] sortArray(int[] nums) {
            int lo = 0;
            int hi = nums.length - 1;

            sortArray(nums, lo, hi);
            return nums;
        }

        private void sortArray(int[] nums, int lo, int hi) {
            if (lo >= hi) {
                return;
            }

            int partion = partion(nums, lo, hi);

            sortArray(nums, lo, partion - 1);

            sortArray(nums, partion + 1, hi);
        }

        private int partion(int[] nums, int lo, int hi) {
            int k = nums[lo];
            int left = lo;
            int right = hi + 1;
            while (true) {
                while (right > 0 && gtCmp(nums[--right], k)) {
                    if (right == lo) {
                        break;
                    }
                }

                while (left < hi && leCmp(nums[++left], k)) {
                    if (left == hi) {
                        break;
                    }
                }

                if (left == right) {
                    break;
                }
                exch(nums, left, right);
            }
            exch(nums, lo, right);
            return right;
        }

        private void exch(int[] nums, int left, int right) {
            int a = nums[left];
            nums[left] = nums[right];
            nums[right] = a;
        }

        private boolean leCmp(Comparable a, Comparable b) {
            return a.compareTo(b) < 0;
        }

        private boolean gtCmp(Comparable a, Comparable b) {
            return a.compareTo(b) > 0;
        }
    }