LeetCode c++ 排序数组

全部基于LeetCode上编程题排序数组
1.快速排序：
每次排序后，对于基准数，他前面的一定比它小，后面的一定比它大。

class Solution {
public:
    void Qsort(vector<int>& nums,int low,int high){
        int pivot;
        if(low<high){
            pivot=Partition(nums,low,high);
            Qsort(nums,low,pivot-1);
            Qsort(nums,pivot+1,high);
        }
    }
    int Partition(vector<int>& nums,int low,int high){
        int pivotkey;
        pivotkey=nums[low];
        while(low<high){
            while(low<high&&nums[high]>=pivotkey)
                high--;
            nums[low]=nums[high];
            nums[high]=pivotkey;
            while(low<high&&nums[low]<=pivotkey)
                low++;
            nums[high]=nums[low];
            nums[low]=pivotkey;
        }
        return high;
    }
    vector<int> sortArray(vector<int>& nums) {
        Qsort(nums,0,nums.size()-1);
        return nums;
    }
};

2.插入排序
注：算法实现中，需要考虑每次如果当前数比之前数大是否已比较到第0位，如果已到达，需要直接将nums[0]置为temp！
在leetcode只有最后一组数超出时间限制，不可行，说明时间复杂度相对较高。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int temp;
        for(int i=1;i<nums.size();i++){
            temp=nums[i];
            for(int j=i-1;j>=0;j--){
                if(temp<nums[j]){
                    nums[j+1]=nums[j];
                    if(j==0)
                        nums[0]=temp;
                }
                else{
                    nums[j+1]=temp;
                    break;
                }
                
            }
            cout<<nums[0]<<endl;
        }
        return nums;
    }
};

3.希尔排序-直接插入排序的优化
gap=gap/3+1//增量设定

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int len=nums.size();
        int gap=len;
        while(gap > 1){   
            gap = gap/3 + 1;
            for(int i = gap;i < len;i++){   
                int key = nums[i];
                int start = i - gap;
                while(start >= 0 && key <= nums[start]){   
                    nums[start+gap] = nums[start];
                    start -= gap;
                }   
                nums[start + gap] = key;
            }   
        }   
        return nums;
    }
};

4.简单选择排序
每次选择最大值放入后面正确位置，同样超出限制时间

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int temp;
        int index;
        for(int i=0;i<nums.size()-1;i++){
            temp=nums[0];
            index=0;
            for(int j=0;j<nums.size()-i;j++){
                if(nums[j]>temp){
                    temp=nums[j];
                    index=j;
                }
                
            }
            // cout<<temp<<endl;
            // cout<<index<<endl;
            nums[index]=nums[nums.size()-i-1];
            nums[nums.size()-i-1]=temp;
            // cout<<nums[nums.size()-i-1]<<endl;
        }
        return nums;
    }    
};

5.冒泡排序
每两个进行比较，顺序不符则交换，每次最大值排在正确位置。
要注意设置i、j上限。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int temp;
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<nums.size()-i-1;j++){
                if(nums[j]>nums[j+1]){
                    temp=nums[j+1];
                    nums[j+1]=nums[j];
                    nums[j]=temp;
                }
            }
        }
        return nums;
    }
};

6.堆排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        //堆排序
        heapSort(nums,nums.size());
        return nums;
    }
    void heapSort(vector<int>& nums,int len){
        //构建大顶堆
        for(int i=len/2-1;i>=0;i--){
            adjust(nums,len,i);
        }
        //调整大顶堆
        for(int i=len-1;i>=1;i--){
            swap(nums[0],nums[i]);
            adjust(nums,i,0);
        }
    }
    
    void adjust(vector<int>& nums,int len,int index){
        int left=index*2+1;
        int right=index*2+2;
        int maxInd=index;
        if(left<len&&nums[left]>nums[maxInd])maxInd=left;
        if(right<len&&nums[right]>nums[maxInd])maxInd=right;
        if(maxInd!=index){
            swap(nums[maxInd],nums[index]);
            adjust(nums,len,maxInd);
        }
    }
    
};

7.归并排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums,0,nums.size()-1); 
        return nums;
    }
    void mergeSort(vector<int>& nums,int i,int j){
        if(i>=j)
            return;
        int mid=i+(j-i)/2;
        mergeSort(nums,i,mid);
        mergeSort(nums,mid+1,j);
        merge(nums,i,mid,j);
    }
    void merge(vector<int> &nums,int i,int mid,int j){
        vector<int> res;
        int l=i,r=mid+1;
        while(l<=mid&&r<=j){
            if(nums[l]<=nums[r])
                res.push_back(nums[l++]);
            else
                res.push_back(nums[r++]);
        }
        if(l>mid&&r<=j)
            while(r<=j)
                res.push_back(nums[r++]);
        else if(r>j&&l<=mid)
            while(l<=mid)
                res.push_back(nums[l++]);
        
        for(int ok=i,oo=0;ok<=j;ok++,oo++){
            nums[ok]=res[oo];
        }
    }
};