912. 排序数组

给你一个整数数组 nums,请你将该数组升序排列。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-an-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

示例 1:

输入:nums = [5,2,3,1]
输出:[1,2,3,5]

示例 2:

输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

提示:

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

解决方案

快排。思路参见《啊哈!算法》第1章第3节:最常用的排序——快速排序。

class Solution {

    private int[] array;

    public int[] sortArray(int[] nums) {
        array = nums;
        quickSort(0, nums.length - 1);
        return nums;
    }

    private void quickSort(int begin, int end) {
        if (begin >= end) {
            return ;
        }
        int middle = partition(begin, end);
        quickSort(begin, middle - 1);
        quickSort(middle + 1, end);
    }

    private int partition(int begin, int end) {
        int pivot = array[begin];
        int ptr1 = begin, ptr2 = end;

        while (ptr1 < ptr2) {
            while (ptr1 < ptr2 && array[ptr2] >= pivot) {
                ptr2 -= 1;
            }
            while (ptr1 < ptr2 && array[ptr1] <= pivot) {
                ptr1 += 1;
            }
            if (ptr1 < ptr2) {
                int tmp = array[ptr1];
                array[ptr1] = array[ptr2];
                array[ptr2] = tmp;
            }
        }

        array[begin] = array[ptr1];
        array[ptr1] = pivot;

        return ptr1;
    }

}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据