没有登录
中国开发网: 论坛: 程序员情感CBD: 贴子 236073
nostalgic: 有这种需求吗?这是啥子算法
package partition;

////////////////////////////////////////////////////////////////
class ArrayPar
{
private long[] theArray; // ref to array theArray
private int nElems; // number of data items
//--------------------------------------------------------------
public ArrayPar(int max) // constructor
{
theArray = new long[max]; // create the array
nElems = 0; // no items yet
}
//--------------------------------------------------------------
public void insert(long value) // put element into array
{
theArray[nElems] = value; // insert it
nElems++; // increment size
}
//--------------------------------------------------------------
public int size() // return number of items
{ return nElems; }
//--------------------------------------------------------------
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 it
System.out.println("");
}
//--------------------------------------------------------------
public int partitionIt(int left, int right, long pivot)
{
int leftPtr = left - 1; // right of first elem
int rightPtr = right + 1; // left of pivot
while(true)
{
while(leftPtr < right && // find bigger item
theArray[++leftPtr] < pivot)
; // (nop)

while(rightPtr > left && // find smaller item
theArray[--rightPtr] > pivot)
; // (nop)
if(leftPtr >= rightPtr) // if pointers cross,
break; // partition done
else // not crossed, so
swap(leftPtr, rightPtr); // swap elements
} // end while(true)
return leftPtr; // return partition
} // end partitionIt()
//--------------------------------------------------------------
public void swap(int dex1, int dex2) // swap two elements
{
long temp;
temp = theArray[dex1]; // A into temp
theArray[dex1] = theArray[dex2]; // B into A
theArray[dex2] = temp; // temp into B
} // end swap()
//--------------------------------------------------------------
} // end class ArrayPar
////////////////////////////////////////////////////////////////
public class PartitionApp
{
public static void main(String[] args)
{
int maxSize = 16; // array size
ArrayPar arr; // reference to array
arr = new ArrayPar(maxSize); // create the array

for(int j=0; j<maxSize; j++) // fill array with
{ // random numbers
long n = (int)(java.lang.Math.random()*199);
arr.insert(n);
}
arr.display(); // display unsorted array

long pivot = 99; // pivot value
System.out.print("Pivot is " + pivot);
int size = arr.size();
// partition array
int partDex = arr.partitionIt(0, size-1, pivot);

System.out.println(", Partition is at index " + partDex);
arr.display(); // display partitioned array
} // end main()
} // end class PartitionApp

相关信息:


欢迎光临本社区,您还没有登录,不能发贴子。请在 这里登录