package com.linzhanghui.algorithm;
//二分法
public class OrdArray {
private long[] a;
private int nElems;
public OrdArray(int max) {
a = new long[max];
nElems = 0;
}
public int size(){
return nElems;
}
public int find(long searchKey) {
int lowerBound = 0;
int upperBound = nElems - 1;
int curIn;
while (true) {
curIn = (lowerBound + upperBound) / 2;
if(a[curIn] == searchKey)
return curIn;
else if(lowerBound > upperBound)
return nElems;
else {
if(a[curIn] < searchKey)
lowerBound = curIn + 1;
else
upperBound = curIn - 1;
}
}
}
public void insert(long value) {
int j;
for(j=0; j<nElems; j++)
if(a[j] > value)
break;
for(int k=nElems; k>j; k--)
a[k] = a[k-1];
a[j] = value;
nElems++;
}
public boolean delete(long value) {
int j = find(value);
if(j == nElems)
return false;
else {
for(int k=j; k<nElems; k++)
a[k] = a[k+1];
nElems--;
return true;
}
}
public void display() {
for(int j=0; j<nElems; j++)
System.out.print(a[j] + " ");
System.out.println(" ");
}
}
package com.linzhanghui.algorithm;
public class OrderedApp {
public static void main(String[] args) {
int maxSize = 100;
OrdArray arr = new OrdArray(maxSize);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
int searchKey = 55;
if(arr.find(searchKey) != arr.size())
System.out.println("找到" + searchKey);
else
System.out.println("找不到" + searchKey);
arr.display();
arr.delete(00);
arr.delete(55);
arr.delete(99);
arr.display();
}
}
package com.linzhanghui.algorithm;
/*
* 冒泡排序,时间复杂度O(n^2)
* 简单描述:
* 两两比较,比较出最大的一个数放在最后位置
* 剩下的继续比较
*
*/
public class ArrayBub {
private long[] a;
private int nElems;
public ArrayBub(int max) {
a = new long[max];
nElems = 0;
}
public void insert(long value) {
a[nElems] = value;
nElems++;
}
public void display() {
for(int j=0; j<nElems; j++)
System.out.print(a[j] + " ");
System.out.println("");
}
public void bubbleSort() {
int out, in;
for(out=nElems-1; out>1; out--)
for(in=0;in<out;in++)
if(a[in] > a[in+1])
swap(in, in+1);
}
private void swap(int one,int two) {
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
}
package com.linzhanghui.algorithm;
public class BubbleSortApp {
public static void main(String[] args) {
int maxSize = 100;
ArrayBub arr = new ArrayBub(maxSize);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display();
arr.bubbleSort();
arr.display();
}
}
package com.linzhanghui.algorithm;
/*随机生成1000个数字,并归并快速排序;
*/
public class ArrayIns {
private long[] theArray;
private int nElems;
public ArrayIns(int max) {
theArray = new long[max];
nElems = 0;
}
public void insert(long value) {
theArray[nElems] = value;
nElems++;
}
public void display() {
System.out.print("A=");
for(int j=0; j<nElems; j++)
System.out.print(theArray[j] + " ");
System.out.println("");
}
public void quickSort() {
recQuickSort(0, nElems-1);
}
public void recQuickSort(int left, int right) {
if(right-left <= 0)
return;
else {
long pivot = theArray[right];
int partition = partitionIt(left, right, pivot);
recQuickSort(left, partition-1);
recQuickSort(partition+1, right);
}
}
public int partitionIt(int left, int right, long pivot) {
int leftPtr = left-1;
int rightPtr = right;
while(true) {
while(theArray[++leftPtr] < pivot);
while(rightPtr > 0 && theArray[--rightPtr] > pivot );
if(leftPtr >= rightPtr)
break;
else
swap(leftPtr, rightPtr);
}
swap(leftPtr, right);
return leftPtr;
}
public void swap(int dex1, int dex2) {
long temp = theArray[dex1];
theArray[dex1] = theArray[dex2];
theArray[dex2] = temp;
}
}
package com.linzhanghui.algorithm;
public class QuickSort1App {
public static void main(String[] args) {
int maxSize = 1000;
ArrayIns arr = new ArrayIns(maxSize);
for(int j=0; j<maxSize; j++) {
long n = (int)(java.lang.Math.random()*999);
arr.insert(n);
}
arr.display();
arr.quickSort();
arr.display();
}
}
分享到:
相关推荐
一本三峡大学理学院的周鹏写的数据结构和算法JAVA语言描述。讲解了常用的数据结构和算法。
这本书是数据结构与算法(JAVA版),通过Java语言实现常用算法和数据机构,书中给出了详细代码和习题,非常值得一读
Java语言描述是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。 系统地介绍各种常用的数据结构,对基本概念、...
Java语言描述(原书第3版)是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。系统地介绍各种常用的数据结构,对...
《数据结构与算法分析+java语言描述》是一本Java学者必读的算法书籍。里面基本包含了所有的Java常用算法,分析,解析,挺全面的,如果对于算法没有过深入了解,学习他会有很大的帮助,本人力推。
系统地介绍各种常用的数据结构,对基本概念、基本原理和基本方法以及相关的算法设计做了...全书采用面向对象的Java语言对算法进行描述,将传统的数据结构的内容与面向对象的思想和技术完全融合,使得讲解更加贴近自然。
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
此书系统用java与c语言两种语言描述了历史上常见的经典算法!
该文档描述了使用Java语言实现常用算法,较为易读,适用于初学者
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
数据结构与算法(JAVA语言版)描述了Java的常用算法,若对你有用,请点个赞~
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
这是一本数据结构与算法(Java版本描述)的国外教材配套的...里面包含了Java语言的常用的几十种数据结构的实现(与JDK库中的实现不同),另有多种JDK库中没有数据结构的代码,供使用Java语言学习数据结构的朋友们使用。
algorithm-java cn.fh.search 二分查找 多线程同时查找 cn.fh.sort 选择排序 插入排序 希尔排序 快速排序 cn.fh.datastructure 基于动态数组的栈 基于链表的栈 基于链表的队列 优先队列 二叉查找树 cn.fh.apply ...
常见数据结构与算法小结(Java语言描述) 这是一个数据结构和算法笔记本,书写 并 整理一些常见的数据结构和其对应的相关操作。这其中每一个类文件都是一个可以单独运行查看结果的main方法类,相关的关键描述和想说...
全书采用面向对象的Java语言对算法进行描述,将传统的数据结构的内容与面向对象的思想和技术完全融合,使得讲解更加贴近自然。内容翔实,结构清晰合理,可作为大专院校计算机及其相关专业的有关数据结构的教材和参考...
我又进一步完善了顺序表结构的常见算法,其中node是顺序表类,SplitList是测试类。写的不好,请大家批评指教。