快排以及快排的中位数算法

1、快排算法 java

/**
 * quicksort to sort array
 *
 */
public class QuickSort {
	int partition(double a[], int low, int high) {
		double tmp = a[low];
		int i = low, j = high;
		while (i < j) {
			while (i < j && a[j] >= tmp){
				j--;
			}
			while (i < j && a[i] <= tmp){
				i++;
			}
			swap(a, i, j);
		}
		a[low] = a[i];
		a[i] = tmp;
		return i;
	}

	void swap(double a[], int i, int j) {
		double tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}

	void quickSort(double a[], int low, int high) {
		if (low < high) {
			int pos = partition(a, low, high);
			quickSort(a, low, pos - 1);
			quickSort(a, pos + 1, high);
		}
	}
	public static void main(String[] args) {
		QuickSort test = new QuickSort();
		double a[] = {1d, 10d, 7d,9d,11d,1d,50d,3d};
		test.quickSort(a, 0, a.length - 1);
		System.out.println(a);
	}
}

 

2、求中位数算法

/**
 * 快排找中位数
 * 思想:转化成找第K小的数 k = array.length / 2 + 1
 * partition分成两边后
 * 1、左边个数>K，则继续在左边找
 * 2、左边个数<K，则在右边找，此时newK = oldK - 左边个数
 * 3、当相等时，则partition得到的pos即是中位数，这种情况分成奇偶两种情况
 * a、奇数时直接返回
 * b、偶数时要找到该中位数左边区域的最大值
 * 最大值分两种情况：
 * 1、该中位数所在迭代中左边还有数，则取左边的最大值
 * 2、该中位数所在迭代中左边无值，则取上回分裂中将该中位数分到右边的分裂点，即程序中的prePart
 *
 */
public class QuieckSortMedium {
	private boolean bOdd;//是否奇偶数
	private int kv;//k值
	private double medium;
	int partition(double a[], int low, int high) {
		double tmp = a[low];
		int i = low, j = high;
		while (i < j) {
			while (i < j && a[j] >= tmp){
				j--;
			}
			while (i < j && a[i] <= tmp){
				i++;
			}
			swap(a, i, j);
		}
		a[low] = a[i];
		a[i] = tmp;
		return i;
	}

	void swap(double a[], int i, int j) {
		if(i == j){
			return;
		}
		double tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	void findMedium(double a[]){
		bOdd = a.length % 2 == 0;
		kv = a.length / 2 + 1;
		medium = 0;
		findK(a, 0, a.length - 1, kv, -1);
	}
	
	/**
	 * 需求第K小
	 * @param a
	 * @param low
	 * @param high
	 * @param k
	 * @param prePart  上回分裂中将该中位数分到右边的分裂点
	 */
	void findK(double a[], int low, int high, int k, int prePart){
		if(low > high){
			return;
		}
		int pos = partition(a, low, high);
		int left = pos - low + 1;//左边个数
		if(k > left){//中位数在分裂点右边，将该分裂点作为下次迭代的prePart
			findK(a, pos + 1, high, k - left, pos);
		}
		else if(k < left){//中位数在分裂点左边，本次的prePart作为下次迭代的prePart
			findK(a, low, pos - 1, k, prePart);
		}
		else{
			if(bOdd){//偶数时的中位数处理，取两个中位数的均值
				double v1 = a[pos];
				double v2 = 0;
				if(low >= pos){
					v2 = a[prePart]; //左边无值时取prePart
				}else{
					v2 = findMax(a, low, pos - 1);//左边有值时取左边最大值
				}
				medium = (v1 + v2) / 2;
			}else{
				medium = a[pos];
			}
		}
	}
	
	double findMax(double a[], int low, int high){
		double max = a[low];
		for(int i = low + 1; i <= high; i ++){
			if(a[i] > max){
				max = a[i];
			}
		}
		return max;
	}
	
	double getMedium(){
		return medium;
	}
}

 

3、扩展成求Java的任意对象数组的中位数

import java.util.ArrayList;
import java.util.List;

/**
 * 找中位数,使用快排找第K小数算法
 * @author wangzejie
 *
 * @param <T>
 */
public class MediumFinder<T extends Comparable<T>> {
	private boolean bOdd;//是否奇偶数
	private int kv;//第几大的值
	private List<T> medium = new ArrayList<T>();//中位数数组
	/**
	 * 一次quicksort划分两边
	 * @param a
	 * @param low
	 * @param high
	 * @return
	 */
	private int partition(T a[], int low, int high) {
		T tmp = a[low];
		int i = low, j = high;
		while (i < j) {
			while (i < j && a[j].compareTo(tmp) >= 0){
				j--;
			}
			while (i < j && a[i].compareTo(tmp) <= 0){
				i++;
			}
			swap(a, i, j);
		}
		a[low] = a[i];
		a[i] = tmp;
		return i;
	}

	/**
	 * 交换数组两个位置的值
	 * @param a
	 * @param i
	 * @param j
	 */
	private void swap(T a[], int i, int j) {
		if(i == j){
			return;
		}
		T tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	/**
	 * 需求中位值
	 * @param a
	 * @return  返回中位的T对象，当偶数时返回两点，奇数时返回一点
	 */
	public List<T> findMedium(T a[]){
		medium.clear();
		if(a.length == 1){
			medium.add(a[0]);
		}else if(a.length == 2){
			medium.add(a[0]);
			medium.add(a[1]);
		}else{
			bOdd = a.length % 2 == 0;
			kv = a.length / 2 + 1;
			findK(a, 0, a.length - 1, kv, -1);
		}
		return medium;
	}
	/**
	 * 寻找第K少的值
	 * @param a
	 * @param low
	 * @param high
	 * @param k
	 * @param prePart
	 */
	private void findK(T a[], int low, int high, int k, int prePart){
		if(low > high){
			return;
		}
		int pos = partition(a, low, high);
		int left = pos - low + 1;
		if(k > left){
			findK(a, pos + 1, high, k - left, pos);
		}
		else if(k < left){
			findK(a, low, pos - 1, k, prePart);
		}
		else{
			if(bOdd){
				T v1 = a[pos];
				T v2 = null;
				if(low >= pos){
					v2 = a[prePart];
				}else{
					v2 = findMax(a, low, pos - 1);
				}
				medium.add(v1);
				medium.add(v2);
			}else{
				medium.add(a[pos]);
			}
		}
	}
	/**
	 * 寻找数组一定范围内的最大值
	 * @param a
	 * @param low
	 * @param high
	 * @return
	 */
	private T findMax(T a[], int low, int high){
		T max = a[low];
		for(int i = low + 1; i <= high; i ++){
			if(a[i].compareTo(max) > 0){
				max = a[i];
			}
		}
		return max;
	}
}


public class Point implements Comparable<Point> {

	private double lng;
	private double lat;
	private double value;

	public double getLng() {
		return lng;
	}

	public void setLng(double lng) {
		this.lng = lng;
	}

	public double getLat() {
		return lat;
	}

	public void setLat(double lat) {
		this.lat = lat;
	}

	public double getValue() {
		return value;
	}

	public void setValue(double value) {
		this.value = value;
	}

	@Override
	public int compareTo(Point o) {
		double t = this.value - o.value;
		if (t > 0) {
			return 1;
		} else if (t < 0) {
			return -1;
		}
		return 0;
	}

}