【高速配列アルゴリズムc+】---912.配列の並べ替え

6730 ワード

テーマ:整数配列numsをあげます.配列を昇順に並べてください.例1:入力:nums=[5,2,3,1]出力:[1,2,3,5]例2:
入力:nums=[5,1,1,2,0,0]出力:[0,0,1,2,5]
ヒント:1<=nums.length <= 50000 -50000 <= nums[i] <= 50000
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/sort-an-array構想:最も基本的な速い配列のルートの速い配列:まず1つの基礎ビットを見つけて通常最初はkey=nums[left]、left=0、right=numsである.size()-1; 右から左へキーより小さいものを探し、left位置、左からキーより大きいものを探し、right位置というように交互に探し、left=rightとなるまで、1回目の早送り終了後、left位置からこのときの配列を2つの部分に分けると、この2つの部分を再帰的に早送りする
上のコード:
class Solution
{
public:
    vector<int> sortArray(vector<int>& nums)
    {
        qucik(nums,0,nums.size()-1);
        return nums;
    }
    void qucik(vector<int>& nums,int s,int e)
{
    int left = s,right = e;
    int key = nums[left];
    while(left<right)
    {
        while(left<right)
        {
            if(nums[right]<=key)
            {
                nums[left] = nums[right];
                break;
            }
            right--;
        }
        while(left<right)
        {
            if(nums[left]>key)
            {
                nums[right] = nums[left];
                break;
            }
            left++;
        }
        nums[left] = key;
    }
    if(s<left-1)
    qucik(nums,s,left-1);
    if(left+1<e)
    qucik(nums,left+1,e);
}
};