JAVA 데이터 구조 와 알고리즘 - 빠 른 정렬 1

      SunnyMoon 。

/**  
 *  
 * @author SunnyMoon  
 */  
////////////////////////////////////////////////////////////////////////////////   
/*******************************************************************************  
 *     ：  
 * *****************************************************************************  
 *   
 *     ：  
 *       ，         ，        ，           。  
 *   
 *     ：  
 *     ，                 。          。  
 *   
 *     ：  
 *            ，              ，        。  
 *   
 *     ：  
 *           ，           。                ，  
 *                  ，     。  
 *   
 *     ：  
 *          ，                 ，        。  
 *                             。  
 *        ：  
 * 1.                       。  
 * 2.              1  。  
 *                   ，       ，         。  
 *          ：  
 * O(N*logN)  
 *   
 *          ：  
 *                 。                     ，  
 *          ，                 ,  O(n2)。                。  
 *                      ，            。  
 */  
////////////////////////////////////////////////////////////////////////////////   
/**  
 *        ，           。  
 */  
class ArrayIns {   
  
    private long[] theArray;//       
    private int nElems;//           
  
    /**  
     *      
     * @param max  
     */  
    public ArrayIns(int max) {   
        theArray = new long[max];   
        nElems = 0;   
    }   
  
    /**  
     *        
     * @param value  
     */  
    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);   
    }   
    /**  
     *               
     * @param left  
     * @param right  
     */  
    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);   
        }   
    }   
  
    /**  
     *              
     * @param left  
     * @param right  
     * @param pivot  
     * @return  
     */  
    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;   
    }   
  
    /**  
     *               
     * @param dex1  
     * @param dex2  
     */  
    public void swap(int dex1, int dex2) {   
        long temp = theArray[dex1];   
        theArray[dex1] = theArray[dex2];   
        theArray[dex2] = temp;   
    }   
}   
/**  
 *          
 */  
public class QuickSort1 {   
  
    public static void main(String[] args) {   
        int maxSize = 16;   
        ArrayIns arr = new ArrayIns(maxSize);   
  
        for (int j = 0; j < maxSize; j++) {   
            long n = (int) (java.lang.Math.random()*99);   
            arr.insert(n);   
        }   
        System.out.println("       ");   
        arr.display();   
        arr.quickSort();   
        System.out.println("       ");   
        arr.display();   
    }   
}   
/**  
 *   
 *        ：  
 * A=9 14 33 27 66 89 53 32 72 14 46 33 13 79 28 26    
 *        ：   
 * A=9 13 14 14 26 27 28 32 33 33 46 53 66 72 79 89   
 */  
  
/**  
 *   ：  
 *                      。  
 *                   ，          ，         。  
 *                          。  
 */