在线验证算法

排序数组

算法实现

1. 快排

思路

树的前序遍历。
每次选取一个数作基准值，将小于基准值的数放在左边，大于基准值的数放在右边。遍历左子树及右子树，直到只有1个数为止。

实现

class QuickSort {
    public static void sort(int[] nums) {
        shuffle(nums);
        sort(nums, 0, nums.length - 1);
    }

    public static void sort(int[] nums, int left, int right) {
        if (left >= right) return;
        int pivot = partition(nums, left, right);
        sort(nums, left, pivot - 1);
        sort(nums, pivot + 1, right);
    }

    public static int partition(int[] nums, int lo, int hi) {
        int i = lo;
        for (int j = lo; j < hi; j++) {
            if (nums[j] < nums[hi]) {
                swap(nums, i++, j);
            }
        }
        swap(nums, i, hi);
        return i;
    }

    public static void shuffle(int[] nums) {
        Random random = new Random();
        int n = nums.length;
        for (int i = 0; i < n; i++)
            swap(nums, i, random.nextInt(n - i) + i);
    }

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

2. 归并

思路

树的后序遍历。
将左子树及右子树分别排序后合并。
合并时避免多次创建临时数组，可以使用同一个临时数组。

实现

class MergeSort {

    private static int[] temp;

    public static void sort(int[] nums) {
        temp = new int[nums.length];
        sort(nums, 0, nums.length - 1);
    }

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

    public static void merge(int[] nums, int left, int mid, int right) {
        for (int i = left; i <= right; i++)
            temp[i] = nums[i];
        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (temp[i] < temp[j]) {
                nums[k++] = temp[i++];
            } else {
                nums[k++] = temp[j++];
            }
        }
        while (i <= mid)
            nums[k++] = temp[i++];
        while (j <= right)
            nums[k++] = temp[j++];
    }

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