Partition函数

快排中核心的方法应该算是Partition函数了,它的作用就是将整个数组分成小于基准值的左边,和大于基准值的右边。

普通的Partition函数是这样的:

public static int partition1(int[] array,int lo,int hi){
//以第一个值为基准值,当然你也可以3取1,
int key=array[lo];
while(lo<hi){
while(array[hi]>key&&hi>lo){//从后半部分向前扫描
hi--;
}
array[lo]=array[hi];
while(array[lo]<=key&&hi>lo){//从前半部分向后扫描
lo++;
}
array[hi]=array[lo];
}
array[hi]=key;
return hi;
} public static void main(String[] args) {
int[] a = {34,2,25,1,12,34,12,56,23,15,34,67,89,54,34};
partition2(a, 0, 14);
for(int i=0; i<a.length; i++) {
System.err.print(a[i]+" ");
}
}
打印的结果是:
34 2 25 1 12 34 12 34 23 15 **34** 67 89 54 56 看出来没,大家都是相同的基准值34是各自分开的,我们希望得结果应该是这样的:
25 1 12 12 23 15 34 34 34 34 89 54 67 56
这样的好处是相同的值,在后续的遍历过程中,不用再比较一次了。

(左程云,左神写的)

牛逼的Partition函数是这样的:

public static int[] partition1(int[] arr, int begin, int end, int pivotValue) {
int small = begin - 1;
int cur = begin;
int big = end + 1;
while (cur != big) {
if (arr[cur] < pivotValue) {
swap(arr, ++small, cur++);
} else if (arr[cur] > pivotValue) {
swap(arr, cur, --big);
} else {
cur++;
}
}
int[] range = new int[2];
range[0] = small + 1;
range[1] = big - 1;
return range;
} public static void main(String[] args) {
int[] a = {34,2,25,1,12,34,12,56,23,15,34,67,89,54,34};
int[] b = partition1(a,0,14,34);
System.out.println(b[0]);
System.out.println(b[1]);
for(int i=0; i<a.length; i++) {
System.err.print(a[i]+" ");
}
}
输出的结果是:
7 //相同基准值的起始索引
10 //相同基准值的末尾索引
2 25 1 12 12 23 15 **34 34 34 34** 89 54 67 56 这样,你下一次递归直接就可以避免重复比较相同的基准值了。
上一篇:【AGC005F】Many Easy Problems (NTT)


下一篇:Python入门笔记(26):Python执行环境