Java 区划排序

Java 划分排序

划分：

指定一个关键值key

从左右两边进行循环划分操作，将小于等于key的放左边，大于等于key的放右边

划分后的序列不一定全部有序

O(N)  只有一趟排序

/**
 * 划分 
 * 
 * @author stone
 * @date   2015-7-29 下午4:37:16
 */
public class Partition {
	
	public static void main(String[] args) {
		int[] ary = Util.generateIntArray(10);
		Util.printArray(ary);
		int pivot = 3;
		int partDex = sort(ary, 0, ary.length - 1, pivot);
		System.out.println("关键值是" + pivot + "，划分的index是" + partDex);
		Util.printArray(ary);
		
	}

	private static int sort(int[] ary, int left, int right, int pivot) {
		int leftPtr = left - 1;  //左边 再左一位   操作时需要先++
		int rightPtr = right + 1; //右边 再右一位  操作时需要先--
		while (true) {
			while (leftPtr < right && ary[++leftPtr] <= pivot); //leftPtr指向的项 > 关键值 停止
			while (rightPtr > left && ary[--rightPtr] >= pivot); //rightPtr指向的项 < 关键值 停止
			if (leftPtr >= rightPtr) {
				break;
			} else {
				//leftPtr rightPtr 指向的项所在的位置都不正确  应该交换
				swap(ary, leftPtr, rightPtr);
			}
			/*
			 *  继续下一次循环。 前面的错误位置的项已经交换了。 左右指针继续移动
			 */
		}
		System.out.println("l=" + leftPtr + ",r=" + rightPtr);
		return rightPtr;//返回 leftPtr也可以
	}

	private static void swap(int[] ary, int a, int b) {
		int temp = ary[a];
		ary[a] = ary[b];
		ary[b] = temp;
	}
}

输出

[2, 6, 9, 8, 4, 0, 5, 1, 7, 3]
l=3,r=2
关键值是3，划分的index是2
[2, 1, 0, 8, 4, 9, 5, 6, 7, 3]

结果：

在<=index 的位置 <key; 在>index的位置>=key

或

在<=index 的位置 <=key; 在>=index的位置>key