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; } }
相关推荐
快速排序是一种经典的排序算法, 它的平均性能非常突出。针对快速排序在某些特殊情况下如数据已有序或重复数据较多时效率较低的问题进行了研究, 对三路快速排序进行改进, 使快速排序在特殊情况下也能保持较好的效率。...
第k小元素,算法分析与设计书上的,用mfc实现。做了四种算法,选择排序 快排选择法 中位数法 随机快排
用位排序和快速排顺序排列30万个数,主要是位排序的算法 30万个数是程序产生的 虽然不推荐中文注释,但是中国人还是喜欢中文的注释,我就是这样的 在linux下,中文注释可能是乱码
当大量数据,且重复数多时,用三路快排 插入排序 直接插入排序 思想 将数据插入到一个有序的序列中 做法 外层for循环控制需要排序的趟数(从1开始因为将第0位看成了有序...
快速排序:在待排序的n个数据中,任取一个数据为基准,经过一次排序后以基准数据把全部数据分为两部分,所有数值比基准数小的都排在其前面,比它大的都排在其后,然后对这两部分分别重复这样的过程,直到全部到为...
利用子区间中位数进行分割 散列表 链接法散列表 theta(1+alpha) 不错的查找速度,较灵活的插入和删除 开放寻址法散列表 theta(1/(1-alpha)) 优秀的查找速度,对删除操作支持不好 完全散列 theta(1) 极好的查找速度,...
(2)按选定的算法,从后备作业队列中选出一部分(多道)或一个作业投入运行; (3)为被选中的作业做好运行前的准备工作。例如建立相应的执行进程和分配系统资源; (4)作业运行结束的善后处理工作。 ...
题目描述 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 这个题目完成的思路有很多,很多排序算法都可以完成既定操作,关键是复杂度...思路2:使用快排中的partit
变量'aresult'中的值应该是一个排过序的唯一的一系列的整数的数组,整数的值的范围均在0到255之间。这样一个数组是非常有用的,例如:对一个字节对字节的转换表,就可以很容易并且非常可靠的来产生一个短的密钥...
写一些基础的算法,如快排 famous 著名的一些算法 LCS 最长公共子序列 graph 图 sort 排序 test 一些测试代码 java 有关java的语法 dataStructure java中的数据结构笔记 api java中常用的api problem 真正的题 array...
和传统的热敏电阻相 比,它能够直接读出被测温度,并且可根据实际要求通过编程实现9~12位的数字值读数 方式;可以分别在93.75ms和750 ms内完成9位和12位的数字量;从DS18B20读出信息或写入DS18B20信息仅需要1根口线...
int median(int p, int q) //挑出a[p…q]的中位数,并返回中位数,参数可根据自己需要修改。 { …… } void QuickSort(int p,int q) //参数可根据自己需要修改。 { if(p>=q)return; int x = median(p, q); int...
经验2:方法2最好使用随机化快排,效率很高 把两个链表表示的数加起来:最佳624ms,3% 用长一点的链表做基础,最多只需要new一个新节点 优化建议:进位尽量用数字。如果一个链到头了,另一个没到,应该沿着长链前进...
1、由字母,数字,下划线以及 $ 组成 var user_name; 正确 var user-name; 错误 var $uname; 正确 2、不能以数字开头 var 1name;错误 3、不能使用JS中的关键字 和 保留关键字 4、变量名不能重复 5、可以...
快速排序:确定中间分界点,左右指针往外扩,三个而来快排,递归处理左和右引申:第k个数 归并排序:确定中间分界点,递归处理左和右,三个而来归并,左到中右到r引申:逆序对的数量 整体二分:左段取左,右段取右,...
利用激光干涉测长、精密测角及光靶跟踪技术,可对任意点的空间坐标进行实时跟踪测量,精度高、速度快、范围大、通用性强,特别适合于大尺寸工件的现场测量,在大型设备的制造安装过程中得到广泛的应用。 现有的"光靶...
在EURO NCAP 2025 Roadmap中,规划车内...4. 因为 CMOS 工艺,将射频和和数位集成在单个雷达芯片上。可以更有效的实现线上即时监测和调试; 5. 方案精度高,测距精度可达 4cm。人体感测距离建议40M内 方案来源:大大通
* 用一个 8 位的 8 进制数表示棋盘上皇后的位置: * 比如:45615353 表示: * 第0列皇后在第4个位置 * 第1列皇后在第5个位置 * 第2列皇后在第6个位置 * 。。。 * 第7列皇后在第3个位置 * * 循环...
压缩技术,因此压缩率极高,几乎可以排到世界第一位,尤其是多文件压缩!唯一的缺点 是压缩速度比其他格式较慢.后面给出各个常用的压缩工具压缩单文件和多文件的结果. ----------------------------------------------...
软件代码多重过滤可以第一时间被搜索引擎收录,独特的静态生成算法可以大大减轻服务器的负担,无论在生成速度还是安全方面都达到国内领先水平。 二、生成过程更简单易用、更直观方便! 网趣HTML静态版V2012采用...