leetcode 628. 三个数的最大乘积

使用归并排序和快速排序：时间复杂度为O(nlogn)，快排132ms，归并880ms，stl 的sort() 80ms

考虑到负数，最大值有两种情况：两个负数一个正数相乘，或者三个正数相乘，取两个的最大值

class Solution {
public:
    int findpivot(vector<int>&nums,int start,int end){
        int pivot=nums[start];
        int i=start,j=end;
        while(i<j){
            while(i<j&&nums[j]>=pivot)
                j--;
            nums[i]=nums[j];
            while(i<j&&nums[i]<=pivot)
                i++;
            nums[j]=nums[i];
        }
        nums[i]=pivot;
        return i;
    }
    void quicksort(vector<int>&nums,int start,int end){
        if(start>=end) return;
        int pivotkey=findpivot(nums,start,end);
        quicksort(nums,start,pivotkey-1);
        quicksort(nums,pivotkey+1,end);
    }
    
    
    void merge(vector<int>&nums,int start,int mid,int end){
        vector<int> tmp;
        int i=start,j=mid+1;
        while(i<=mid&&j<=end){
            if(nums[i]<nums[j]){
                tmp.push_back(nums[i++]);
            }else{
                tmp.push_back(nums[j++]);
            }
        }
        while(i<=mid){
            tmp.push_back(nums[i++]);
        }
        while(j<=end){
            tmp.push_back(nums[j++]);
        }
        for(int k=0;k<tmp.size();k++){
            nums[start+k]=tmp[k];
        }
    }
    void mergesort(vector<int>&nums,int start,int end){
        if(start==end) return;
        int mid=(end-start)/2+start;
        mergesort(nums,start,mid);
        mergesort(nums,mid+1,end);
        merge(nums,start,mid,end);
    }
    int maximumProduct(vector<int>& nums) {
        int len=nums.size();
        if(len<3) return 0;
        //mergesort(nums,0,len-1);
        quicksort(nums,0,len-1);
        //sort(nums.begin(),nums.end());
        return max(nums[0]*nums[1]*nums[len-1],nums[len-3]*nums[len-2]*nums[len-1]);
    }
    
};