一，概述
许多将要讨论到的算法直接适用于某些特殊的数据结构。对于大多数数据结构来说，都需要知道如何
插入一条新的数据
寻找某一条特定的数据项
删除某一特定的数据项
1，数据结构的特征：
数据结构 优点 缺点
数组 插入快，如果有下标，可以非常快的存取 查找慢，删除慢，大小固定
有序数组 比无序的数组查找快 删除和插入慢，大小固定
栈 提供后进先出方式的存取 存取其他项很慢
队列 提供先进先出方式的存取 存取其他项很慢
链表 插入快，删除快 查找慢
二叉树 查找，插入，删除都快（如果树保持平衡） 删除算法复杂
红-黑树 查找，插入，删除都快。数总是平衡的 算法复杂
2-3-4 树 查找，插入，删除都快。树总是平衡的 算法复杂
类似的树对磁盘存储有用。
哈希表 如果关键字已知则存取极快。插入快 删除慢，如果不知道关键字则存取很慢，对
存储空间是用不充分。
堆 插入，删除快，对最大数据项的存取很快 对其他数据项存取很慢
图 对现实世界建模 有些算法慢且复杂
二 ，数组
数组是应用最广泛的数据存储结构。他被植入到大部分编成语言中，由于数组十分易懂，所以它被用来作为介绍数据结构的起步点，并展示面向对象编程的数据结构之间的相互关系。
使用二分法可以大大提高检索速度，减少查询次数。
二分法所需要的比较次数
范围 次数
10 4
100 7
1000 10
10000 14
100000 17
1000000 20
10000000 24
100000000 27
1000000000 30
根据上面的二分法查询次数，我们还可以推断出来一个方程式：
r = 2*2....s;(s表示步数（次数），乘2的次数，即2的幂)， r表示范围。
例如:如果是已知步数s,通过这个方程就可以得出范围r,如: 如果s是6,则范围应该是64;
同样可以根据对数来计算其相应的次数.
大O表示法:
在计算机算法中,我们使用一种粗略的度量算法效率的方法称作"大O"表示法.
在比较算法时似乎应该说一些类似"算法A比算法B快两倍"之类的话，但实际上这些陈述并没有多大意义。这是由于当数据项个数变化时，对应的比例也会发生根本改变。
用大O表示法表示运行时间
算法 大O表示法表示的运行时间
线性查找 O(N)
二分查找 O(logN)
无序数组的插入 O(1)
有序数组的插入 O(N)
无序数组的删除 O(N)
有序数组的删除 O(N)
上面的显示了时间与数据项个数的大O关系。通过它我们可以比较不同的大O值（非常主观）
：O(1)是优秀，O(logN)是良好， O(N) 还可以，O(N的平方)则差了一些。
三,简单排序
一旦建立了一个重要的数据库后,就可能根据某些需求对数据进行不同方式排序.比如对姓名按字母序排序,对学生按年级排序,对顾客按邮政编码排序,对国内销售品按价格排序,等.
对数据进行排序有可能是检索的一个初始步骤.正如在第二章"数组"中看到的那样,二分查找法比线性查找法要快的多,然而它只能应用于有序的数据.
冒泡排序
冒泡排序算法运行起来非常慢,但在概念上他是排序算法中最健的,因此冒泡排序算法在刚开始研究排序技术时是一个非常好的算法.
冒泡算法要遵循的规则(一组数按照从小到大的顺序排序 从左到右)
1,比较两个数.
2,如果左边的值大,则两个数交换位置(如果左边的值不大那么不改变位置) .
3,向右移动一个位置,比较下面两个数.
这样一直比下去,一直比到最右端,那么最大的数就可以比较出来了.
冒泡排序的java代码:
package sort;
/** *//**
* 冒泡排序
* @author jason
*
*/
public class BubbleSort
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayBub arr; // reference to array
arr = new ArrayBub(maxSize); // create the array
arr.insert(77); // insert 10 items
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(); // display items
arr.bubbleSort(); // bubble sort them
arr.display(); // display them again
} // end main()
}
class ArrayBub {
private long[] a; // ref to array a
private int nElems; // number of data items
// --------------------------------------------------------------
public ArrayBub(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
// --------------------------------------------------------------
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
// --------------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
// --------------------------------------------------------------
public void bubbleSort()
{
int out, in;
for(out=nElems-1; out>1; out--) // outer loop (backward)
for(in=0; in<out; in++) // inner loop (forward)
if( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
} // end bubbleSort()
// --------------------------------------------------------------
private void swap(int one, int two)
{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
// --------------------------------------------------------------
} // end class ArrayBub上面的代码中为了清晰起见,使用了一个独立的swap()方法来执行交换操作,实际上使用一个独立的swap()方法不一定好,因为方法调用会增加一些额外的消耗.最好还是将交换方法直接放到程序中,这样可以提高一些速度.
通过上面的程序,我们可以看到,比较执行的次数
为: 9+8+7+6+5+4+3+2+1=45
公式为: N*(N-1)/2
因为两个数值只有在需要时才交换,所以交换的次数少于比较的次数.如果数据是随机的那么大概有一半数据需要交换.
冒泡排序运行需要时间可以认为：O(N平方)这个级别算法速度很慢。
选择排序：
选择排序改进了冒泡排序，将交换次数从O(N平方)减少到O(N),但是比较次数仍为 O(N平方).然而,选择排序仍然为大记录的排序提出一个非常重要的改进,因为这些大量的记录需要在内存中移动,这就是交换的时间和比较时间相比起来,交换时间更为重要.(一般来说,在java语言中不是这种情况,java中只是改变引用位置,而实际对象的位置并没有发生改变.)
选择算法要遵循的规则(一组数按照从小到大的顺序排序 从左到右)
1,从当前所有数中选择一个最小的 ,放在第一位(换位),然后从第二个开始同样选择最小的.
开始向右移动,选择对小的放在第二位,以此这样操作。
就可以得到排序的效果。
选择排序的程序代码 ：
package sort;
/** *//**
* 选择排序
* @author jason
*
*/
public class BubbleSort
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayBub arr; // reference to array
arr = new ArrayBub(maxSize); // create the array
arr.insert(77); // insert 10 items
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(); // display items
arr.bubbleSort(); // bubble sort them
arr.display(); // display them again
} // end main()
}
class ArrayBub {
private long[] a; // ref to array a
private int nElems; // number of data items
// --------------------------------------------------------------
public ArrayBub(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
// --------------------------------------------------------------
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
// --------------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
// --------------------------------------------------------------
public void bubbleSort()
{
int out, in;
for(out=nElems-1; out>1; out--) // outer loop (backward)
for(in=0; in<out; in++) // inner loop (forward)
if( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
} // end bubbleSort()
// --------------------------------------------------------------
private void swap(int one, int two)
{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
// --------------------------------------------------------------
} // end class ArrayBub
插入排序
在大多数情况下，插入排序是比上面两种排序算法要好的一种，虽然算法仍然要O(N平方)的时间，但在一般情况下，它要比冒泡排序快一倍，比选择排序还要快一点。尽管它比冒泡排序算法和选择算法都更麻烦一些，但它也并不很复杂。他经常被用在较复杂的排序算法的最后阶段，例如快速排序。
插入算法原理：
插入算法要遵循的规则(一组数按照从小到大的顺序排序 从左到右)
插入排序，从第一位开始，如果第二位小于第一位，那么第一位和第二位换位，第一位与第二位有正确的顺序，
这时排序好的第二位与第三位比较，如果第三位小于第二位，那么拿出第三位的值，并且把第二位移到第三位上，
然后比较这个临时值（原来的第三位）与第一位比较，如果第一位也大于第三位,那么同样,第一位移到原来第二位的位置
这个临时值就占据了第一位,如果一位的值小于临时值(原来的第三位),则第一位不变,第二位为临时值,以此类推
就是插入算法的原理.
插入算法就是对一个有序的序列,进行插入操作.
插入排序代码:
package sort;
/** *//**
*
* @author jason
*
*/
class ArrayIns
{
private long[] a; // ref to array a
private int nElems; // number of data items
//--------------------------------------------------------------
public ArrayIns(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
//--------------------------------------------------------------
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
//--------------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
//--------------------------------------------------------------
public void insertionSort()
{
int in, out;
for(out=1; out<nElems; out++) // out is dividing line
{
long temp = a[out]; // remove marked item
in = out; // start shifts at out
while(in>0 && a[in-1] >= temp) // until one is smaller,
{
a[in] = a[in-1]; // shift item to right
--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
} // end insertionSort()
//--------------------------------------------------------------
} // end class ArrayIns
////////////////////////////////////////////////////////////////
class InsertSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize); // create the array
arr.insert(77); // insert 10 items
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(); // display items
arr.insertionSort(); // insertion-sort them
arr.display(); // display them again
} // end main()
} // end class InsertSortApp