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

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

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

提示：
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        //bubbleSort(nums);
        
        //selectionSort(nums);
        
        //InsertionSort(nums);
        
        //ShellSort(nums);
        
        //return mergeSort(nums);
        
        //quickSort(nums,0,nums.size()-1);

        heapSort(nums);
        
        return nums;
    }

    // 冒泡排序 O(n²)
    void bubbleSort(vector<int>& nums){
        for(int i=nums.size()-1;i>0;i--)
            for(int j=0;j<i;j++){
                if(nums[j]>nums[j+1])
                    swap(nums[j],nums[j+1]);
            }
    }

    // 选择排序 O(n²)
    void selectionSort(vector<int>& nums){
        for(int i=nums.size()-1;i>0;i--){
            int maxSub=0;
            for(int j=1;j<=i;j++){
                if(nums[j]>nums[maxSub])
                    maxSub=j;
            }
            swap(nums[i],nums[maxSub]);
        }
            
    }

    // 插入排序 O(n²)
    void InsertionSort(vector<int>& nums){
        for(int i=1;i<nums.size();i++){
            int pos=i;
            int curVal = nums[i];
            while(pos>0 && nums[pos-1]>curVal){
                nums[pos]=nums[pos-1];
                pos--;
            }
            nums[pos]=curVal;     
        }
    }

    //希尔排序 O(nlogn) 
    void ShellSort(vector<int>& nums){      
        for(int gap = nums.size()/2; gap>0; gap/=2)
            for(int i=gap; i<nums.size();i++){
                int curVal = nums[i];
                int pos=i;
                while(pos>=gap && nums[pos-gap]>curVal){
                    nums[pos]=nums[pos-gap];
                    pos-=gap;
                }
                nums[pos]=curVal;
            }
    }
    // 归并排序 O(nlogn)  
    vector<int> mergeSort(vector<int> nums){  
        if(nums.size()<2)
            return nums;

        int l=0,r=nums.size()-1;
        int mid=(l+r)/2;
        vector<int> left = mergeSort(vector<int>(nums.begin(),nums.begin()+mid+1));
        vector<int> right= mergeSort(vector<int>(nums.begin()+mid+1,nums.end()));

        int i=0,j=0;
        vector<int> res;
        while(i<left.size() && j<right.size()){
            if(left[i]<right[j]){
                res.push_back(left[i]);
                i++;
            }
            else{
                res.push_back(right[j]);
                j++;
            }          
        }

        if(i<left.size())
            res.insert(res.end(),left.begin()+i,left.end());
        else if(j<right.size())
            res.insert(res.end(),right.begin()+j,right.end()); 
        return res; 
    }   

    // 快速排序 O(nlogn)  
    void quickSort(vector<int>& nums, int l,int r){
        if(l>=r)
            return;
        // 不随机会超时
        swap(nums[l], nums[rand() % (r - l + 1) + l]);
        int pivot=nums[l];
        int i=l+1, j=r;
        while(i<=j){
            while(i<=j && nums[i]<=pivot)
                i++;
            while(i<=j && nums[j]>=pivot)
                j--;
            if(j<i) break;
            swap(nums[i],nums[j]);
         }
         swap(nums[j],nums[l]);

         quickSort(nums,l,j-1);
         quickSort(nums,j+1,r);

      }

      // 堆排序 O(nlogn) 
      void heapSort(vector<int>& nums){
          int len=nums.size();
        for(int i=len/2-1; i>=0;i-- )
            MaxHeapify(nums, len, i);

        for(int i=len-1;i>0;i--){
            swap(nums[0],nums[i]);
            MaxHeapify(nums,i, 0);
        }
      }

      //堆调整
      void MaxHeapify(vector<int>& nums,int len,int index){
        int lc=2*index+1;
        int rc=2*index+2;
        int largest=index;

        if(lc<len && nums[lc]>nums[largest])
            largest=lc;
        if(rc<len && nums[rc]>nums[largest])
            largest=rc;

        if(largest!=index){
            swap(nums[index],nums[largest]);
            MaxHeapify(nums, len, largest);
        }
      }
    
};