数据结构与算法(1)

java数据库结构与算法

一，概述

 

许多将要讨论到的算法直接适用于某些特殊的数据结构。对于大多数数据结构来说，都需要知道如何

插入一条新的数据
寻找某一条特定的数据项
删除某一特定的数据项

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

 

 还没有完成----

分享到：

成功12级跳 | 常用数据库函数对比(1)

• 2008-08-01 13:45
• 浏览 1274
• 评论(0)
• 查看更多