优选算法_分治_快速排序_归并排序_C++

一.题目解析

我们不使用内置的函数进行升序,并且时间复杂度是O(nlog(n))

随机数的取值

我们不选中间值等的取值方法,完全随机取值效率更好,证明略

srand(time(NULL));//随机数种子 int getrandom(vector<int>& nums,int l,int r) { return nums[rand()%(r-l+1)+l]; }

算法一解析:分三组快速排序

选定一个关键数字key分为三组小于key的区间,等于key的区间,大于key的区间

怎么分呢?

再对左右区间进行排序,排序方法和第一步一样也就是递归实现,跟着代码走思路更加清晰

代码编写:

class Solution { public: vector<int> sortArray(vector<int>& nums) { srand(time(NULL));//随机数种子 int n=nums.size(); qsort(nums,0,n-1); return nums; } void qsort(vector<int>& nums,int l,int r) { if(l>=r)return ;//递归出口 int i=l,left=l-1,right=r+1; int key=getrandom(nums,l,r); while(i<right) { if(nums[i]<key) swap(nums[i++],nums[++left]); else if(nums[i]==key) i++; else swap(nums[i],nums[--right]); } //现在数组就分为了三组[l,left][left+1,right-1][right.r] qsort(nums,l,left);//左区间排序 qsort(nums,right,r);//右区间排序 return; } int getrandom(vector<int>& nums,int l,int r) { return nums[rand()%(r-l+1)+l]; } };

算法二:归并排序

将数组mid分成两部分,将左区间排序,将右区间排序,归并两个有序数组

具体就三步

1.mid分为两数组

2.左数组排序

3.右数组排序

4.合并两个有序数组

代码编写:

class Solution { public: vector<int> sortArray(vector<int>& nums) { mergesort(nums,0,nums.size()-1); return nums; } void mergesort(vector<int>& nums,int left,int right) { if(left>=right)return;//递归出口 int mid=left+(right-left)/2;//防止溢出 //区间变成了[left,mid][mid+1,right] //左右区间排序 mergesort(nums,left,mid); mergesort(nums,mid+1,right); //合并两个有序数组 vector<int>tmp(right-left+1); int cur1=left,cur2=mid+1,i=0; while(cur1<=mid&&cur2<=right) { if( nums[cur1]<=nums[cur2])tmp[i++]=nums[cur1++]; else tmp[i++]=nums[cur2++]; } while(cur1<=mid)//其中可能有一个数组更长 { tmp[i++]=nums[cur1++]; } while(cur2<=right) { tmp[i++]=nums[cur2++]; } //还原到nums中 for(int i=left;i<=right;i++) { nums[i]=tmp[i-left]; } } };