詳解Java數(shù)據(jù)結(jié)構(gòu)和算法（有序數(shù)組和二分查找）

更新時間：2017年09月23日 16:21:29 作者：臨窗聽雨

本篇文章主要介紹了詳解Java數(shù)據(jù)結(jié)構(gòu)和算法（有序數(shù)組和二分查找），具有一定的參考價值，感興趣的小伙伴們可以參考一下

一、概述

有序數(shù)組中常常用到二分查找，能提高查找的速度。今天，我們用順序查找和二分查找實(shí)現(xiàn)數(shù)組的增刪改查。

二、有序數(shù)組的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：查找速度比無序數(shù)組快多了
缺點(diǎn)：插入時要按排序方式把后面的數(shù)據(jù)進(jìn)行移動

三、有序數(shù)組和無序數(shù)組共同優(yōu)缺點(diǎn)

刪除數(shù)據(jù)時必須把后面的數(shù)據(jù)向前移動來填補(bǔ)刪除項(xiàng)的漏洞

四、代碼實(shí)現(xiàn)

public class OrderArray {
  
   private int nElemes; //記錄數(shù)組長度
   
   private long[] a;
   
   /**
   * 構(gòu)造函數(shù)里面初始化數(shù)組 賦值默認(rèn)長度
   *
   * @param max
   */
   public OrderArray(int max){
     this.a = new long[max];
     nElemes = 0;
   }
   
   //查找方法 (二分查找)
   public int find(long searchElement){
     int startIndex = 0;
     int endIndex = nElemes-1;
     int curIn;
     while(true){
       curIn = (startIndex + endIndex)/2;
       if(a[curIn]==searchElement){
         return curIn; //找到
       }else if(startIndex>endIndex){ //沒有找到
         return nElemes; //返回大于最大索引整數(shù)
       }else{ //還要繼續(xù)找
         if(a[curIn]<searchElement){
           startIndex = curIn + 1; //改變最小索引
         }else{ //往前找
           endIndex = curIn -1;
         }
       }
       
     }
   }
   
   
   //插入元素（線性查找）
   public void insert(long value){
     int j;
     for(j=0;j<nElemes;j++){
       if(a[j]>value){
         break;
       }
     }
     for(int k=nElemes;k>j;k--){
       a[k] = a[k-1];
     }
     a[j] = value;
     nElemes++;
   }
   
   //刪除數(shù)據(jù)項(xiàng)
   public boolean delete(long value){
     int j = find(value);
     if(j==nElemes){
       return false; //沒找到
     }else{
       //所有元素往前移動一位
       for(int k=j;k<nElemes;k++)
       a[k] = a[k+1];
       
       nElemes--;
       return true;
     }
   }
   //展示的方法
   public void display(){
     for(int i=0;i<nElemes;i++){
       System.out.print(a[i]+" ");
     }
   }
   
   public int size(){
     return nElemes;
   }
}

五、測試

 public static void main(String[] args) {
     int max = 100;
     OrderArray oa = new OrderArray(max);
     oa.insert(12);
     oa.insert(14);
     oa.insert(90);
     oa.insert(89);
     oa.insert(87);
     oa.insert(88);
     oa.insert(67);
     oa.display();
     int searchkey = 90;
     if(oa.find(searchkey)!=oa.size()){
       System.out.println("found"+searchkey);
     }else{
       System.out.println("not found");
     }
     oa.delete(88);
     oa.delete(90);
     oa.delete(89);
     oa.display();
   }

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: