912. 排序数组（中等）

青旅半醒 2022-09-12 03:53 115阅读 0赞

### 912. 排序数组 ###

*   *   *  题目描述
         *  源码
         *   *   *  方法一：快速排序
                 *  方法二：归并排序
                 *  方法三：堆排序

Leetcode链接：[912. 排序数组][912.]

### 题目描述 ###

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

示例 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

### 源码 ###

##### 方法一：快速排序 #####

class Solution {
        
        public int[] sortArray(int[] nums) {
        
            int n = nums.length;
            quickSort(nums, 0, n - 1);
            return nums;
        }
    
        public void quickSort(int[] nums, int left, int right){
        
            if(left >= right) return;
    
            int target = nums[left];
            int i = left;
            int j = right;
    
            while(i < j){
        
                while(i < j && nums[j] >= target){
        
                    j --;
                }
                while(i < j && nums[i] <= target){
        
                    i ++;
                }
    
                if(i < j){
        
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
    
            nums[left] = nums[i];
            nums[i] = target;
    
            quickSort(nums, left, i - 1);
            quickSort(nums, i + 1, right);
        }
    }

##### 方法二：归并排序 #####

class Solution {
        
        //2.归并排序
        public int[] sortArray(int[] nums) {
        
            int n = nums.length;
            //辅助数组，节省空间
            int[] help = new int[n];
            mergeSort(nums, 0, n - 1, help);
            return nums;
        }
    
        public void mergeSort(int[] nums, int left, int right, int[] help){
        
            if(left >= right) return;
            int middle = left + (right - left) / 2;
            mergeSort(nums, left, middle, help);
            mergeSort(nums, middle + 1, right, help);
            merge(nums, left, right, help);
        }
    
        public void merge(int[] nums, int left, int right, int[] help){
        
            for(int i = left; i <= right; i ++){
        
                help[i] = nums[i];
            }
            int middle = left + (right - left) / 2;
            int i = left;
            int j = middle + 1;
            int k = left;
    
            while(i <= middle && j <= right){
        
                if(help[i] <= help[j]){
        
                    nums[k ++] = help[i ++];
                }else{
        
                    nums[k ++] = help[j ++];
                }
            }
    
            while(i <= middle){
        
                nums[k ++] = help[i ++];
            }
            while(j <= right){
        
                nums[k ++] = help[j ++];
            }
        }
    }

##### 方法三：堆排序 #####

[https://leetcode-cn.com/problems/sort-an-array/solution/fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419/][https_leetcode-cn.com_problems_sort-an-array_solution_fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419]

[912.]: https://leetcode-cn.com/problems/sort-an-array/
[https_leetcode-cn.com_problems_sort-an-array_solution_fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419]: https://leetcode-cn.com/problems/sort-an-array/solution/fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419/