Javaの順序配列データ構造と二分探索アルゴリズムの解析

この記事では、主に Java のデータ構造とアルゴリズム (順序付けされた配列と二分探索) について詳しく説明します。興味のある方は参考にしてください。

順序付けされた配列では、二分探索がよく使用されます。検索速度を向上させるために使用されます。現在、配列の追加、削除、変更、検索を実装するために、逐次検索と二分検索を使用しています。

2. 順序付き配列の長所と短所

利点: 順序なし配列よりも検索速度がはるかに高速です 欠点: 挿入時に、次のデータをソートされた方法で移動する必要があります

3. 順序付き配列と順序なし配列配列 順序配列の一般的な利点と欠点

データを削除するときは、削除された項目の抜け穴を埋めるために次のデータを前方に移動する必要があります

4. コードの実装

public class OrderArray {
  
   private int nElemes; //记录数组长度
   
   private long[] a;
   
   /**
   * 构造函数里面初始化数组 赋值默认长度
   *
   * @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; //返回大于最大索引整数
       }else{ //还要继续找
         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++;
   }
   
   //删除数据项
   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;
   }
}

5. テスト

りー

以上がJavaの順序配列データ構造と二分探索アルゴリズムの解析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。