今天随便翻了翻Java数据结构与算法这本书,写了一些常见的简单算法。当练习一下。当然代码不是十分完善,只是演示算法而已。
/**
* 排序、查找算法
* @author sunlong
*
*/
public class OrderArray {
private int[] arr;
private int length;
public OrderArray(int size){
arr = new int[size];
length = 0;
}
/**
* 未检查边界,有序插入
* @param value
*/
public void insert(int value){
int pos = length;
for(int i=0; i<length; i++){
if(arr[i] > value){
pos = i;
break;
}
}
for(int j = length; j > pos; j--){
arr[j] = arr[j-1];
}
arr[pos] = value;
length++;
}
/**
* 无序插入
* @param value
*/
public void insertNoOrder(int value){
arr[length++] = value;
}
/**
* 二分查找
* @param value
* @return
*/
public int find(int value){
int lower = 0, higher = length-1, current = (lower+higher)/2;
while(lower <= higher){
if(arr[current] == value){
return current;
}else if(arr[current] > value){
higher = current - 1;
}else{
lower = current + 1;
}
current = (lower+higher)/2;
}
return -1;
}
public int find2(int value){
return findDiGui(0, length-1, value);
}
/**
* 递归的二分查找
* @return
*/
public int findDiGui(int lower, int higher, int value){
int current = (lower+higher)/2;
if(lower > higher) return -1;
if(arr[current] == value){
return current;
}else if(arr[current] > value){
higher = current - 1;
}else{
lower = current + 1;
}
return findDiGui(lower, higher, value);
}
public void print(){
for(int i=0; i<length; i++)
System.out.print(arr[i]+",");
System.out.println();
}
/**
* 冒泡排序
* 比较相临的两个元素
*/
public void bubbleSort(){
int tmp;
for(int i=length-1; i>=0; i--){
for(int j=0; j<i; j++){
if(arr[j]>arr[j+1]){
tmp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = tmp;
}
}
}
}
/**
* 选择排序改进了冒泡排序,使得交换次数从o(n*n)降到o(n)
* 选择排序是第一遍扫描选择最小的值,然后和0位置交换,接着再选择次小的值和1位置交换,直到全部完成
*/
public void selectSort(){
if(length == 0) return ;
int min = 0, tmp;
for(int j=0; j<length; j++){
for(int i=j+1; i<length; i++){
if(arr[min] > arr[i]){
min = i;
}
}
tmp = arr[min];
arr[min] = arr[j];
arr[j] = tmp;
}
}
/**
* 插入排序,通常比冒泡和选择排序要好,虽然比较o(n*n)
* 它以局部有序为前提
* 假设标记的左边全部有序,则要在左边插入这个标记的值。
*/
public void insertSort(){
int tmp;
for(int i=1; i<length; i++){
tmp = arr[i];
int j = i;
while(j>0 && arr[j-1]>tmp){
arr[j] = arr[j-1];
j--;
}
arr[j] = tmp;
}
}
/**
* 归并排序o(n*logN),比冒泡、选择、插入排序要好
* 思想是归并两个已经有序的数组,把一个数组一分为二,再一分为二……
*/
public void mergeSort(){
int[] workspace = new int[length];
recMerge(workspace, 0, length-1);
}
private void recMerge(int[] workspace, int lower, int higher){
if(lower == higher) return;
else{
int mid = (lower + higher)/2;
recMerge(workspace, lower, mid);
recMerge(workspace, mid+1, higher);
merge(workspace, lower, mid, higher);
}
}
/**
* 合并两个数组,分别是arr数组中的lower至mid,还有一个是mid+1至higher
* 合到workspace中,然后把workspace中数据复制到lower至higher中
* @param workspace
* @param lower
* @param mid
* @param higher
*/
private void merge(int[] workspace, int lower, int mid, int higher){
int left = lower;
int right = mid+1;
int index = 0;
while(left<=mid && right<=higher){
if(arr[left] < arr[right]){
workspace[index++] = arr[left++];
}else{
workspace[index++] = arr[right++];
}
}
//有可能left部分的数组没有考完,但是right已经结束了,所以不需要再比较,直接把
//left部分剩余的数复制过去即可
while(left<=mid){
workspace[index++] = arr[left++];
}
//同上分析
while(right<=higher){
workspace[index++] = arr[right++];
}
int n = higher-lower+1;
for(int i=0; i<n; i++){
arr[lower+i] = workspace[i];
}
}
/**
* 希尔排序是对插入排序的一种改进,它使用n-增量法,首先对间隔n的数进行排序,然后逐渐减少间隔n直到变成1,此时
* 数组基本有序,那么再进行插入排序,将大大提高插入排序的效率
* 间隔算法可以用Knuth提出的算法,间隔以1开始,逆向使用。
* 算法为n=3*n+1,n初始为1,递归生成
* 比如1,然后n=3*1+1=4,然后n=3*4+1=13……
*
* 举例来说10个数,h=4,则(0,4,8) (1,5,9) (2,6) (3,7)
* 在排序时每组先比较前两个数,排完返回,再对第三个数处理,所以实际上是
* (0,4) (1,5) (2,6) (3,7) (0, 4, 8) (1, 5, 9)
* 当然个人觉得可以按小组来排完再说,我的写法是基于此方式
*/
public void shellSort(){
/*个人按理解写的希尔排序*/
int h = 1;
while(h<=length/3){
h = h*3 + 1;
}
int tmp;
while(h>0){
for(int span=0; span<h; span++){
for(int i=(h+span); i<length; i+=h){//每组进行插入排序
tmp = arr[i];
int index = i;//index用于向前遍历
while(index>=h && arr[index-h]> tmp){
arr[index] = arr[index-h];//向右移动数据
index -= h;
}
arr[index] = tmp;
}
}
h = (h-1)/3;
}
/*以下是Java数据结构与算法中的写法
int inner, outer;
int temp;
int h = 1;
while (h <= length/3){
h = h*3 + 1;
}
while (h > 0) {
for (outer = h; outer < length; outer++) {
temp = arr[outer];
inner = outer;
while (inner > h - 1 && arr[inner - h] >= temp) {
arr[inner] = arr[inner - h];
inner -= h;
}
arr[inner] = temp;
}
h = (h - 1) / 3;
}*/
}
}
分享到:
相关推荐
Java的主要特点和优势包括以下几个方面: 跨平台性(Write Once, Run Anywhere): Java的代码可以在不同的平台上运行,只需编写一次代码,就可以在任何支持Java的设备上执行。这得益于Java虚拟机(JVM),它充当了...
11.11 编程练习 第12章 搜索与排序 12.1 搜索 12.2 排序 12.3 评估算法效率 12.4 使用数据文件 12.5 小结 12.6 复习题 12.7 编程练习 第13章 数组与ArrayList类 13.1 ArrayList类回顾 13.2 HashMap类 13.3 Java集合...
自1995年首次发布以来,Java编程语言作为一种教学语言变得日益重要,现在已经成为初级计算课程斯坦福大学的标准语言。Java语言可以让学生编写高度交互式程序,这充分激发了他们的学习兴趣。但Java语言很复杂,老师和...
几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet...
几种简单排序之间的比较 小结 问题 实验 编程作业 第4章 栈和队列 不同的结构类型 栈 队列 优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet...
54. java中有几种方法可以实现一个线程?用什么关键字修饰同步方法? stop()和suspend()方法为何不推荐使用? 13 55. java中有几种类型的流?JDK为每种类型的流提供了一些抽象类以供继承,请说出他们分别是哪些类? 14 56....
专题二 3 总结数组拷贝的几种方法,并实现 5 专题二 4 Fibonacci数列。实践2拓展练习2.2 6 专题二 5 函数调用:素数问题 7 专题二 6 switch 8 专题二 7控制结构 9 专题二 8 数组排序 10 专题二 9合并数组 11 ...
2、内容全面:全面论述排序、搜索、图处理和字符串处理的算法和数据结构,涵盖每位程序员应知应会的50种算法 3、全新修订的代码:全新的Java实现代码,采用模块化的编程风格,所有代码均可供读者使用 4、与...
Sedgewick之巨著,与高德纳TAOCP一脉相承,几十年多次修订,经久不衰的畅销书,涵盖所有程序员必须掌握的50种算法。 《算法:第4版》作为算法领域经典的参考书,全面介绍了关于算法和数据结构的必备知识,并特别针对...
第2章 Java经典练习题 2.1 斐波那契数列 2.2 判断素数 2.3 水仙花数 2.4 分解质因数 2.5 杨辉三角 2.6 学习成绩查询 2.7 求最大公约数与最小公倍数 2.8 完全平方数 2.9 统计字母、空格、数字和其它字符个数 2.10 求...
全面论述排序、搜索、图处理和字符串处理的算法和数据结构,涵盖每位程序员应知应会的50种算法 全新修订的代码 全新的Java实现代码,采用模块化的编程风格,所有代码均可供读者使用 与实际应用相结合 在...
全面论述排序、搜索、图处理和字符串处理的算法和数据结构,涵盖每位程序员应知应会的50种算法 全新修订的代码 全新的Java实现代码,采用模块化的编程风格,所有代码均可供读者使用 与实际应用相结合 在...
几种常见排序算法.docx JAVA 修饰符 JAVA泛型 韩顺平java笔记完整版-基础篇 ##数据类型 JAVA中的基本数据类型有四类八种:整数类型、小数类型、字符类型、布尔类型。 整数类型:byte、short、int、long 占用字节: 1...
Sedgewick之巨著,与高德纳TAOCP一脉相承,几十年多次修订,经久不衰的畅销书,涵盖所有程序员必须掌握的50种算法。 《算法:第4版》作为算法领域经典的参考书,全面介绍了关于算法和数据结构的必备知识,并特别针对...
”但稍加练习之后,你就会发觉自己只用预期的一半时间,就用新功能写出 了更短、更清晰的代码,这时你会意识到自己永远无法返回到“旧Java”了。 本书会帮助你跨过“原理听起来不错,但还是有点儿新,不太适应”的...
全面论述排序、搜索、图处理和字符串处理的算法和数据结构,涵盖每位程序员应知应会的50种算法 ? 全新修订的代码 全新的Java实现代码,采用模块化的编程风格,所有代码均可供读者使用 ? 与实际应用相结合 在重要的...
本书非常适合Java的初学者,如高校学生、求职人员作为练习、速查、学习使用,也适合Java程序员参考、查阅。 目 录 第1篇 Java语法与面向对象技术 第1章 开发环境的应用 2 1.1 Java环境 3 实例001 下载JDK开发...
i++){ //运行老久,减少循环次数会快很多,只是精确度小些 pi += (fenZi/fenMu) ; fenZi *= -1.0; //每项分子的变化是+4,-4,+4,-4 .... fenMu += 2.0; //分母的变化是1,3,5,7, .... 每项递加2 } ...