ソートとその拡張子の挿入

キャンパスの时間は多くなくて、仕事を探すつもりで、多くのものを見て知識を増やして、自分のために助けます!がんばって!
ソートの挿入:単純なソート方法
基本的な操作:新しいレコードを並べ替えられた秩序配列に挿入します.
時間の複雑さに影響する要因:レコード間の比較と移動
元の挿入ソートアルゴリズム:時間複雑度O(n 2)

 1 //      
 2 public void simpleSort(int[] array){
 3         for(int i=1; i<array.length; i++){
 4             int temp = array[i];
 5             if(array[i]<array[i-1]){
 6                 array[i]=array[i-1];
 7                 int j=i-2;
 8                 for(; j>=0&&temp<array[j]; j--){
 9                     array[j+1]=array[j];
10                 }
11                 array[j+1]=temp;
12             }
13             
14         }
15     }

折りたたみ挿入ソート:折りたたみ検索を使用して、ソートされた配列の中で、新しいレコードが挿入すべき位置を見つけます.改善効果:記録前の比較回数は減少しましたが、移動回数は変わらないため、時間の複雑さは変わりません.

    /*
     *       
     *   ：      
     *      ：O(n^2) [       ]
     */
    public void binaryInsertSort(int[] array){
        for(int i=1; i<array.length; i++){
            int temp = array[i];
            //              
            int low = 0;
            int high = i - 1;
            while(low<=high){
                int half = (low+high)/2;
                if(array[i]<array[half]){
                    high = half-1;
                }else{
                    low = half+1;
                }
            }
            
            for(int j=i-1; j>high; j--){
                array[j+1]=array[j];
            }
            array[high+1]=temp;
        }
    }

2ウェイ挿入ソートアルゴリズム:折りたたみ挿入ソートに基づいてさらに改良され、元の配列サイズの配列を補助空間として使用し、記録の移動回数を減らすことを目的としています.注意:選択した最初の要素が配列内の最大または最小の要素である場合、このソート方法は劣化します.

 1     /*
 2      *       
 3      *   ：        
 4      *     ：  n     
 5      */
 6     public int[] tInsertSort(int[] array){
 7         int[] cArray= new int[array.length];
 8         int start=0,end=array.length-1;
 9         int temp = array[0];
10         
11         for(int i=1; i<array.length; i++){
12             if(array[i]<=temp){
13                 if(cArray[start]==0){
14                     cArray[start]=array[i];
15                 }else{
16                     int j=start;
17                     for(; j>=0&&array[i]<cArray[j]; j--){
18                         cArray[j+1]=cArray[j];
19                     }
20                     cArray[j+1]=array[i];
21                     start++;
22                 }
23                 
24             }else{
25                 if(cArray[end]==0){
26                     cArray[end]=array[i];
27                 }else{
28                     int k=end;
29                     for(;k<cArray.length&&array[i]>cArray[k];k++){
30                         cArray[k-1]=cArray[k];
31                     }
32                     cArray[k-1]=array[i];
33                     end--;
34                 }    
35             }
36         }
37         cArray[++start]=temp;
38         
39         return cArray;
40     }

表挿入ソート方法:レコードの移動を減らしますが、時間の複雑さは変わりません.

 1     /*
 2      *      
 3      *   ：         
 4      */
 5     public void tableInsertSort(DataItem[] array){
 6         for(int i=2;i<array.length;i++){
 7             int s=0;
 8             while(array[array[s].getNext()].getVal()<array[i].getVal()){
 9                 s=array[s].getNext();
10             }
11             array[i].setNext(array[s].getNext());
12             array[s].setNext(i);
13         }
14     }

ヒルソート:インクリメンタルソートの縮小とも呼ばれ、時間効率が向上します.増分配列を使用して、配列内の要素を間隔でソートします.
増分配列の選択については、inc[k]=2 t-k+1+1、ここでtがソート回数、1<=k<=t<=log 2(n+1)のとき、ヒルソートの時間的複雑度はO(n 3/2)であるという統一的な定説はない.

 1     /*
 2      *     
 3      *         ，                   
 4      */
 5     public void shellSort(int array[],int[] incArray){
 6         for(int i=0; i<incArray.length; i++){
 7             incrementSort(array,incArray[i]);
 8         }
 9     }
10     
11     public void incrementSort(int[] array, int inc){
12         //     i++  ，      ，              
13         //5-0 6-1 7-2 8-3 9-4 10-5
14         
15         for(int i=inc; i<array.length; i++){
16             if(array[i]<array[i-inc]){
17                 int temp=array[i];
18                 array[i]=array[i-inc];
19                 int j=i-2*inc;
20                 for(;j>=0&&temp<array[j]; j-=inc){
21                     array[j+inc]=array[j];
22                 }
23                 array[j+inc]=temp;
24             }
25         }
26     }