快速排序1

package com.pskfire.example;// quickSort1.java// demonstrates simple version of quick sort// to run this program: C>java QuickSort1App////////////////////////////////////////////////////////////////class ArrayIns {private long[] theArray; // ref to array theArrayprivate int nElems; // number of data items// --------------------------public ArrayIns(int max) // constructor{theArray = new long[max]; // create the arraynElems = 0; // no items yet}// --------------------------public void insert(long value) // put element into array{theArray[nElems] = value; // insert itnElems++; // increment size}// --------------------------public void display() // displays array contents{System.out.print("A=");for (int j = 0; j < nElems; j++)// for each element,System.out.print(theArray[j] + " "); // display itSystem.out.println("");}// --------------------------public void quickSort() {recQuickSort(0, nElems - 1);}// --------------------------public void recQuickSort(int left, int right) {if (right - left <= 0) // if size <= 1,return; // already sortedelse // size is 2 or larger{long pivot = theArray[right]; // rightmost item// partition rangeint partition = partitionIt(left, right, pivot);recQuickSort(left, partition - 1); // sort left siderecQuickSort(partition + 1, right); // sort right side}} // end recQuickSort()// --------------------------public int partitionIt(int left, int right, long pivot) {int leftPtr = left - 1; // left (after ++)int rightPtr = right; // right-1 (after --)while (true) { // find bigger itemwhile (theArray[++leftPtr] < pivot); // (nop)// find smaller itemwhile (rightPtr > 0 && theArray[--rightPtr] > pivot); // (nop)if (leftPtr >= rightPtr) // if pointers cross,break; // partition doneelse// not crossed, soswap(leftPtr, rightPtr); // swap elements} // end while(true)swap(leftPtr, right); // restore pivotreturn leftPtr; // return pivot location} // end partitionIt()// --------------------------public void swap(int dex1, int dex2) // swap two elements{long temp = theArray[dex1]; // A into temptheArray[dex1] = theArray[dex2]; // B into AtheArray[dex2] = temp; // temp into B} // end swap(// --------------------------} // end class ArrayIns// //////////////////////////////////////////////////////////////class QuickSort1App {public static void main(String[] args) {int maxSize = 16; // array sizeArrayIns arr;arr = new ArrayIns(maxSize); // create arrayfor (int j = 0; j < maxSize; j++) // fill array with{ // random numberslong n = (int) (java.lang.Math.random() * 99);arr.insert(n);}arr.display(); // display itemsarr.quickSort(); // quicksort themarr.display(); // display them again} // end main()} // end class QuickSort1App// //////////////////////////////////////////////////////////////