快排
class Solution {
public:
int partition(vector<int>&nums,int left, int right){
swap(nums[right],nums[rand()%(right-left+1)+left]);
int pivot = nums[right];
int i =left-1;
for(int j=left;j<=right-1;++j){
if(nums[j]<pivot){
i++;
swap(nums[i],nums[j]);
}
}
swap(nums[i+1],nums[right]);
return i+1;
};
void quicksort(vector<int>& nums,int left,int right){
if(left<right){
int pos =partition(nums,left,right);
quicksort(nums,left,pos-1);
quicksort(nums,pos+1,right);
}
};
vector<int> sortArray(vector<int>& nums) {
srand((unsigned)time(NULL));
quicksort(nums,0,(int)nums.size()-1);
return nums;
}
};
二、归并
class Solution {
public:
void merge(vector<int> &nums,int left,int mid,int right){
vector<int> tmp(right-left+1);
int i=left,j=mid+1,k=0;
while(i<=mid&&j<=right){
tmp[k++] = nums[i]<nums[j]?nums[i++]:nums[j++];
}
while(i<=mid) tmp[k++]=nums[i++];
while(j<=right) tmp[k++]=nums[j++];
for(i=0;i<k;++i) nums[left+i] = tmp[i];
}
void mergeSort(vector<int> &nums,int left,int right){
if(left>=right) return;
int mid =left+(right-left)/2;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
merge(nums,left,mid,right);
}
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums,0,(int)nums.size()-1);
return nums;
}
};
|