package aa;
class Array{
//定义一个有序数组
private long[] a;
//定义数组长度
private int nElems;
//构造函数初始化
public Array(int max){
a = new long[max];
nElems = 0;
}
//size函数
public int size(){
return nElems;
}
//定义添加函数
public void insert(long value){
//将value赋值给数组成员
a[nElems] = value;
//然后将数组长度加一
nElems ++;
long temp;
//用冒泡法排序
for(int i = 0; i < nElems - 1; i ++)
{
for(int j = 0; j < nElems - 1 - i; j++)
{
if(a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
//定义查找方法
public int find(long searchKey){
//因为是有序数组，我们可以用二分法来查找时间为 O(logN),如果线性查找则为O(N)
//下限
int lowerBound = 0;
//上限
int upperBound = nElems -1;
//中间值
int curIndex;
while(true)
{
curIndex = (lowerBound + upperBound) / 2;
if(a[curIndex] == searchKey)
{
return curIndex;
}
else if(lowerBound > upperBound)
{
return nElems;
}
else
{
if(a[curIndex] > searchKey)
{
upperBound = curIndex -1;
}
else
{
lowerBound = curIndex + 1;
}
}
}
}
//定义删除方法
public boolean delete(long value){
int index = find(value);
if(index == size())
{
return false;
}
else
{
for(int i = index; i < size(); i++)
{
a[i] = a[i + 1];
}
nElems --;
return false;
}
}
//定义显示方法
public void display(){
for(int j = 0; j < nElems; j++)
{
System.out.println(a[j] + " ");
}
System.out.println("");
}
}
public class Arr {
public static void main(String[] args)
{
int maxSize = 100;
Array arr = new Array(maxSize);
arr.insert(77);
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(22);
arr.insert(66);
arr.insert(33);
arr.display();
int searchKey = 54;
if(arr.find(searchKey) != arr.size())
{
System.out.println("found" + searchKey);
}
else
{
System.out.println("cant find" + searchKey);
}
arr.delete(22);
arr.delete(55);
arr.delete(99);
arr.display();
}
}
package aa;
//定义一个无序数组
class HighArray{
private long[] a;
private int nElems;
public HighArray(int max)
{
a = new long[max];
nElems = 0;
}
public boolean find(long searchKey)
{
int j;
for(j = 0; j < nElems; j++)
{
if(a[j] == searchKey)
{
break;
}
}
if(j == nElems)
{
return false;
}
else
{
return true;
}
}
public void insert(long value)
{
a[nElems] = value;
nElems++;
}
public boolean delete(long value)
{
int j;
for(j = 0; j < nElems; j++)
{
if(value == a[j])
{
break;
}
}
if(j == nElems)
{
return false;
}
else
{
for(int k = j; k < nElems; k++)
{
a[k] = a[k+1];
}
nElems --;
return true;
}
}
public void display()
{
for(int j = 0; j < nElems; j++)
{
System.out.println(a[j] + "");
}
System.out.println("");
}
}
public class highArrayApp {
public static void main(String[] args)
{
int maxSize = 100;
HighArray arr = new HighArray(maxSize);
arr.insert(77);
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();
int searchKey = 35;
if(arr.find(searchKey))
{
System.out.println("Found" + searchKey);
}
else
{
System.out.println("cant find" + searchKey);
}
arr.delete(00);
arr.delete(55);
arr.delete(99);
arr.display();
}
}
大O表示法
O(1)：优秀。例如无须数组插入。
O(logN)：良好。例如有序的二分查找。
O(N):及格。例如无序数组的删除，有序数组的删除和插入，线性查找。
O(N2):不及格。例如冒泡排序。
总结有序数组和无序数组
有序数组：插入+ 查找 +删除 = O(N) +O(logN)+O(N);
无序数组：插入 + 查找 + 删除 = O(1) + O(N) + O(N);
所以在数据偏向查找操作的时候用有序数组快一些，在数据偏向插入的时候，无序数组好一些。删除操作效率一样。