这两天趁复习算法之际,顺便实现了下插入、合并、堆和快速排序。不解释,贴点代码算是给自己留下备日后复习。
/**
* 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;
}
分享到:
相关推荐
虽然Hadoop有自己的MapReduce编程模型,与Java中的Map排序不直接相关,但在处理大规模数据时,有效地排序和组织数据是非常重要的,这可能是在提到Hadoop时顺便提及排序的原因之一。 由于文档提供的内容中存在OCR...
而实验报告,想必大家考完试是需要的,顺便整理了: 1、OpenGL开发环境及扫描转换算法; 2、基本图形几何变换的OpenGL实现; 3、Bezier曲线生成。 希望对师弟师妹有帮助吧。 好吧,师兄只能帮你到这了,认真...
【火线100天四川专版2016中考英语总复习第一部分第十九课时九年级Units9_10试题】这篇资料是针对四川地区2016年中考英语复习的一份课件,主要关注的是九年级Units 9~10的内容,特别是关于风俗习惯的话题。...
【标题】和【描述】提及的是“仁爱英语 八年级下册”的复习练习题PPT学习教案,属于教育资料,特别适合八年级学生进行英语复习。【标签】表明这是专业资料,意味着内容可能涉及教育行业的专业术语和教学方法。 在...
这些内容是初中英语八年级下册Unit单元复习的一部分,涵盖了日常表达、状语从句、固定搭配和语法要点等基础知识,对于学生的英语学习和复习至关重要。通过这样的复习,学生可以强化语言运用能力,提高阅读和写作水平...
快速排序-- 使用PHP来实现,适合刚学习算法的同学,顺便我也赚点金币
【火线100天河北专版2016中考英语总复习第一部分第十九课时九年级Units9_10试题】 本课时重点涵盖了英语词汇、短语及句型,主要关注“风俗习惯”这一话题。以下是相关知识点的详细说明: 1. **风俗习惯**:在学习...
写之前先抱怨几句。本来一心一意做.net开发的,渐渐地成了只做前端。... 深知自己前端技术不足,以前虽说用asp.net...排序从下图中可以看出来,只是字符串的排序,没有实现数字的排序,知道如何用vue.js在前端解决的朋友希
顺便广告下(图片不出来,看附件)"的博客文章可能详细讨论了如何使用EXT标签来增强文档的结构和功能。作者可能分享了一些最佳实践,如如何定义EXT标签,何时应该使用它们,以及如何避免潜在的兼容性问题。由于描述中...
牛津译林版八年级英语(下册)_期末复习重点 本文档主要是对八年级英语(下册)的期末复习重点的总结,涉及到英语语法、词汇、句法等多方面的知识点。 一、重点词组 1. 过去常常(used to do sth.):表示过去...
在词汇拓展部分,学生们需要掌握以下内容: 1. marry(娶/嫁)的形容词形式为married,名词形式为marriage。 2. pollute(污染)的名词形式为pollution,形容词形式为polluted。 3. pleasant(愉快的)的反义词是...
3. **在某种程度上 (in some ways)**、**挡路 (in the way)**、**用这种方式 (in this way)**、**在……路上 (on the/one’s way home)** 和 **顺便问一下 (by the way)**:这些都是表达方式或情况的短语。...
- “by the way”则用于插入话题,表示顺便说一下。 5. **频率副词**: - “from time to time”或“sometimes”表示偶尔,有时。 - “sometime”指的是某个未特定的时间点,未来的一个时刻。 - “some time”...
【知识点详解】 本课时的主题为“风俗习惯”,主要涵盖了九年级Units 9~10的相关英语知识,包括...以上是九年级Units 9~10的复习内容,涵盖了词汇、词组和重要句型,对学习英语和理解风俗习惯相关的表达有极大帮助。
这些知识点构成了九年级下册英语期末复习的重点,不仅涵盖了词汇的记忆,还包含了不同文化背景下的礼仪知识和日常交际用语,对于提升学生的语言运用能力大有裨益。学生需要熟练掌握这些内容,以便在期末考试中能自如...
PS:使用进程版本的另一个重要原因是,想顺便复习下共享内存。 我们使用信号量来同步,用一个整型数组来当缓冲区。很显然这两者都要能够在各生产者和消费者进程间全局可见,所以我们用共享内存来实现他们。
12. take off: 脱下(衣服),飞机起飞,表示移除或启程。 13. go out of one’s way: 特地,格外努力,表示额外付出。 14. make…feel at home: 使(某人)感到宾至如归,让他人感到舒适自在。 15. get used to: ...
16. **过来,顺便拜访**:come over **句型再现:** 1. 请求他人做事的句型:"Could you please...?",如 "Could you please sweep the floor?" 2. 使用 **in order to** 引导的目的状语,如 "They should spend ...
3. **固定搭配**:第4题的"in advance"意为"提前",正确选项是B,提醒学生们提前思考并写下问题。 4. **名词辨析**:第5题的"awareness"意为"意识",在此指对世界饥饿问题的认识。 5. **介词和短语动词**:第6题的...