検索とソートアルゴリズムのまとめ&関連応用アルゴリズム

Byteは事前に二つの面で自分が二分で探した変形問題で車をひっくり返したので、今は面接が合格するかどうか分からないので、面接が終わった後、本当に自分がこんな簡単な問題で車をひっくり返すことを許すことができないような気がします.自分がアルゴリズムの准备の上でまだ十分だと思って、もとは自分が高い目标を持って、ずっと比较的に难しいアルゴリズムを见て、着実に基础のアルゴリズムを掌握していません.インターンシップから面接まで、7月中ずっと人間として教えられ、着実に勉強しましょう.
1二分検索とその応用
二分探索の基本思想(二叉探索木も二分探索の範疇とすべき)二分探索の基本思想は:(R[low,high]を現在の探索区間とする)(1)まず当該区間の中点位置を確定する:(2)次に調べるK値とR[mid].key比較:等しい場合、検索に成功してこの位置に戻る.そうでない場合、新しい検索区間を確定し、二分検索を継続しなければならない.具体的な方法は以下の通りである:1 R[mid]である.key>Kである、表の秩序性からR[mid,n]が分かる.keysはいずれもKより大きいため、テーブルにキーワードがKに等しいノードが存在すると、そのノードは必ず位置midの左側のサブテーブルR[1,mid−1]にあるので、新しいルックアップ区間は左サブテーブルR[1,mid−1]である.②同様に、R[mid]である.したがって、keyは、初期のルックアップ区間R[1,n]から、現在のルックアップ区間の中点位置におけるノードキーワードとの比較を1回行うごとに、ルックアップが成功したか否かを決定することができ、成功しない場合は現在のルックアップ区間を半分に縮小することができる.このプロセスは、キーワードKのノードが見つかるまで、または現在の検索区間が空(すなわち、検索に失敗)になるまで繰り返される.二分ルックアップの適用配列における局所最小値の数ソート配列に現れる回数秩序回転配列における最小値秩序回転配列における最小数k個の数を見つける−ここでpartatonと二分を組み合わせた方法の時間的複雑さと空間的複雑さが最適である
2速列とその応用
並べ替えアルゴリズムでは、高速列、スタック列、集計思想が最も多く使用されていることがわかりました.並べ替えアルゴリズムでは、キーワード(key)をピボットとして選択し、一般的にグループ記録の最初の数/最後の数を取ります.ここでは、選択シーケンスの最後の数をピボットとし、初期のピット位置でもあります.2つの変数left=0を設定します.right = N - 1;    はleftからkeyより大きい値が見つかるまで後ろに進み、その数をピットに入れ、ピット位置はarray[left]になった.キーより小さい値が見つかるまで、その数をピットに入れ、ピット位置はarray[right]になります.3と4の手順を繰り返してleftとrightが出会うまで、keyを最後のピットに入れます.

class Solution {
    public int[] sortArray(int[] nums) {
        int left=0;
        int right=nums.length-1;
        quickSort(nums,left,right);
        return nums;
    }
    public void quickSort(int[] array,int left,int right){
 	    if(left >= right)//         
    	{
		    return;
	    }
	    int index = partation(array,left,right);//     
    	quickSort(array,left,index - 1);
    	quickSort(array,index + 1,right);

    }
    public int  partation(int[] array,int left,int right){
        int key = array[right];
	    while(left < right) {
		while(left < right && array[left] <= key)
		{
			++left;
		}
		array[right] = array[left];
		while(left < right && array[right] >= key)
		{
			--right;
		}
		array[left] = array[right];	 
	}
	array[right] = key;
	return left;
    }
}

速い列の応用(実はpartationの応用)経典のオランダの国旗の問題
3スタック及び応用
ジルコニウムスタックは、完全二叉木と呼ばれるデータ構造である.≪大上位ヒープ|Maximum Heap|emdw≫:各ノードの値が、その左右のサブノードの値より大きいか、等しいかのいずれかです.小天井スタック:各ノードの値は、その左右のサブノードの値以下です.大きなトップスタック:arr[i]>=arr[2 i+1]&&arr[i]>=arr[2 i+2]、小さなトップスタック:arr[i]<=arr[2 i+1]&&arr[i]<=arr[2 i+2].1、ソート付きシーケンスを大きなトップスタックに構築し、大きなトップスタックの性質に基づいて、現在のスタックのルートノード(トップ)はシーケンスの中で最大の要素である.2、スタックトップ要素と最後の要素を交換し、残りのノードを大きなスタックに再構築する.3、手順2を繰り返して、このように繰り返して、初めて大きなトップスタックを構築してから、構築するたびに、シーケンスの最大値を得ることができて、それを大きなトップスタックの尾に置くことができます.最後に,秩序あるシーケンスが得られる.

import java.util.*;
class Solution {
    public int[] sortArray(int[] nums) {
       // Arrays.sort(nums);
        heapSort(nums);
        return nums;
    }
    public  void heapSort(int[] arr) {
		if (arr == null || arr.length == 0) {
			return;
		}
		int len = arr.length;
		//      ，            ，            
		buildMaxHeap(arr, len);
 
		//             ，     
		while(len>0){
            swap(arr,0,len-1);
            heapify(arr,0,--len);
        }
	}
 
	private  void buildMaxHeap(int[] arr, int len) {
		//                ，      ，       
		for(int i=(int)len/2;i>=0;i--){
            heapify(arr,i,len);
        }
	}
 

	private  void heapify(int[] nums, int i, int len) {
		//       ，          
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		//       （   ）    。
		int largestIndex = i;
		if (left < len && nums[left] > nums[largestIndex]) {
			//       ，         ，        
			largestIndex = left;
		}
		if (right < len && nums[right] > nums[largestIndex]) {
			//       ，         ，        
			largestIndex = right;
		}
 
		if (largestIndex != i) {
			//                 ，                   
			swap(nums, i, largestIndex);
			//       ，       ，              ，       。
			heapify(nums, largestIndex, len);
		}
	}
 
	private  void swap (int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}

スタックソートのアプリケーションウィンドウの中央値-優先キューleetcode 253を使用する.会議室II(java):最小スタック(非常によく見られる高周波という問題)データストリームの中位数分金ストライプの最小費用がプロジェクトの最大収益を行う前にK個の高周波要素の前にK個の高周波単語
4集計ソートおよび適用
「Merge Sort」は、分割法(Divide and Conquer)を用いた非常に典型的な応用である、集計操作において確立された有効で安定したソートアルゴリズムである.既存のシーケンスのサブシーケンスを結合し、完全に秩序化されたシーケンスを得る.すなわち、各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化する.2つの順序テーブルを1つの順序テーブルに結合すると、2ウェイ集計と呼ばれます.集計ソートの適用

import java.util.*;
class Solution {
    
    public int[] sortArray(int[] nums) {
        //                
        int[] help=new int[nums.length];
        mergeSort(nums,help,0,nums.length-1);
        return nums;

    }
    public void mergeSort(int[] arr,int[] help,int left,int right){
        //basecase
        if(left>=right){
            return;
        }
        int mid=left+(right-left)/2;
        mergeSort(arr,help,left,mid);
        mergeSort(arr,help,mid+1,right);
        merge(arr,help,left,mid,right);
    }
    public void merge(int[] arr,int[] help,int left,int mid,int right){
        int l=left;
        int r=mid+1;
        int index=left;
        //      
        while(l<=mid&&r<=right){
            if(arr[l]<arr[r]){
                help[index++]=arr[l++];
            }else{
                help[index++]=arr[r++];
            }
        }
        //     
        if(l<=mid){
            for(int i=l;i<=mid;i++){
                help[index++]=arr[i];
            }
        }
        if(r<=right){
            for(int i=r;i<=right;i++){
                help[index++]=arr[i];
            }
        }
        //                
        for(int j=left;j<=right;j++){
            arr[j]=help[j];
        }
    }
}

5その他の4つの比較ソート
バブル、挿入、選択ソートは時間複雑度N*Nのアルゴリズムに属し、めったに使用されず、ヒルソートは挿入ソートの変形であり、時間複雑度は改善されたが使用シーンも多くない.泡:

class Solution {
    public int[] sortArray(int[] nums) {
        bubbleSort(nums);
        return nums;
    }
   public void bubbleSort(int[] arr){
       if(arr==null){
           return;
       }
       for(int i=0;i<arr.length-1;i++){
           for(int j=0;j<arr.length-1-i;j++){
               if(arr[j]>arr[j+1]){
                   int temp=arr[j];
                   arr[j]=arr[j+1];
                   arr[j+1]=temp;
               }
           }
       }

   }
}

ソートの選択

class Solution {
    public int[] sortArray(int[] nums) {
        selectSort(nums);
        return nums;
    }
    public void selectSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            int min=i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[min]){
                    min=j;
                }
            }
            if(min!=i){
                int temp=arr[min];
                arr[min]=arr[i];
                arr[i]=temp;
            }
        }
    
    }
}

ソートの挿入

class Solution {
    public int[] sortArray(int[] nums) {
        insertSort(nums);
        return nums;
    }
    public void insertSort(int[] arr){
        if(arr==null){
            return;
        }
        int i=0;
        int j=0;
        for(i=1;i<arr.length;i++){
            int temp=arr[i];
            for(j=i;j>0&&arr[j-1]>temp;j--){
                arr[j]=arr[j-1];
            }
            arr[j]=temp;
        }
    }
}

ヒルソート

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

6非比較ソート
カウントソート

            ，                
          
                  
                

import java.util.Arrays;

/**
 *     2
 *                     ，            
 *                     ，            
 * 

 *          ：
 *                 （  ）         ，
 *                       
 *
 *      
 *     ，   for        O(k),    O(n),    O(k),    O(n)，     O(k+n),   n==k   ，      O(n)。
 *            ，        ，          ，                ，                 。
 *     O(k)>=O(nlogn)   ，           。
 */
public class _05CountSortExample {
    public static void main(String[] args) {
        int[] arr = {2, 5, 3, 0, 2, 3, 0, 3};
        int[] arr2 = jspx(arr);
        System.out.println(Arrays.toString(arr2));
    }

    public static int[] jspx(int[] A) {
        // ：         ，         ：                      
        int max = A[0], min = A[0];
        for (int i : A) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }

        // ：                    
        //  5-0+1 = 6
        int[] pxA = new int[max - min + 1];

        // .           :                    B 
        for (int i : A) {
            pxA[i - min] += 1;//      +1
        }

        // .    
        //      ，       ，         ，       
        int[] result = new int[A.length];
        int index = 0;//         

        //                    
        for (int i = 0; i < pxA.length; i++) {
            //       
            for (int j = 0; j < pxA[i]; j++) {//pxA[i]:        
                result[index++] = i + min;//       min    min，         
            }
        }
        return result;
    }
}

カウントソートの応用:一般的にmax-minは小さくて、データ量はまた大きくてカウントソートを試して大学入試の順位を求めることができます(テンセントの面接問題)
ベースソート