这是小弟的程序,一个以中间数(median of three)为基准的快速排序
- Java code
public class pivot{ final static int CUTOFF = 10; public static void main(String[] args){ int[] numbers = {18,100,84,75,95,54,55,30}; quickSort(numbers); for(int element:numbers){ System.out.println(element); } } private static void quickSort(int[] a){ quickSort(a,0,a.length-1); } private static void quickSort(int[] a, int lo, int hi){ if(lo + CUTOFF > hi){ insertionSort(a,lo,hi); }else{ int mi = (lo+hi)/2; if(a[mi]<a[lo]) swap(a,lo,mi); if(a[hi]<a[lo]) swap(a,lo,hi); if(a[hi]<a[mi]) swap(a,mi,hi); swap(a,mi,hi-1); int p = a[hi-1]; int i,j; for(i=lo,j=hi-1; ; ){ while(a[++i]<p); while(p<a[--j]); if(i<j) swap(a,i,j); else break; } swap(a,i,hi-1); quickSort(a,lo,i-1); quickSort(a,i+1,hi); } } private static void swap(int[] a, int i, int j){ int tmp = a[i]; a[i]=a[j]; a[j]=tmp; } private static void insertionSort(int[] a,int lo,int hi){ if(lo>hi||lo<0||hi>=a.length){ lo = 0; hi = a.length-1; } for(int i=lo+1;i<=hi;i++){ int tmp = a[i]; int k = i-1; while(k>=lo&&tmp<a[k]){ a[k+1]=a[k]; k--; } a[k+1]=tmp; } }}
现在求高人指点一下该如何得到选择基准的次数
譬如说我程序里的数组是18,100,84,75,95,54,55,30。
选择第一次基准,也就是第3个值75,排序的结果是18 30 55 54 75 100 84 95
然后75左边和右边的子数组各选择一次基准,分别是30和84,排序的结果是18 30 54 55 75 84 100 95
然后剩下18;54和55;100和95未排序,如果比较的数组元素不足3个,就只作简单的排序,不计入基准的次数
所以对这个数组排序共选择了3次基准,分别是75,30和84。而小弟想要的就是共选择了多少次基准(在这个例子里是3次),如果可以的话,连基准本身也求出来
谢谢大家了
------解决方案--------------------
把CUTOFF改成2,然后声明一个int count,每次进行基准计算时加1