Quick Sort

http://www.lintcode.com/en/problem/sort-integers-ii/

code

class Solution {
public:
    /**
     * @param A an integer array
     * @return void
     */
    void sortIntegers2(vector<int>& A) {
        // Write your code here

        helper(A, 0, A.size()-1);

    }

    void helper(vector<int>& A, int s, int e)
    {
        if(s >= e)
        {
            return ;
        }

        int p = partition(A, s, e);
        helper(A, s, p-1);
        helper(A, p+1, e);
    }

    int partition(vector<int>& A, int s, int e)
    {
        int l = s;
        int r = e;
        int pivot = A[l];

        while(l<r)
        {
            while(l<r && A[r] >= pivot)
            {
                r--;
            }
            A[l] = A[r];

            while(l<r && A[l] <= pivot)
            {
                l++;
            }
            A[r] = A[l];
        }

        A[l] = pivot;
        return l;
    }
};