【高速配列アルゴリズム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つの部分を再帰的に早送りする
上のコード:
入力: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);
}
};