class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // BubbleSort(nums);
        int n = nums.size();
        // merge(nums,0,n-1);
        // SelectSort(nums);
        quickSort(nums,0,n-1);
        return nums;
    }
    void BubbleSort(vector<int>& nums){
        int n = nums.size();
        for(int i = 0 ;i< n-1;i++){
            int flag = 0;
            for(int j = 0 ;j< n-i-1;j++){
                if(nums[j] > nums[j+1]){
                    int tmp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                    flag = 1;
                }
            }
            if(flag == 0) break;
        }
    }

    void merge(vector<int> & nums,int l,int r){
        if(l>=r) return ; //当两个指针重合时就不用在排了
        int mid = (l+r)>>1;
        merge(nums,l,mid);
        merge(nums,mid+1,r);
        vector<int> res(r-l+1);
        int k = 0;
        int i = l,j= mid+1;
        while(i<=mid && j<= r){
            if(nums[i] > nums[j]){
                res[k++] = nums[j++];
            }
            else res[k++] = nums[i++];
        }  //合并两个区间
        while(i <= mid) res[k++] = nums[i++];
        while(j <= r) res[k++] = nums[j++]; //把剩余部分复制进去
        i= l,k = 0;
        while(i<=r) nums[i++] = res[k++];//复制回原数组
    }

    void SelectSort(vector<int>& nums){
        int n  = nums.size();
        for(int i=  0 ;i <n ;i++){
            int min = i;
            for(int j = i+1;j< n; j++){
                if(nums[j] < nums[min]) min = j ;
            }
            if(min!=i) swap(nums[i],nums[min]); //找到最小的就分别和最前面的交换
        }
    }

    //快排

    int partition(vector<int>& nums,int low,int high){
        int pivot = nums[low];
        while(low < high){
            while(low < high && nums[high] >= pivot) high--;
            nums[low] = nums[high];
            while(low <high && nums[low] <= pivot) low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

    void quickSort(vector<int>& nums,int low,int high){
        int n = nums.size();
        if(low < high){
            int pivotpos = partition(nums,low,high);
            quickSort(nums,low,pivotpos-1);
            quickSort(nums,pivotpos+1,high);
        }
    }

    void insertSort(vector<int>& nums){
        int n  = nums.size();
        for(int i = 0 ; i< n;i++){
            int tmp = nums[i];   //这是一个哨兵，他的位置会空出来，他之前的比它大的会依次往后移动一个单位
            int j = i-1;
            while(j >=0 && nums[j] > tmp){
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = tmp;  //把哨兵放到正确位置
        }
    }
};