Array

无序数组：

	不允许重复	允许重复
查找	N/2次比较	N次比较
插入	无比较、一次移动	无比较、一次移动
删除	N/2次比较、N/2次移动	N次比较、大于N/2次移动

 1 public class Array {
 2 
 3     private long[] array;
 4     
 5     private int maxLength;
 6     
 7     public Array(int size){
 8         array = new long[size];
 9         maxLength = 0;
10     }
11     
12     public void insert(long l){
13         array[maxLength++] = l;
14     }
15     
16     public int find(long key){
17         for(int i = 0 ; i < maxLength ; i++){
18             if(array[i] == key){
19                 return i;
20             }
21         }
22         return -1;
23     }
24     
25     //删除之后必须随后的数据向前移一步补这个洞
26     public boolean delete(long key){
27         int index = find(key);
28         if(index < 0){
29             return false;
30         }else{
31             for(int i = index; i < maxLength-1; i++){
32                 array[i] = array[i+1];
33             }
34             maxLength --;
35         }
36         return true;
37     }
38     
39     public void display(){
40         for(int i = 0 ; i < maxLength; i++){
41             System.out.println("NO." + (i+1) + " --> " +  array[i]);
42         }
43     }
44     
45 }

 1     public static void main(String[] args) {
 2         Array array = new Array(100);
 3 
 4         array.insert(49);
 5         array.insert(158);
 6         array.insert(81);
 7         array.insert(93);
 8         array.insert(18);
 9         
10         array.delete(81);
11         array.delete(82);
12         
13         array.display();
14     }

打印结果：
NO.1 --> 49
NO.2 --> 158
NO.3 --> 93
NO.4 --> 18

有序数组：

核心插入数据后保证数组的数据必须是有序的，查找可以用二分查找。

 1 public class OrderArray {
 2 
 3     private long[] array;
 4     
 5     private int maxLength;
 6     
 7     public OrderArray(int size){
 8         array = new long[size];
 9         maxLength = 0;
10     }
11     
12     /*public void insert(long l){
13         int index = -1;
14         for(int i = 0 ; i < maxLength; i++){
15             if(array[i]>l){
16                 index = i;
17                 break;
18             }
19         }
20         if(index == -1){
21             array[maxLength++] = l;
22             return;
23         }
24         for(int i = maxLength ; i > index; i --){
25             array[i] = array[i-1];
26         }
27         array[index] = l;
28         maxLength++;
29     }*/
30     
31     //插入时判断大小，保证有序。
32     public void insert(long l){
33         int i ;
34         for(i = 0 ; i < maxLength; i++){
35             if(array[i]>l){
36                 break;
37             }
38         }
39         for(int j = maxLength ; j > i; j --){
40             array[j] = array[j-1];
41         }
42         array[i] = l;
43         maxLength++;
44     }
45     
46     //二分查找
47     public int find(long key){
48         int lower = 0;
49         int upper = maxLength-1;
50         int index ;
51         while(true){
52             index = (lower + upper)/2;
53             if(array[index]==key){
54                 return index;
55             }else if(lower > upper){
56                 return -1;
57             }else{
58                  if(array[index] < key){
59                      lower = index + 1 ;
60                  }else{
61                      upper = index - 1 ;
62                  }
63             }
64         }
65     }
66     
67     public boolean delete(long key){
68         int index = find(key);
69         if(index < 0){
70             return false;
71         }else{
72             for(int i = index; i < maxLength-1; i++){
73                 array[i] = array[i+1];
74             }
75             maxLength --;
76         }
77         return true;
78     }
79     
80     public void display(){
81         for(int i = 0 ; i < maxLength; i++){
82             System.out.println("NO." + (i+1) + " --> " +  array[i]);
83         }
84     }
85     
86 }

 1     public static void main(String[] args) {
 2         OrderArray array = new OrderArray(100);
 3 
 4         array.insert(49);
 5         array.insert(158);
 6         array.insert(81);
 7         array.insert(93);
 8         array.insert(18);
 9         array.insert(1);
10         array.insert(9);
11         array.insert(7);
12         array.insert(81);
13         array.insert(669);
14         
15         array.display();
16         
17         int key = 18;
18         System.out.println(key + " is NO " + (array.find(key)+1));
19     }

打印结果：
NO.1 --> 1
NO.2 --> 7
NO.3 --> 9
NO.4 --> 18
NO.5 --> 49
NO.6 --> 81
NO.7 --> 81
NO.8 --> 93
NO.9 --> 158
NO.10 --> 669
18 is NO 4

二分查找步数：
如果一组数组的个数为r，那么二分查找的步数为：s=log₂r

无序数组的插入：常数
因为无序数组的插入总是放到下一个有空的地方。无论数据项N有多大，一次插入的时间总是相同的。所以可以说向一个无序数组插入数据的时间T的表示为：
T = 1 * K （K是指现实中影响时间的因素，比如：CPU、编辑器生成class的效率等等）

线性查找：与 N 成正比
T = K * N / 2
将 2 并入Ｋ中可以得到一个方便的公式：
Ｔ=K * N ，这个方程式说明了线性查找的时间与数据项的个数成正比，如果一个数组增加一倍个数，那么查找的时间也会变成原来的2倍。

二分查找：与log(N) 成正比
二分查找的时间：T=K * log₂(N)，但是因为从底数为2转为底数为10只需要乘以3.2222，所以底数2也并入K值中，不必指定底数：
T = K * log(N)

大O表示法与以上公式类似，当比较算法的时候，并不在乎CPU或是编译器，真正比较的是N值的大小，所以不需要常数。
大O表示法的实质并不是对运行时间给出实际值，而是表达了运行时间如何受数据项的个数影响。

算法	大O表示法的运行时间
线性查找	O(N)
二分查找	O(logN)
无序数组的插入	O(1)
有序数组的插入	O(N)
无序数组的删除	O(N)
有序数组的删除	O(N)

以上显示一些时间与数据项的个数的大O关系，可以看出O(1)是最好的，O(logN)良好，O(N)还可以，O(N²)则差了些。O(N²)会在冒泡排序或其它排序出现。