题解 | #排序#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        int size = arr.size();
        my_qsort(arr,0,size-1);
        return arr;
    }
    
    void exchange(int *p, int *q){
        int temp = *p;
        *p = *q;
        *q = temp;
    }
    
    void my_qsort(vector<int>& arr, int i, int j){
        int temp = arr[i];
        int start = i, end = j;
        //arr[i] = -1;
        if(i>=j) return;
        while(i<j){
            while(i<j&&arr[j]>temp){
                j--;
            }
            
            exchange(&arr[j], &arr[i]);
            i++;
            while(i<j&&arr[i]<temp){
                i++;
            }
            
            exchange(&arr[j], &arr[i]);
            j--;
        }
        arr[i] = temp;
        
        my_qsort(arr, start, i-1);
        my_qsort(arr, j+1, end);  
    }  
};