バブルソート、選択、挿入ソート、二分法検索

21203 ワード

バブルソート
最近新しいソート方法を知って、前にも泡が出てソートして、Cを勉強していたときによく知っていたので、見てみましょう.
/*        ,  int    ,               
    boolean   flag                */

public static void bubbleSort(int [] arr, boolean flag){
        int length = arr.length;
        for(int i=0; i1; i++){
            for(int j=0; j1 - i; j++){ 
     //             ,                
                if(flag){   //        
                    if(arr[j] > arr[j + 1]){
                        swap(arr,j,j+1);//        
                    }
                }else{    //        
                    if(arr[j] < arr[j + 1]){
                        swap(arr,j,j+1);//        
    }}}
    printArray(arr);  //    
    }  
}
public static void printArray(int [] arr){
        int length = arr.length;
        System.out.println();
        for(int i=0; iout.print(arr[i] + " ");
        }
        System.out.println();
    }

mainメソッドで実行する場合
int ff []={2,5,2,4,7,3,1};
bubbleSort(ff,true);

ソートの実行状況は次のとおりです.
//          -------               

      2,5,2,4,7,3,1  //    

2 2 4 5 3 1 7   //           7

2 2 4 3 1 5 7   //       7      5

2 2 3 1 4 5 7   //       7 5      4

2 2 1 3 4 5 7   //      

2 1 2 3 4 5 7   //  .

1 2 2 3 4 5 7   // .

従って,発泡ソートの実行原理と具体的なソート過程が分かる.最大値(最小値)の昇順(降順)を順に探します.
ソートの選択
これは最近見たソート方法で、原理を理解する必要があると思います.
public static void selectSort(int [] arr){
        int length = arr.length;
        for(int i=0;i<length - 1; i++){
            int min = i;
            for(int j=i+1; j<length; j++){
                if(arr[min] > arr[j]){
//       a[min]    arr[j],            arr[j]
                    min = j;
                }
            }
            printArray(arr);
            if(min != i){
                swap(arr,i,min);//    
            }
        }
    }

それともmainメソッドで実行しますか?
int ff []={2,5,2,4,7,3,1};
selectSort(ff);

プロセスの実行:
//        
//         2,5,2,4,7,3,1         

//                   2,        
//2>1(       )        2    1   ,     1,    
1 5 2 4 7 3 2  
//                  1,        
//5>2    5 2   ,     2,    
1 2 5 4 7 3 2 
//                  2,        
//5>2    5 2   ,     2,    
1 2 2 4 7 3 5 
//                  2,        
//4>3    4 3   ,     3,    
1 2 2 3 7 4 5 
//    。。
1 2 2 3 4 7 5 

1 2 2 3 4 5 7 

ソートを選択する過程は上の状況で、原理を見ましたか!
ソートの挿入
挿入ソートがどうなっているかを見てみましょう.
public static void insertSort(int[] arr){
        int i,j;
        int insert;
        for(i=1; i1;
            while(j >= 0 && insert < arr[j]){
                arr[j+1] = arr[j];
                j --;
            }
            arr[j+1] = insert;
            printArray(arr);
        }
    }

同じmainメソッドで実行
int ff []={2,5,2,4,7,3,1};
insertSort(ff);

結果:

2 5 2 4 7 3 1   //      ,       ,
  2<5 true    --    5    
2 2 5 4 7 3 1  //       ,  ,   2<2<5
    4<5 true    --    5    
2 2 4 5 7 3 1 //       ,  ,   2<2<4<5
      7<5 false   --    5    
2 2 4 5 7 3 1 //       ,  ,   2<2<4<5<7
        3<7 true     --    5    
      3<5 true    
    3<4  true    
  2<3 false     
2 2 3 4 5 7 1 //       ,  ,   2<2<3<4<5<7
//  。。
1 2 2 3 4 5 7

同様に配列int ff []={2,5,2,4,7,3,1};を並べ替える
3つの方法で並べ替えられるそれぞれの原理を見てみましょう.
挿入ソート—————選択ソート—————————泡ソート
2 5 2 4 7 3 1 --1 5 2 4 7 3 2 --2 2 4 5 3 1 7 
2 2 5 4 7 3 1 --1 2 5 4 7 3 2 --2 2 4 3 1 5 7 
2 2 4 5 7 3 1 --1 2 2 4 7 3 5 --2 2 3 1 4 5 7
2 2 4 5 7 3 1 --1 2 2 3 7 4 5 --2 2 1 3 4 5 7
2 2 3 4 5 7 1 --1 2 2 3 4 7 5 --2 1 2 3 4 5 7 
1 2 2 3 4 5 7 --1 2 2 3 4 5 7 --1 2 2 3 4 5 7

最近では新しい検索方法も認識されています
にぶんほうたんさく
たとえば
int arr[]={1,4,3,6,9,8,7,0,2,5};

このような数の中で数字が2の下付きの位置を探すには、私たちの方法は
for(int i=0;i<arr.length;i++){
    if(arr[i]==2){
    return i;
    }else{
    return -1;
    }
}

データが十分大きい場合は、数万以上のデータ・クエリー量があります.この方法はもちろん可能ですが、効率的ではありません.このような効率的なデータクエリーの方法です.
//      int x         
public static int erFen( int arr[],int x){
         int min = 0;
           int max = arr.length - 1;
           while (min <= max) {
               int middle = (min + max) / 2;
               if (x < arr[middle]) {
                   max = middle - 1;
               } else if (x > arr[middle]) {
                   min = middle + 1;
               } else {
                   return middle;
               }
           }
           return -1;
       }

二分法クエリーを使用するには、配列が整列していることが前提です.つまり、まず配列をソートしてから、二分法クエリーを使用することができます.
だから
    selectSort(arr);  //               
  //      : 0 1 2 3 4 5 6 7 8 9 

  //       2
  System.out.println(erFen(arr,2));
  //     : 2           arr      2    arr[2]

配列に複数のクエリーの数値が表示された場合、すべてクエリーすることはできません.そのうちの1つの場所しかクエリーできません.