LeetCode912. 排序数组【快速排序】

淩亂°似流年 2023-01-22 10:49 45阅读 0赞

题目难度：中等  
题目描述：

> 给你一个整数数组 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:
        void quicksort(vector<int>& nums,int l,int r){ 
            if(l<r){ 
                int pivot=part(nums,l,r);
                quicksort(nums,l,pivot-1);
                quicksort(nums,pivot+1,r);
            }
        }
        int part(vector<int>& nums,int l,int r){ 
            int mid = l + ((r-l) >> 1);//三数取中
            if (nums[l] > nums[r]) swap(nums[l],nums[r]);
            if (nums[mid] > nums[r]) swap(nums[mid],nums[r]);
            if (nums[mid] > nums[l]) swap(nums[mid],nums[l]); 
            int pivot=nums[l];
            while(l<r){ 
                while(l<r&&nums[r]>=pivot){ 
                    r--;
                }
                nums[l]=nums[r];
                while(l<r&&nums[l]<=pivot){ 
                    l++;
                }
                nums[r]=nums[l];
            }
            nums[l]=pivot;
            return l;
        }
        vector<int> sortArray(vector<int>& nums) { 
            int r=nums.size()-1;
            quicksort(nums,0,r);
            return nums;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，45人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-912. 排序数组

目录题目思路代码实现题目来源 [912. 排序数组][912.] 题目思路快速排序原理：快速排序算法有两个核心点，分

偏执的太偏执、/ 2024年03月23日 13:35/ 0 赞/ 83 阅读

相关数组-快速排序

话不多说，直接上代码： public class kuaisu { public static void main(String[] args

淩亂°似流年/ 2023年06月14日 10:43/ 0 赞/ 14 阅读

相关 LeetCode912. 排序数组【快速排序】

题目难度：中等题目描述： > 给你一个整数数组 nums，请你将该数组升序排列。示例 1： > 输入：nums = \[5,2,3,1\] > 输出：\[1,

淩亂°似流年/ 2023年01月22日 10:49/ 0 赞/ 46 阅读

相关 leetcode--912--排序数组

给你一个整数数组 nums，请你将该数组升序排列。示例 1：输入：nums = \[5,2,3,1\] 输出：\[1,2,3,5\] 示例 2：输入：num

怼烎@/ 2022年10月24日 11:55/ 0 赞/ 178 阅读

相关 912. 排序数组（中等）

912. 排序数组题目描述源码方法一：快速排序方法

青旅半醒/ 2022年09月12日 03:53/ 0 赞/ 124 阅读

相关 LeetCode-912. 排序数组

排序数组给你一个整数数组 nums，请你将该数组升序排列。示例 1：输入：nums = [5,2,3,1] 输出：[1,2,3,5] 示例 2

- 日理万妓/ 2022年09月03日 13:14/ 0 赞/ 156 阅读

相关 LeetCode:快速排序

快速排序（Quicksort）是对[冒泡排序][Link 1]的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另

迈不过友情╰/ 2022年05月16日 11:50/ 0 赞/ 37 阅读

相关数组快速排序

[常用数组排序算法][Link 1] 1. 2. 3. public class SortAll \{ 4. 5. /\\ 6.

墨蓝/ 2022年03月20日 04:28/ 0 赞/ 233 阅读

相关 js数组排序---自定义快速排序

文章目录 js数组自带的sort方法快速排序测试一下效率 2020年

小鱼儿/ 2021年09月28日 14:54/ 0 赞/ 565 阅读

相关数组（五）--快速排序

快速排序（Quicksort）是对 [冒泡排序][Link 1]的一种改进。它的基本思想是： > 一趟快速排序的算法是： > > 1）设置两个变量i、j， [排序][L

系统管理员/ 2021年09月14日 08:14/ 0 赞/ 323 阅读