`
wangzjie
  • 浏览: 74728 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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

阅读更多

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

}

 

分享到:
评论

相关推荐

    算法集锦\快排.txt

    从给定的文件标题、描述、标签以及部分内容来看,本篇文章将深入探讨快速排序(简称快排)算法的核心原理与实现细节。快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔于1960年提出。其基本思想是通过一...

    快排算法 C程序 源码

    - **三数取中法**:在选择基准时,避免总是选取数组的第一个或最后一个元素,而是取中间三个数的中位数,这样能降低最坏情况出现的概率。 - **尾递归优化**:在某些实现中,可以优化递归调用,使其变为尾递归,减少...

    冒泡、快排、插入、合并、选择排序算法集锦

    ### 冒泡、快排、插入、合并、选择排序算法集锦 #### 一、冒泡排序 **原理概述:** 冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的...

    冒泡,选择,快排,归并,堆排序算法

    常见的排序算法有冒泡排序、选择排序、快排、归并排序、堆排序等。这些算法的时间复杂度和空间复杂度各不相同,本文将对这些算法进行详细的介绍。 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法,通过...

    python_百度快排(附源码核心

    通常选择第一个或最后一个元素,但更优的选择方式是选取中位数,这可以减少平均情况下的比较次数。 2. **分区操作**:遍历数组,将小于基准的元素放在基准的左边,大于基准的放在右边。这样,基准就位于最终排序后...

    快速排序的算法php实现类.zip

    实际实现时,可以考虑一些优化措施,比如三数取中法(取首、尾、中间三个元素的中位数作为基准),以减少最坏情况的发生;对于小规模数据,可以使用插入排序,因为插入排序在小规模数据上效率更高。 8. **使用示例...

    广州大学 数据结构实验报告 实验四 查找和排序算法实现

    1. **插入排序**:插入排序的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。在未完成排序的序列中,从前往后遍历,将每个元素插入到已排序部分的正确位置。在这个过程中,...

    冒泡排序 快排 堆排序 的c++实现

    在编程领域,排序算法是计算机科学中的核心概念,它们用于对数据进行有序排列。这里我们主要探讨三种经典的排序算法:冒泡排序、快速排序和堆排序,并且它们都是使用C++语言实现的。这些排序算法各有特点,适用于...

    数据结构实验五 快速、堆、基数排序算法的设计.doc

    实验中,你需要实现这三个排序算法,并理解它们的物理存储结构以及如何用高级语言(如C语言)实现。理解这些排序算法的性能分析方法也很重要,比如快速排序的平均时间复杂度为O(nlogn),但最坏情况下为O(n^2),而堆...

    算法分析 2.3快速排序 分治法

    - **三数取中**:选取枢轴时,可以选取待排序序列的第一个、最后一个和中间元素的中位数,以减少平均情况下的分割不均。 - **随机化选择枢轴**:随机选取待排序序列中的一个元素作为枢轴,可以避免最坏情况的发生,...

    Java实现的快速排序和随机快排

    - **三数取中法**:选择数组首、尾、中间三个元素的中位数作为基准,可以进一步提高划分的均匀性。 - **尾递归优化**:当子数组大小小于某个阈值时,可以改用插入排序,因为对于小数组,插入排序可能更快。 通过...

    常用排序算法的java实现(冒泡、插入、选择、希尔、归并、快排)

    改进的冒泡排序通常包括设置标志位来检测是否已经完成排序,以及添加一个提前退出循环的条件,当某次遍历没有发生交换时,说明数组已有序。 2. **插入排序**:插入排序的工作原理是将数组分为已排序和未排序两部分...

    大数据处理算法.pdf

    例如,给 20 亿个不重复的 unsigned int 的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那 40 亿个数当中,并且所耗内存尽可能的少?可以使用 Bitmap 算法来解决这个问题。 在 Java 中,可以使用 ...

    排序 快排,shell,insert,select 等

    ### 排序算法知识点 根据提供的代码片段及标题、描述,可以提炼出以下关于排序算法的知识点: #### 1. 插入排序(Insert Sort) 插入排序是一种简单直观的比较排序算法。它的工作原理是通过构建有序序列,对于未...

    基数排序算法.zip

    例如,如果当前处理的是个位,那么将所有个位为3的数放入“3”桶中。 3. 重新排列:收集每个桶中的元素,并按照顺序放置回原数组。这样,个位已经按照大小顺序排列好了。 4. 对下一位进行相同的操作,直到所有的位...

    可强占的优先进程调度算法

    在设计PCB表时,对于“可强占的优先数调度算法”,我们需要额外考虑进程的优先级和当前状态,以便在运行过程中能够根据需要中断正在执行的进程,转而执行优先级更高的进程。这需要在PCB中包含优先级字段以及一个标志...

    数据结构中的所有排序算法加报告

    在IT领域,排序算法是计算机科学中至关重要的一个部分,特别是在数据结构与算法设计中。本文将详尽探讨数据结构中的各种排序算法及其原理、性能分析,并附带一份详细的报告,帮助读者深入理解这些核心概念。 一、...

    面试常见基础算法题总结

    8. **快排优化**:三向切分快排能处理大量重复元素的情况,避免过多的递归。当子问题规模较小,可用插入排序替代递归。 9. **链表反转**:通过三个指针,分别指向当前节点、前一个节点和下一个节点,迭代完成链表...

Global site tag (gtag.js) - Google Analytics