一般的なデータ構造とアルゴリズム(アルゴリズム編)

検索とソートは最も基礎的で最も重要な2種類のアルゴリズムであり、この2種類のアルゴリズムを熟練して把握し、これらのアルゴリズムの性能を分析することが重要であり、この2種類のアルゴリズムには主に二分検索、高速ソート、集計ソートなどが含まれている.まず検索アルゴリズムを理解しましょう!シーケンシャル検索:シーケンシャル検索は線形検索とも呼ばれます.そのプロセスは、検索テーブルの最後の要素から1つずつ指定されたキーワードと比較し、あるレコードのキーワードと指定された値が比較的等しい場合、検索に成功します.そうしないと、最初のレコードまでキーワードと指定された値の比較が等しくない場合、テーブルに検索されていないレコードが検索に成功しないことを示し、効率が低下するという欠点があります.二分検索:二分検索は折半検索とも呼ばれ、秩序テーブルにとって比較回数が少なく、検索速度が速く、平均性能が良いという利点があります.二分探索の基本思想は、n個の要素をほぼ等しい2つの部分に分け、a[n/2]を目標値xと比較し、x=a[n/2]であればxを見つけ、アルゴリズムは中止し、xがa[n/2]未満であれば、配列aの左半分でxを探索し続け、x>a[n/2]であれば、配列aの右半分でxを探索する.コードは以下のように実現される.

public int funBinSearch(int[] array,int data){

    int low=0;
    int high=array.length-1;

    while(low<=high){
        int mid=(low+high)/2;
        if(data==array[mid]){
            return mid;
        }else if(data<array[mid]){
            high=mid-1;
        }else{
            low=mid+1;
        }
    }
    return -1;
}

ソートはコンピュータプログラム設計における重要な操作であり、データ要素(または記録)の任意のシーケンスをキーワード順に並べ替える機能を備えています.以下は主にいくつかのよく見られるソートアルゴリズムについて紹介する.まず泡のソートを理解しましょう!バブルソート:バブルソートの基本思想は、ソートシーケンスの記録個数をnとし、n-1回の遍歴を行い、毎回遍歴が開始位置から前後に隣接する要素を順次後方に比較することであり、このように大きな要素が後方に移動し、n-1回の遍歴が終了すると、シーケンスが秩序化する.あるループで交換が発生しない場合は、シーケンスが秩序化されているため、次のループを行う必要はありません.コードは次のように実装されます.

    public void bubbleSort(int[] array){
        boolean flag=true;
        for(int i=0;i<array.length-1&&flag;i++){
            //              ,            ,        
            flag=false;
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    int temp=array[i];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                    flag=true;
                }
            }
        }
    }

単純選択ソート:単純選択ソートの考え方は、ソートシーケンスのレコード個数をnとし、1ラウンドごとにn-2-i回選択し、n-i-1(i=1,2,...,n-1)個のレコードのうちキーワードが最小のレコードを有効シーケンスのi番目のレコードとして選択することである.コードは次のように実装されます.

    public void selectionSort(int[] array){
        for(int i=0;i<array.length-1;i++){
            int mink=i;
            //                 
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[mink]){
                    mink=j;
                }
            }

            //         
            if(mink!=i){
                int temp=array[mink];
                array[mink]=array[i];
                array[i]=temp;
            }
        }
    }

直接挿入ソート:直接挿入の考え方は、順序付けされた順序付けテーブルにレコードを挿入し、新しい、記録数が1増加した順序付けテーブルを得ることです.

    public void insertSort(int[] array){
        int j;
        for(int i=1;i<array.length;i++){
            int temp=array[i];
            j=i-1;
            while(j>-1&&temp<array[j]){
                array[j+1]=array[j];
                j--;
            }
            array[j+1]=temp;
        }
    }

ヒルソート:
ヒルソートは「縮小インクリメンタルソート」とも呼ばれ、直接挿入ソートの以下の2つの性質に基づいて提案された改良である:(1)直接挿入ソートは、ほぼ並べ替えられたデータに対して操作する際に、効率が高く、すなわち線形ソートの効率を達成することができる.(2)直接挿入ソートは一般的に非効率である.挿入ソートは毎回データを1ビットしか移動できないからである.ヒルソート

public void xier(int[] arrays,int n){
        int gap=n/2;
        for(;gap>0;gap=gap/2){
            for(int i=0;iint temp=a[i];
                int j=i-gap;
                while(j>=0&&temp

クイックソート:クイックソートの主な考え方は、ソートされるシーケンスの中でプライマリと呼ばれる要素を選択し、配列を2つの部分に分けて、第1の部分のすべての要素がプライマリと等しいようにし、第2の部分のすべての要素がプライマリより大きいようにし、2つの部分にクイックソートアルゴリズムを再帰的に適用することです.高速ソートアルゴリズムを簡単に理解する.

public void quickSort(int[] s,int left,int right){
        if(1int i=left,j=right,temp=s[left];
            while(iwhile(i=temp){//          temp  
                    j--;
                }
                if(iwhile(i//            temp  
                    i++;
                }
                if(i1);//    (   )
            quickSort(s,i+1,right);
        }
    }

ヒープソート:ヒープソートについて説明する前に、まずヒープの定義を理解する必要があります.n個のキーワードシーケンスK 1,K 2,...,Knをヒープと呼びます.このシーケンスが以下の性質(略称ヒープ特性)を満たす場合にのみ、(1)ki<=k(2 i)、ki<=k(2 i+1)(1≦i≦n/2)、もちろん、これは小根ヒープであり、大根ヒープは>=番号に変更されます.スタックの性質を満たすシーケンスを完全なツリーと見なす場合、スタックの意味は、完全なツリーのすべての非終端ノードの値が、その左右の子供ノードの値より大きくない(または小さくない)ことを示す.スタックソートの主な考え方は、ソートされるシーケンスを与え、まず調整を経て、シーケンスを大きなトップスタックに構築することである.このとき、最初の要素は最大の要素であり、シーケンスの最後の要素と交換し、前のn-1の要素を大きなトップスタックに調整し、最初の要素と末尾の要素を交換することで、最後に秩序シーケンスを得ることができる.スタックのソートは簡単です.

//  
    //  :        ,       ,    
    public void heapify(int[] arrays,int currentRootNode,int size){

        if(currentRootNode//          
            int left=2*currentRootNode+1;
            int right=2*currentRootNode+2;

            //            
            int max=currentRootNode;
            if(left//          ,      
                if(arrays[max]max=left;
                }
            }
            if(right//          ,      
                if(arrays[max]max=right;
                }
            }
            //            ,     
            if(max!=currentRootNode){
                int temp=arrays[max];
                arrays[max]=arrays[currentRootNode];
                arrays[currentRootNode]=temp;

                //    ,        
                heapify(arrays,max,arrays.length);
            }
        }
    }

    //      ,        (   )
    public void maxHeapify(int[] arrays,int size){

        //        ,       (   0)
        for(int i=size-1;i>=0;i--){
            heapify(arrays,i,size);
        }
    }

    for(int i=0;ilength;i++){

        //             
        maxHeapify(arrays,arrays.length-i);

        //  
        int temp=arrays[0];
        arrays[0]=arrays[arrays.length-1-i];
        arrays[length-1-i]=temp;
    }

集計ソート:集計ソート(merge sort)は、挿入ソート、交換ソート、選択ソートとは異なる別のソート方法です.集計とは、2つ以上の順序付きテーブルを新しい順序付きテーブルに統合することを意味します.安定したソートですjavautil.Arraysクラスにおけるsort法は,集計並べ替えの変異体を用いて実現した.「深く理解する」-集計ソートアルゴリズム.

public void mergeSort(int[] arrays){
        if(arrays.length>1){
            sort(arrays,0,arrays.length);
        }
    }

    //    
    //   (     )                   
    //         ,         .           
    //      
    //       ,      
    public int[] sort(int[] nums,int low,int high){
        int mid=(low+high)/2;
        if(low//    
            sort(nums,low,mid);
            //    
            sort(nums,mid+1,high);
            //    
            merge(nums,low,mid,high);
        }
        return nums;
    }

    public void merge(int[] nums,int low,int mid,int high){
        //        
        int[] temp=new int[high-low+1];
        int i=low;
        int j=mid+1;
        int k=0;
        //         temp   
        while(i<=mid&&j<=high){
            if(nums[i]else{
                temp[k++]=nums[j++];
            }
        }
        //      
        while(i<=mid){
            temp[k++]=nums[i++];
        }
        while(j<=high){
            temp[k++]=nums[j++];
        }
        //  temp      nums    
        for(int k2=0;k2

より多くのアルゴリズムの内容はよく見られるデータ構造とアルゴリズムの整理と総括を閲覧することができる(下).