以一个枢纽值二分一个数组
划分算法由两个指针开始，分别指向数组的两头。在左边的指针向右移动，右边的指针向左移动。左边的指针leftPtr初始化为第一个数据项，右边的指针rightPtr初始化为数组的最后一项。算法如下：?
import java.util.Random;public class Partition { private long[] theArr; private int nElems; public Partition(int max) { theArr = new long; nElems = 0; } public void insert(long value) { theArr = value; } public int size() { return nElems; } public void display() { System.out.print("A = "); for (int j = 0; j < nElems; j++) { System.out.print(theArr + " "); } System.out.println(); } public int partitionIt(int left, int right, long pivot) { int leftPtr = left - 1; int rightPtr = right + 1; while (true) { // keep moving to right until current value is larger than pivot while (leftPtr < right &amp;&amp; theArr[++leftPtr] < pivot) { // } // keep moving to left until current value is smaller than pivot while (rightPtr > left &amp;&amp; theArr[--rightPtr] > pivot) { // } // if left pointer meet the right pointer, break if (leftPtr >= rightPtr) { break; } else { swap(leftPtr, rightPtr); } } // return pivot position return leftPtr; } public void swap(int dex1, int dex2) { long temp = theArr; theArr = theArr; theArr = temp; }}
?
end.
页:
[1]