/*
    
    * 快速排序是最流行的排序算法，本质上通过把一个数组划分为两个子数组，
    
    * 然后递归地调用自身为每一个子数组进行快速排序来实现。
    
    * ArrayIns.java
    
    * linzhanghui@gmail.com
    
    */
    
    package linzhanghui.quicksort;
    
    public class ArrayIns {
    
    private long[] theArray;
    
    private int nElems;
    
    public ArrayIns（int max） {
    
    theArray = new long[max];
    
    nElems = 0;
    
    }
    
    public void insert（long value） {
    
    theArray[nElems] = value;
    
    nElems++;
    
    }
    
    public void display（） {
    
    System.out.print（"A="）；
    
    for（int j=0; j<nElems; j++）
    
    System.out.print（theArray[j] + " "）；
    
    System.out.println（""）；
    
    }
    
    public void quickSort（） {
    
    recQuickSort（0, nElems-1）；
    
    }
    
    public void recQuickSort（int left, int right） {
    
    if（right-left <= 0）
    
    return;
    
    else {
    
    long pivot = theArray[right];
    
    int partition = partitionIt（left, right, pivot）；
    
    recQuickSort（left, partition-1）；
    
    recQuickSort（partition+1, right）；
    
    }
    
    }
    
    public int partitionIt（int left, int right, long pivot） {
    
    int leftPtr = left-1;
    
    int rightPtr = right;
    
    while（true） {
    
    while（ theArray[++leftPtr] < pivot）
    
    ;
    
    while（rightPtr > 0 && theArray[--rightPtr] > pivot）
    
    ;
    
    if（leftPtr >= rightPtr）
    
    break;
    
    else
    
    swap（leftPtr, rightPtr）；
    
    }
    
    swap（leftPtr, right）；
    
    return leftPtr;
    
    }
    
    public void swap（int dex1, int dex2） {
    
    long temp = theArray[dex1];
    
    theArray[dex1] = theArray[dex2];
    
    theArray[dex2] = temp;
    
    }
    
    }
    
    /*
    
    * 程序随机产生16个2位随机数，显示这16个随机数后，对其进行快速排序并输出。
    
    * linzhanghui@gmail.com
    
    */
    
    package linzhanghui.quicksort;
    
    public class QuickSortApp {
    
    public static void main（String[] args） {
    
    int maxSize = 16;
    
    ArrayIns arr;
    
    arr = new ArrayIns（maxSize）；
    
    for（int j=0; j<maxSize; j++） {
    
    long n = （int）（java.lang.Math.random（）*99）；
    
    arr.insert（n）；
    
    }
    
    arr.display（）；
    
    arr.quickSort（）；
    
    arr.display（）；
    
    }
    
    }
//java/4486