[数据结构与算法]力扣912.排序数组（十大排序算法走一遍101℃）=十大模板

力扣912.排序数组
给你一个整数数组 nums，请你将该数组升序排列。

示例一：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例二：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

解法一：STL，sort直接排

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    return nums;
    }
};

解法二：选择排序

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

解法三:冒泡排序

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

解法三：插入排序

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

解法四：快速排序

class Solution {
public:
void qssort(vector<int>&nums,int l,int r){
   int i=l,j=r,flag=nums[l+(r-l)/2];
   do{
       while(nums[i]<flag)i++;
       while(nums[j]>flag)j--;
       if(i<=j){
           swap(nums[i],nums[j]);
           i++;
           j--;
       }
   }while(i<=j);
   if(l<j)qssort(nums,l,j);
   if(i<r)qssort(nums,i,r);
}
    vector<int> sortArray(vector<int>& nums) {
    int n=nums.size();
    qssort(nums,0,n-1);
    return nums;
    }
};

快排还是很强的

解法五：希尔排序

class Solution {
public:
 void shellsort(vector<int>& nums) {
    int n=nums.size();
    for(int inc=n/2;inc>=1;inc/=2){
        for(int k=0;k<=inc-1;k++){
            for(int j=k+inc;j<n;j+=inc){
                int i=j-inc;
                int tmp=nums[j];
                while(i>=k&&nums[i]>tmp){
                    nums[i+inc]=nums[i];
                    i-=inc;
                }
                nums[i+inc]=tmp;
            }
        }
    }
} 
vector<int> sortArray(vector<int>& nums) {
    int n=nums.size();
    shellsort(nums);
    return nums;
    }
};

解法六：归并排序

class Solution {
public:
void mergesort(vector<int>&nums,int beg,int end){
        if(beg>=end)return;
        int mid=beg+(end-beg)/2;
        mergesort(nums,beg,mid);
        mergesort(nums,mid+1,end);
        vector<int>nums2(nums.begin()+mid+1,nums.begin()+end+1);
        merge(nums,beg,mid,end,nums2,end-mid);
    }
void merge(vector<int>&nums1,int beg,int mid,int end,vector<int>&nums2,int n){
        int right=end+1,cur1=mid,cur2=n-1;
        while(1){
            if(cur1==beg-1&&cur2==-1)return ;
            else if(cur1==beg-1&&cur2!=-1){
                right--;
                nums1[right]=nums2[cur2];
                cur2--;
            }
            else if(cur1!=beg-1&&cur2==-1)return ;
            else if(nums1[cur1]>=nums2[cur2]){
                right--;
                nums1[right]=nums1[cur1];
                cur1--;
            }
            else if(nums1[cur1]<nums2[cur2]){
                right--;
                nums1[right]=nums2[cur2];
                cur2--;
            }
        }
    }
vector<int> sortArray(vector<int>& nums) {
    int n=nums.size();
    mergesort(nums,0,n-1);
    return nums;
    }
};

解法七：堆排序

解法八：计数排序

解法九：基数排序

解法十：桶排序

解法：十一：我先休息一下<(＿　＿)>