[数据结构与算法]十大排序算法

快排

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;
    }
};