这两天趁复习算法之际,顺便实现了下插入、合并、堆和快速排序。不解释,贴点代码算是给自己留下备日后复习。
/**
* Sort the array of a
* Just like a number of n cards on the desk, you pick one by one, each time you pick up one card, insert into the correct place into the cards in your hand
* @param <T>
* @param a
*/
@SuppressWarnings("unchecked")
public static <T extends Comparable<?>> T[] insertSort(T[] a){
if( a == null || a.length == 0 )
return null;
for( int i = 1; i < a.length; ++i){
T key = a[i];
int j = i - 1;
while( j >= 0 && ((Comparable)a[j]).compareTo(key) > 0 ){
//if a[j] > key
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
return a;
}
public static <T extends Comparable<?>> void mergeSort(T[] a, int low, int high){
if( low < high){
int q = (low + high) / 2;//(0+3)/2 = 1 a,0,1 ==> q = 0 a 00,11 a,2,3
mergeSort(a,low,q);
mergeSort(a,q+1,high);
merge(a,low,q,high);
}
}
/**
* Merge two sorted sub arrays into a whole array
* Suppose the sub arrays a[p,p+1,...q] and a[q+1,q+2,...r] are the sorted arrays
* Merge these two sub arrays into the whole array T[] a to make it sorted array
*/
@SuppressWarnings("unchecked")
public static <T extends Comparable<?>>void merge(T[] a, int p, int q, int r){
int n1 = q - p + 1;
int n2 = r - q;
T[] L = (T[]) Array.newInstance(Comparable.class, n1);
for( int i = 0; i < n1; i++)
L[i] = a[p+i];
T[] R = (T[]) Array.newInstance(Comparable.class, n2);
for( int i = 0; i < n2; i++)
R[i] = a[q+1+i];
int i = 0, j = 0, k = p;
while( k < r && i < n1 && j < n2){
if( ((Comparable)L[i]).compareTo(R[j]) < 0 ){
//L[i] < R[j]
a[k] = L[i];
i++;
}else{
a[k] = R[j];
j++;
}
k++;
}
if( i >= n1){
while( j < n2){
a[k] = R[j];
k++;
j++;
}
}
if( j >= n2 ){
while( i < n1 ){
a[k] = L[i];
k++;
i++;
}
}
}
public static <T extends Comparable<?>> void heapSort(T[] a){
buildMaxHeap(a);
for( int i = 1; i < a.length; ++i){
swap(a,1,a.length - i);//注意这里是1 不是i
maxHeapify(a, 1, a.length - i - 1 );//是1
}
}
public static <T extends Comparable<?>> void swap(T[] a, int i, int j){
T temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* 给定一个数组,构建一个大顶堆
* 对于满二叉树,子数组a[length/2 + 1],....a[length] 为叶子节点,
* 所以只要从a[length/2]开始直至a[1],一次进行对调整即可
* @param <T>
* @param a
*/
public static <T extends Comparable<?>> void buildMaxHeap(T[] a){
for( int i = (a.length-1)/2; i > 0; i--){
maxHeapify(a,i, a.length - 1);
}
}
/**
* 保持大顶堆操作
* 假设a中第i个元素为根的子树不符合打顶堆性质
* 思想:比较i和两个子女,若子女中最大者比i大,则交换之,继续以交换的子女为根调整
* @param <T>
* @param a
* @param i
*/
@SuppressWarnings("unchecked")
public static <T extends Comparable<?>> void maxHeapify(T[] a, int i, int heapSize){
int largest = -1;
int left = i<<1;
int right = left+1;
if( left <= heapSize && ((Comparable)a[left]).compareTo(a[i]) > 0){
largest = left;
}else{
largest = i;
}
if( right <= heapSize && ((Comparable)a[right]).compareTo(a[largest]) > 0){
largest = right;
}
if( largest != i ){
T tmp = a[i];
a[i] = a[largest];
a[largest] = tmp;
maxHeapify(a, largest, heapSize);
}
}
public static <T extends Comparable<?>> void quickSort(T[] a, int p, int r){
if( p < r ){
int q = partition(a, p, r);
quickSort(a,p,q-1);
quickSort(a,q+1,r);
}
}
@SuppressWarnings("unchecked")
public static <T extends Comparable<?>> int partition(T[] a, int p, int r){
T x = a[r];
/**
* i 用来指明当前比a[r]小得区域,初始状态该区域为空,所以置初始值 i = p - 1
* j 用来指示当前扫描到的元素,从p开始扫描,初始值 j = p
* 当发现a[j]比a[r]小或等,则把a[j]放到i指示的区域:很简单,先i自增即找到大于a[r]的区域中第一个元素,然后交换a[i]和a[p],做完以后,i的区域增加了一个小于a[r]的元素
* 最后,a[i+1]即位x的位置
*/
int i = p - 1;
for(int j = p; j < r; ++j){
if(((Comparable)a[j]).compareTo(x) <= 0){
HeapSortor.swap(a, ++i, j);
}
}
HeapSortor.swap(a,i+1,r);
return i+1;
}
分享到:
相关推荐
JAVA复习题与答案,可以让把一些概念记得更牢固,顺便测试下自己的学习
而实验报告,想必大家考完试是需要的,顺便整理了: 1、OpenGL开发环境及扫描转换算法; 2、基本图形几何变换的OpenGL实现; 3、Bezier曲线生成。 希望对师弟师妹有帮助吧。 好吧,师兄只能帮你到这了,认真...
数组有工具类Arrays,集合也有一个工具类Collections,这里练习一下集合工具类的排序方法,顺便过一下sort排序方法,比较器。 sort方法 sort(List<T> list):根据其元素的natural ordering对指定的列表进行排序。 ...
快速排序-- 使用PHP来实现,适合刚学习算法的同学,顺便我也赚点金币
写之前先抱怨几句。本来一心一意做.net开发的,渐渐地成了只做前端。... 深知自己前端技术不足,以前虽说用asp.net...排序从下图中可以看出来,只是字符串的排序,没有实现数字的排序,知道如何用vue.js在前端解决的朋友希
前段时间因为项目需要,做了个用来对数组排序的类,顺便把以前学过的几种排序算法用C#实现一下。用C#的一些机制来诠释了一下算法的是实现。在阅读本之前,需要一些对C#的有些基本的了解,了解方法参数中out ,ref的...
PS:使用进程版本的另一个重要原因是,想顺便复习下共享内存。 我们使用信号量来同步,用一个整型数组来当缓冲区。很显然这两者都要能够在各生产者和消费者进程间全局可见,所以我们用共享内存来实现他们。
NULL 博文链接:https://kanful.iteye.com/blog/571057
在日常学习计算机网络知识时,顺便对计算机网络的知识要点做了总结,供大家参考
前些日子不是在做使用Jquery-UI实现一次拖拽多个选中的元素操作嘛,在持续完善这个组件时遇到了一个关于拖放排序的bug。今天就着图片和代码重现一下,也顺便告诉大家如何解决这个问题
randomNumberSorter 一种简单的冒泡排序算法,通过生成多个随机数然后对其进行排序来显示。 语言 Python 关于我 我是一个青少年,喜欢在业余时间编码,... 顺便说一句,这是一个完成的应用程序,尽管可以进行任何优化
bisect 模块里实现了一个向列表插入元素时也会顺便排序的算法。(升序) import bisect inter_list = [] # 插入一些随机数 bisect.insort(inter_list, 3) bisect.insort(inter_list, 2) bisect.insort(inter_list, 5...
数组productlist中存储的是自定义类Product,Product有一个方法是返回商品的价格,于是对productlist按照Product的价格从低到高进行排序,仅需要如此简单的一行代码即可实现。 Python真的是一门简洁而强大的语言,...
16MB的FLASH,顺便打开了UART
openjdk的源码文件,对照java文件及c文件,深入理解java语言及虚拟机,顺便复习下底层的C基础。学会用代码帮助自己做事。 相信对你会有帮助。
虎年了大家应该试一试老虎表情哦!...这次也顺便写了个插件。仅供参考下。 代码开源,大家一起探讨。大家看我的代码哪写的有问题,或者能有什么更好的优化方法,谢谢你别吝啬提出来,大家一起进步!!
最成功的女人把年龄顺便活成了气质
最近自学java中的框架-struts写了一些小例子,这都是很经典的程序,如果大家瞧得起要下载去看看,顺便给俺找找不足的地方。我的qq 821865130 email qingtian_hechen@163.com 希望大家能多多给我帮助。在此谢谢各位!...
想养一只桌面宠物吗?顺便学习python-pyqt