当前位置: 代码迷 >> J2SE >> 请问怎么统计快速排序选择了多少次基准值(pivot)
  详细解决方案

请问怎么统计快速排序选择了多少次基准值(pivot)

热度:323   发布时间:2016-04-24 01:29:28.0
请教如何统计快速排序选择了多少次基准值(pivot)?
这是小弟的程序,一个以中间数(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
  相关解决方案