（十五）高级排序—划分算法

一、 划分算法描述

1. 划分就是将数据项分成两组，一组大于某个特定的数据项，而另一组小于某个特定的数据项。在划分算法中，这个特定的数据项叫做枢纽。

2. 如下图所示：划分算法的思想是：中间的横线代表枢纽；数据项的左端和右端分别有两个指针（leftPtr和rightPtr）；leftPtr从左向右遍历元素，rightPtr从右向左遍历元素，当leftPtr遇到比枢纽元素大的元素时停止，当rightPtr遇到比枢纽元素小的元素时停止，然后将这两个元素交换位置；接下来，leftPtr继续向右遍历，rightPtr继续向左遍历，重复上面的操作；当两个指针相遇时遍历结束。

二、 Java语言描述划分算法

package com.solid.sort;

public class Partition {

//定义数组

private int[] arr;

private static int nElems;

/**

* 构造方法

* @param maxSize

*/

public Partition(int maxSize) {

arr = new int[maxSize];

nElems = 0;

}

/**

* 数组中插入元素

* @param key

*/

public void insert(int key) {

arr[nElems++] = key;

}

/**

* 遍历数组中的所有元素

*/

public void display() {

for(int i=0; i<nElems; i++) {

System.out.print(arr[i] + " ");

}

System.out.println();

}

/**

* 划分算法

* @param left

* @param right

* @param pivot

* @return

*/

public int partitionIt(int left, int right, int pivot) {

int leftPtr = left - 1;

int rightPtr = right + 1;

while(true) {

while(leftPtr < right && arr[++leftPtr] < pivot)

;

while(rightPtr > left && arr[--rightPtr] > pivot)

;

if(leftPtr >= rightPtr) {

break;

} else {

int temp = arr[leftPtr];

arr[leftPtr] = arr[rightPtr];

arr[rightPtr] = temp;

}

}

return leftPtr;

}

/**

* 测试main方法

* @param args

*/

public static void main(String[] args) {

Partition partition = new Partition(100);

partition.insert(15);

partition.insert(30);

partition.insert(65);

partition.insert(70);

partition.insert(18);

partition.insert(75);

partition.insert(55);

partition.insert(40);

partition.display();

System.out.println("pivot at index:" + partition.partitionIt(0, nElems-1, 50));

partition.display();

}

}