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

一.题目解析我们不使用内置的函数进行升序,并且时间复杂度是O(nlog(n))随机数的取值我们不选中间值等的取值方法,完全随机取值效率更好,证明略srand(time(NULL));//随机数种子 int getrandom(vectorint nums,int l,int r) { return nums[rand()%(r-l1)l]; }算法一解析:分三组快速排序选定一个关键数字key分为三组小于key的区间,等于key的区间,大于key的区间怎么分呢?再对左右区间进行排序,排序方法和第一步一样也就是递归实现,跟着代码走思路更加清晰代码编写:class Solution { public: vectorint sortArray(vectorint nums) { srand(time(NULL));//随机数种子 int nnums.size(); qsort(nums,0,n-1); return nums; } void qsort(vectorint nums,int l,int r) { if(lr)return ;//递归出口 int il,leftl-1,rightr1; int keygetrandom(nums,l,r); while(iright) { if(nums[i]key) swap(nums[i],nums[left]); else if(nums[i]key) i; else swap(nums[i],nums[--right]); } //现在数组就分为了三组[l,left][left1,right-1][right.r] qsort(nums,l,left);//左区间排序 qsort(nums,right,r);//右区间排序 return; } int getrandom(vectorint nums,int l,int r) { return nums[rand()%(r-l1)l]; } };算法二:归并排序将数组mid分成两部分,将左区间排序,将右区间排序,归并两个有序数组具体就三步1.mid分为两数组2.左数组排序3.右数组排序4.合并两个有序数组代码编写:class Solution { public: vectorint sortArray(vectorint nums) { mergesort(nums,0,nums.size()-1); return nums; } void mergesort(vectorint nums,int left,int right) { if(leftright)return;//递归出口 int midleft(right-left)/2;//防止溢出 //区间变成了[left,mid][mid1,right] //左右区间排序 mergesort(nums,left,mid); mergesort(nums,mid1,right); //合并两个有序数组 vectorinttmp(right-left1); int cur1left,cur2mid1,i0; while(cur1midcur2right) { if( nums[cur1]nums[cur2])tmp[i]nums[cur1]; else tmp[i]nums[cur2]; } while(cur1mid)//其中可能有一个数组更长 { tmp[i]nums[cur1]; } while(cur2right) { tmp[i]nums[cur2]; } //还原到nums中 for(int ileft;iright;i) { nums[i]tmp[i-left]; } } };