Quick sort

思路：
在partition的时候，可以只用一个指针。详见：https://visualgo.net/en/sorting
代码如下：

 public class Solution {  
   /*  
    * @param A: an integer array  
    * @return:   
    */  
   public void sortIntegers(int[] A) {  
     // write your code here  
     quickSort(A, 0, A.length - 1);  
   }  
   private void quickSort(int[] A, int start, int end) {  
     if(start < end)  
     {  
       int pivot = partition(A, start, end);  
     // since A[pivot] is at sorted poisition, exclude pivot.   
       quickSort(A, start, pivot - 1);  
       quickSort(A, pivot + 1, end);  
     }  
   }  
   private int partition(int[] A, int start, int end) {  
     int pivotValue = A[start];  
     int storeIndex = start + 1;  
     for(int i = start + 1; i <= end; i++) {  
       // put value less then pivotValue to left  
       if(A[i] < pivotValue) {  
         swap(A, storeIndex++, i);  
       }  
     }  
     // place the pivot in the middle  
     swap(A, start, storeIndex - 1);  
     // return the new pivot index  
     return storeIndex - 1;  
   }  
   private void swap(int[] A, int left, int right) {  
         int temp = A[left];  
         A[left] = A[right];  
         A[right] = temp;  
   }  
 }  

在partition的时候，storeIndex指向比pivot大的起始点。最后一步swap, 形成了一个局部sorted array:[numbers < pivot],  pivot, [numbers >  pivot]。

极端情况会出现, start == end, start < end, 需要排除掉。