五
3
2009
排序算法汇总
作者: seasun一 排序的基本概念
所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来. 其确切定义如下:
输入: n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn.
输出: Ril,Ri2,…,Rin,使得Ki1 ≤ Ki2 ≤ … ≤ Kin.(或Ki1 ≥ Ki2 ≥ … ≥ Kin.)
分类目录 ‘Algorithm’
四
9
2009
全文检索中近义词、关联词的解决方案
作者: seasun一直想找到一个好的同义词解决方案，在百度和google查找，大家对于这个问题都只是寥寥数语，不愿讲清，我在javaeye搜此类信息也求不到,后来发了个提问贴也只有浏览数而无回复，不知道这是什么原因，无奈之下我只有自己研究。
因为没有其它的解决方案可以借鉴，以下纯为我个人的见解。 (全文…)
三
31
2009
排序－插入
作者: seasun插入排序总是假设指定位置的左边的数组是有序的，而后将指定位置的值插入左边的有序数组。
指定的位置从下标1开始，每次循环递增1，直到数组结束。
插入排序的比较次数与交换次数的时间效率均为O(n^2)，确切的说是O(n^2 / 4)，比冒泡排序快一倍。
对于一个基本有序数组，由于内循环基本都是空循环，插入排序的效率接近O(n)，但对于完全逆序数组，插入排序的效率与冒泡相同。因此插入排序对于 基本有序，或反复排序的数组比较有利，实是上插入排序常常用于其他排序的首尾工作，其他排序只要排到基本有序即可，比如快速排序。
下面是代码。
class Insert {
public static void main(String[] args) {
int[] a = {1,5,3,8,4,3,8};
sort(a);
print(a);
}
private static void sort(int[] a) {
int temp;
for(int i=1; i<a.length; i++) {
int pos = i; //确定位置，在此位置左边的数组是有序的。
temp = a[i]; //根据位置确定要插入的数值。
while(pos>0 && a[pos-1]>temp) { //选择第一个不大于要插入数值的的位置
a[pos] = a[pos - 1]; //将数据以此向后移动
pos–;
}
a[pos] = temp; //将指定数值插入恰当位置
}
}
private static void print(int[] a) {
for(int i: a) System.out.print(i + ” “);
System.out.println();
}
}
三
31
2009
排序－冒泡
作者: seasun冒泡排序的算法此处不在叙述。冒泡排序比较与交换的时间效率都是O(n^2)。
下面提供冒泡排序的Java代码。代码足够简单，没有加注释。
class Bubble {
public static void main(String[] args) {
int[] a = {6,3,2,6,3,2,9,7};
sort(a);
print(a);
}
private static void print(int [] a) {
for(int i: a) System.out.print(i + ” “);
System.out.println();
}
private static void sort(int[] a) {
int temp;
for(int i=a.length-1; i>0; i–) {
for(int j=0; j<i; j++) {
if(a[j] > a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
}
三
31
2009
递归－三角数字
作者: seasun三角数字是这样一组数字：1 3 6 10 15 21 28 36 45……
其中第n个数字等于n-1个数字的值加上n。
此处用递归算法求三角数字。（要求得该数字不一定要使用递归，迭代来的效率更高一些）
下面是代码：
class Triangle {
public static void main(String[] args) {
for(int i=1; i<10; i++) System.out.print(getNext(i) + ” “);
System.out.println();
}
private static int getNext(int n) {
if(n == 1) return 1;
return n + getNext(n-1);
}
}
三
31
2009
排序－选择
作者: seasun选择排序 ，原理与冒泡 类似，相比之下，交换的时间效率为O(n)，比较的时间效率依然为O(n^2)
代码如下，程序简单，没有提供注释。
class Select {
public static void main(String[] args) {
int[] a = {2,4,6,3,6,2,6,4,9};
sort(a);
print(a);
}
private static void sort(int[] a) {
int temp;
for(int i=0; i<a.length-1; i++) {
int min = i;
for(int j=i+1; j<a.length; j++) {
if(a[j] < a[min]) min = j;
}
if(min != i) {
temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}
private static void print(int[] a) {
for(int i: a) System.out.print(i + ” “);
System.out.println();
}
}
三
31
2009
Tree 二叉搜索树
作者: seasun每个节点最多两个子节点，其中左边节点的值小于该节点的值，右边节点的值大于该节点的值。为了简便起见，该二叉树装入的数据为整数，且不允许有重复的关键字值。
编程中为了简便，采用了递归算法，运算时会带来额外的开销，如果能将相应的算法替换为迭代，则更为有效。删除的算法相应复杂一些，但也可以承受。
API
add：将数加入树
remove：从树中删除指定的节点
contains：树中是否包含指定的数
ordinal：从小到大遍历打印数（测试只用）
max：查找最大值
min：查找最小值
其中Node类是辅助类，为了简单没有写标准的 get，set方法。
因为该树没有自我保持平衡的能力，因此对于随机插入的数据，效果较好，对于有局部生降序特征的插入序列，则会失去平衡，极端状况下，树退化成链表。关于平衡树请参见（Tree2-3-4 ，红黑树 ,Tree-2-3 )
Tree的main函数仅为测试之用。
class Node {
private int value;
private Node left;
private Node right;
Node(int value) {
this.value = value;
}
int value() {
return value;
}
void left(Node left) {
this.left = left;
}
void right(Node right) {
this.right = right;
}
Node left() {
return left;
}
Node right() {
return right;
}
}
class Tree {
private Node root;
void add(int value) {
Node node = new Node(value);
if(root == null) root = node;
else add(root,node);
}
private void add(Node current, Node node) {
if(node.value() < current.value()) {
if(current.left() == null) current.left(node);
else add(current.left(), node);
} else if(node.value() > current.value()) {
if(current.right() == null) current.right(node);
else add(current.right(), node);
}
}
boolean contains(int value) {
if(root == null) return false;
else return contains(root,value);
}
private boolean contains(Node current, int value) {
if(current == null) return false;
if(current.value() == value) return true;
if(value < current.value()) return contains(current.left(),value);
else return contains(current.right(),value);
}
void remove(int value) {
remove(null,root,value);
}
private void remove(Node parent, Node current, int value) {
if(current == null) return;
if(current.value() == value) {
Node node;
if(current.left() == null && current.right() == null) node = null;
else if (current.left() != null && current.right() == null) node = current.left();
else if (current.right() != null && current.left() == null) node = current.right();
else {
node = removeMin(current,current.right());
node.left(current.left());
node.right(current.right());
}
if(parent == null) root = node;
else if(parent.left() == current) parent.left(node);
else parent.right(node);
} else if(value < current.value()) remove(current,current.left(),value);
else remove(current,current.right(),value);
}
private Node removeMin(Node parent, Node current) {
if(current.left() != null) return removeMin(current,current.left());
else {
if(parent.left() == current) parent.left(current.right());
else parent.right(current.right());
return current;
}
}
int max() {
if(root == null) return -1;
else return max(root);
}
private int max(Node current) {
if(current.right() == null) return current.value();
else return max(current.right());
}
int min() {
if(root == null) return -1;
else return min(root);
}
private int min(Node current) {
if(current.left() == null) return current.value();
else return min(current.left());
}
void ordinal() {
if (root == null) return;
else ordinal(root);
}
void ordinal(Node current) {
if(current.left() != null) ordinal(current.left());
System.out.println(current.value() + ” “);
if(current.right() != null) ordinal(current.right());
}
public static void main(String[] args) {
Tree t = new Tree();
t.add(50);
t.add(6);
t.add(29);
t.add(100);
t.add(34);
t.add(45);
t.add(4);
t.add(68);
t.ordinal();
System.out.println(t.contains(34));
assert t.contains(34);
assert t.contains(6);
assert !t.contains(110);
assert t.max() == 100;
assert t.min() == 4;
t.remove(50);
t.remove(45);
t.remove(6);
t.ordinal();
}
}
Copyright © 2009 - 我想网 板凳 | SiteMap | Entries (RSS) | Comments (RSS)
WordPress theme by 
9th sphere website design