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

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;
	}

}