数据结构回顾---排序，查找

首先说一下查找

    查找大概有一下几种：
   1.顺序查找，他的思想是：从起始位置开始，到结束，一个一个的去找，相当于是遍历一次数组，这个是基本的，

   2.折半查找，也叫二分发，他是对顺序查找的优化，折半查找有个硬性的要求，就是要查找的数组必须是有序的，否则没法实现。他的思想是：首先确定一个数组的中间位置的值，然后要查找的值和中间位置的这个值比较。如果相等了，则说明找到，如果小于（假设数组是正序的），则将查找区域设置在左半部分，如果是大于，则说明查找值在右半部分，一次类推，直到找到为止。
 
   非递归实现
   public static int zbcz(int a[], int key) {
int max = a.length;
int min = 0;

int mid = 0;

while (min <= max) {

mid = (min + max) / 2;
if (key == a[mid]) {
return mid;
} else if (key > a[mid]) {
min = mid + 1;
} else {
max = mid - 1;
}

}
return -1;
}
//递归实现

public static int dgzbcz(int[] a, int max, int min, int key) {
int mid = (max + min) / 2;
if (min > max) {
return -1;
}
if (key == a[mid]) {
return mid;
} else if (key > a[mid]) {
return dgzbcz(a, max, mid + 1, key);
} else {
return dgzbcz(a, mid - 1, min, key);
}

}
做了一下简单测试，建立一个int数组，大小为1000000000/7（再大内存溢出了），然后循环查找1000000000/7次。如下

    long start = System.currentTimeMillis();
// 折半查找 非递归
for (int i = 0; i < a.length; i++) {
zbcz(a, i);
}
System.out
.println("非递归找到花费时间为：" + (System.currentTimeMillis() - start));

使用大概在7.050秒上下，

  递归模式测试

   start = System.currentTimeMillis();
for (int i = 0; i < a.length; i++) {
//     System.out.println(zbcz(a, 10000000 - 1));
dgzbcz(a, a.length - 1, 0, 10000000 - 1);
}


System.out.println("递归找到花费时间为：" + (System.currentTimeMillis() - start));

大概使用时间为7200，由此可以看出来，递归需要花费的时间还是比非递归的要多一点，但是差异不是很大，

另外用同样的数字测试了一下顺序查找，结构死了，等了好久都没出来。

      3.分块查找

    　分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。我们可以理解他需要两个列表，一个是用来存放数据的，一个是用来存放索引列的，

          （1）"分块有序"的线性表
    　表R[1..n]均分为b块，前b-1块中结点个数为   ，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是"分块有序"的

         　抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即：
ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。

分块查找的基本思想是：
（1）首先查找索引表
　　索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。

（2）然后在已确定的块中进行顺序查找
　　由于块内无序，只能用顺序查找。

今天就说这些吧，开始工作！！！！！！！！！