题解 | #快排2#

思路2：前后指针x和y，x向后，y向前，不符合顺序则交换。这样的代码比较简短。在递归左右部分的时候与partition版本不同。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    void quick_sort(vector<int>& arr,int left,int right){
        if(left>=right) return;
        int x=left;
        int y=right;
        int pivot=arr[left];
        while(x<=y){
            while(arr[x]<pivot) ++x;
            while(arr[y]>pivot) --y;
            if(x<=y){
                swap(arr[x],arr[y]);
                ++x; //下一个元素
                --y;
            }
        };
        quick_sort(arr,left,y);
        quick_sort(arr,x,right);
        return;
    }
    
    vector<int> MySort(vector<int>& arr) {
        // write code here
        quick_sort(arr,0,arr.size()-1);
        return arr;
    }
};