详解快速排序算法中的区间划分法及Java实现示例

详解快速排序算法中的区间划分法及Java实现示例

初始时，left = 0; rwAeQHwight= 9;   X = a[left] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从right开始向前找一个<=X的数。显然,right=8时，符合条件，将a[8]挖出再填到上一个坑a[left]中。 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从left开始向后找一个大于X的数，当left=3，符合条件，将a[3]挖出再填到上一个坑a[right] 中;

数组变为：

public class Partition {

/**

* 基于base划分，小的在左，大的在右， 不要求整个序列有序

*

* @param wAeQHwary

* @param base

*/

static void sort(int[] ary, int base) {http://

int left = 0;

int right = ary.length - 1;

int leftpoint = left, rightpoint = right;

while (true) {

// 分成左右两边同时进行比较，一边从左向右，一边从右向左，

while (leftpoint < right && ary[leftpoint++] < base); //leftpoint大于right或ary[leftpoint]>base停止循环

while (rightpoint >= left && ary[rightpoint--] > base); //反之

System.out.println("左边需要交换的索引:" + (leftpoint-1));

System.out.println("右边需要交换的索引:"+ (rightpoint+1));

//上面拿到了不符合条件的两个索引，即需要交换的两个索引

if (leftpoint - 1 < rightpoint + 1) {//需要交换

swap(ary, leftpoint - 1, rightpoint + 1);

Util.printArray(ary);

leftpoint = left;

rightpoint = right;

} else {

break;

}

}

}

private static void swap(int[] ary, int a, int b) {

int temp = ary[a];

ary[a] = ary[b];

ary[b] = temp;

}

public static void main(String[] args) {

int[] ary = Util.generateIntArray(10);

System.out.println("原序列：");

Util.printArray(ary);

sort(ary, 5);

System.out.println("排序后：");

Util.printArray(ary);

}

}

结果：

原序列：

[2, 8, 4, 3, 7, 5, 1, 9, 0, 6]

左边需要交换的索引:1

右边需要交换的索引:8

[2, 0, 4, 3, 7, 5, 1, 9, 8, 6]

左边需要交换的索引:4

右边需要交换的索引:6

[2, 0, 4, 3, 1, 5, 7, 9, 8, 6]

左边需要交换的索引:5

右边需要交换的索引:5

排序后：

[2, 0, 4, 3, 1, 5, 7, 9, 8, 6]

区间划分的的另一种指导思维:

将数组的第一个元素作为区间划分值，从第二个元素开始分区，直到形成如图所示的结果，

然后交换l

如此，可以如下编写快速排序代码：

public void qSort(int array[],int left,int right)

{

if(left < right){

int key = array[left];

int high = right;

int low = left+1;

while(true){

while(low <= high && array[low] <= key) low++;

while(low <= high && array[high] >= key) high--;

if(low > high)

break;

swap(array,low,high);

}

swap(array,left,high);

printArray(array);

qSort(array,left,high-1);

qSort(array,high+1,right);

}

}

如此，可以如下编写快速排序代码：

public void qSort(int array[],int left,int right)

{

if(left < right){

int key = array[left];

int high = right;

int low = left+1;

while(true){

while(low <= high && array[low] <= key) low++;

while(low <= high && array[high] >= key) high--;

if(low > high)

break;

swap(array,low,high);

}

swap(array,left,high);

printArray(array);

qSort(array,left,high-1);

qSort(array,high+1,right);

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。