912. Sort an Array

QuickSort

class Solution {
    public int[] sortArray(int[] nums) {
        sortArray(nums, 0, nums.length - 1);
        return nums;
    }

    private void sortArray(int[] nums, int left, int right) {
        if (left >= right) { // 注意此处需要使用大于等于，当上一层 [0, 1] 找到任意一个枢纽后的下一层调用将会出现 left 大于 right 的情况
            return;
        }

        int pivotIndex = partition(nums, left, right);
        sortArray(nums, left, pivotIndex - 1);
        sortArray(nums, pivotIndex + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        int pivotIndex = left + ThreadLocalRandom.current().nextInt(right - left + 1);
        int pivotValue = nums[pivotIndex];
        swap(nums, left, pivotIndex);

        int index = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, i, ++index); // 确保跳出时 index 为小于 pivotValue 的元素
            }
        }

        swap(nums, left, index); // 注意此处是将 left 与 index 交换，因为 left 为枢纽元素

        return index; // 注意此处返回 index
    }

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

QuickSort

class Solution {
    public int[] sortArray(int[] nums) {
        sortArray(nums, 0, nums.length - 1);
        return nums;
    }

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

        int pivotIndex = partition(nums, left, right);
        sortArray(nums, left, pivotIndex - 1);
        sortArray(nums, pivotIndex + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        int randomIndex = left + ThreadLocalRandom.current().nextInt(right - left + 1);
        swap(nums, left, randomIndex);

        int pivotValue = nums[left];
        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= pivotValue) {
                j--;
            }
            while (i < j && nums[i] <= pivotValue) {
                i++;
            }
            swap(nums, i, j);
        }

        swap(nums, left, i);
        return i;
    }

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

MergeSort

class Solution {
    public int[] sortArray(int[] nums) {
        int[] tmp = new int[nums.length];
        mergeSort(nums, tmp, 0, nums.length - 1);
        return nums;
    }

    private void mergeSort(int[] nums, int[] tmp, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = (left + right) >>> 1;
        // [left, mid] / [mid + 1, right]
        mergeSort(nums, tmp, left, mid);
        mergeSort(nums, tmp, mid + 1, right);

        // 如果左侧数组末尾元素值小于等于右侧数组起始元素值，则提前返回
        if (nums[mid] <= nums[mid + 1]) {
            return;
        }

        for (int i = left; i <= right; i++) {
            tmp[i] = nums[i];
        }

        int i = left, j = mid + 1;
        int k = left;
        while (i <= mid || j <= right) {
            if (i > mid) {
                nums[k++] = tmp[j++];
            } else if (j > right) {
                nums[k++] = tmp[i++];
            } else if (tmp[i] <= tmp[j]) {
                nums[k++] = tmp[i++];
            } else {
                nums[k++] = tmp[j++];
            }
        }
    }
}

Priority Queue

class Solution {
    public int[] sortArray(int[] nums) {
        // index tree:
        //      0
        //   1    2
        // 3  4  5  6

        // 堆排序思路：先建立大根堆，然后将堆顶元素交换至数组尾部完成排序
        heapify(nums); // 建立大根堆

        int endIndex = nums.length - 1;
        while (endIndex > 0) {
            // 将最大值交换至 endIndex
            swap(nums, 0, endIndex--);
            siftdown(nums, 0, endIndex);
        }

        return nums;
    }

    private void heapify(int[] nums) {
        // 从最后一个非叶子节点开始倒序 siftdown
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            siftdown(nums, i, nums.length - 1);
        }
    }

    private void siftdown(int[] nums, int i, int endIndex) {
        while (i * 2 + 1 <= endIndex) {
            // 存在左子节点
            int maxChildIndex = i * 2 + 1;
            // 如果存在右子节点且右子节点的值比左子节点大
            if (maxChildIndex + 1 <= endIndex && nums[maxChildIndex + 1] > nums[maxChildIndex]) {
                maxChildIndex++;
            }
            if (nums[i] < nums[maxChildIndex]) {
                // 将 nums[i] 下潜
                swap(nums, i, maxChildIndex);
            } else {
                // nums[i] 大于所有子节点，已满足大根堆的性质，下潜结束
                break;
            }
            i = maxChildIndex; // 继续尝试下潜
        }
    }

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

Reference

912. Sort an Array