# 快速排序以及使用快排找中位数

2015/09/21 23:57

####快速排序

java实现

    public void quickSort(long[] array, int begin, int end){
if (begin>=end)
return;
int b = begin;
int e = end;
long sentry = array[begin];
while(begin<end){
while (begin<end && array[end]>sentry) --end;
array[begin] = array[end];
while (begin<end && array[begin]<=sentry) ++begin;
array[end] = array[begin];
}
array[begin] = sentry;

quickSort(array, b, begin-1);
quickSort(array, begin+1, e);
}


    @Test
public void _median_(){
float[] medians = new float[]{1,2,3,4,5,6,7,8};
if ((medians.length&0x01) == 0){
median4even(medians, 0, medians.length-1);
}else{
median4odd(medians, 0, medians.length-1);
}
}

/**
* 奇数数组找中位数
* @param array
* @param low
* @param high
* @return
*/
public float median4odd(float[] array, int low, int high){

int pivot = xsort(array, low, high);

if (low<array.length/2)
return median4odd(array, pivot + 1, high);
if (low>array.length/2)
return median4odd(array, low, pivot - 1);
else return array[pivot];
}

/**
* 偶数数组去中位数
* @param array
* @param low
* @param high
* @return
*/
public float median4even(float[] array, int low, int high){
if (low>=high)
return (array[array.length/2]+array[array.length/2-1])/2;

int pivot = xsort(array, low, high);

if (low<=array.length/2-1)
return median4even(array, pivot + 1, high);
else
return median4even(array, low, pivot - 1);
}

/**
* 给定数组范围快速排序一次
* @param array
* @param low
* @param high
* @return
*/
public int xsort(float[] array, int low, int high){
float sentry = array[low];
while(low<high){
while (low<high && array[high]>sentry) --high;
array[low] = array[high];
while (low<high && array[low]<=sentry) ++low;
array[high] = array[low];
}
array[low] = sentry;
return low;
}


0
1 收藏

0 评论
1 收藏
0