7つのソート


ソートの選択


最も簡単なアルゴリズム:まず配列の最小の要素と1つの要素の交換位置を見つけて、次に次の要素の中で最小の要素と配列の2番目の要素の交換を見つけて、このように往復します.
特徴:
  • 運転時間は入力に関係なく:N^2/2回の比較が必要
  • データ移動は最小限:N回の交換
  • のみ
  • 不安定、例えば、(2,2,5,4,7,8,1)
  • import java.util.*;
    public class Selection
    {
        public static void main(String[] args){
            int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void sort(int[] arr){
            
            for(int i = 0; i < arr.length;i++){
                int min = i;
                for(int j = i;j

    バブルソート


    左から右へ隣接する逆順序の要素を交換し続け、1ラウンドのループの後、並べ替えられていない最大要素を右側に浮かべることができます.
    1サイクルで交換が発生しない場合は、配列が秩序化されていることを示し、直接終了することができます.
  • 安定な並べ替え,時間複雑度O(N^2)
  • import java.util.*;
    public class Bubble{
        public static void main(String[] args){
            int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
        public void sort(int[] arr){
            int N = arr.length;
            for(int i = N-1;i>=0;i--){
                for(int j = 0;j arr[j+1]){
                        swap(arr,j,j+1);
                    }
                }
            }
        }
        public static void exch(int[] arr,int i,int j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
        }
    }

    ソートの挿入


    ソートされた配列の適切な位置に各数を挿入すると、残りの要素は1ビット右に移動する必要があります.
    特徴:
  • 最悪はN^2/2回の比較とN^2/2回の交換が必要であり、最良の場合はN-1回の比較と0回の交換が必要である.平均してN^2/4回比較してN^2/4回交換する必要がある.
  • 安定
  • import java.util.*;
    public class Insertion
    {
        public static void main(String[] args){
            int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void sort(int[] arr){
            
            for(int i = 0 ; i < arr.length;i++){
                for(int j = i;j>0 && arr[j] < arr[j-1] ;j--){
                    exch(arr,j,j-1);
                }
            }
        }
    
        public static void exch(int[] arr,int i,int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    

    ヒルソート


    アイデア:
  • 配列中の任意の間隔hの要素を秩序化
  • とする.
  • ヒルソート速度を速めるために挿入ソートを改善し、隣接しない要素を交換して配列の局所をソートし、最終的には挿入ソートで局所秩序の配列を
  • ソートした.
  • 不安定
    import java.util.*;
    public class Shell
    {
        public static void main(String[] args){
            int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void sort(int[] arr){
            int h = 1;
            int N = arr.length;
            while( h < N/3)
                h = 3*h + 1;
            while(h >=1){
                for(int i = h; i=h && arr[j] < arr[j-h];j -= h){
                        exch(arr,j,j-h);
                    }
                }
                h = h/3;
            }
        }
    
        public static void exch(int[] arr,int i,int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
  • ヒープのソート


    ≪ヒープ|Heap|oem_src≫:各ノードが2バイト以上のポイント
    スタックソートは、スタックというデータ構造によって設計されたソートアルゴリズムであり、着実に選択されたソートである.
    最良、最悪、平均時間複雑度はO(Nlogn)、
    アイデア:
  • は、並べ替えられるシーケンスを大きなスタックに構成し、このとき、シーケンス全体の最大値がルートノードである.末尾要素と交換し、末尾が最大値になります.その後、残りのN−1の要素をスタックに再構築し、Nの要素の最小値を得る.このように繰り返すと、秩序あるシーケンスが得られます.
  • 不安定
  • import java.util.*;
    public class Heap
    {
        public static void main(String[] args){
            int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
        
        public static void sort(int[] arr){
            
            
            
    
            int N = arr.length - 1;
            //       
            for(int i = (N+1)/2 ;i >= 0 ;i--){
                sink(arr,i,N);
            }
    
            while(N > 0){
                exch(arr,0,N--);
                sink(arr,0,N);
            }
        }
    
    
        //        
        public static void sink(int[] arr,int k,int N){
            while(2 * k <= N){
                int j = 2 * k;
                if(j < N && arr[j] < arr[j+1])   //          ,     j     
                    j++;
                if(arr[k] < arr[j]){    //            ,             
                    exch(arr,k,j);
                    k = j;
                }else{
                    break;
                }
                
            }
        }
    
        public static void exch(int[] arr,int i ,int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
    }

    集計ソート


    集計ソートは、配列を再帰的に2つの半分に分けてソートし、結果を集計します.
    特徴:
  • 時間:O(Nlogn)、
  • 分割後の層数はlognであり、各層のマージはNであるため、時間複雑度はO(Nlogn)である.分割はO(1),
  • と考えられる.
  • 時間複雑度:総演算回数式がn変化の影響を受ける最も大きい項で係数を含まない.したがって(N+1)logN=NlogNとなる.
  • 空間はO(N)であり、1つの補助配列によってデータの記憶
  • を行う必要がある.
  • 安定
  • 2つの秩序化された配列を1つの配列にソートします.2つのi,jの2つのポインタがそれぞれ2つの配列を指し、ポインタが実行する値を比較し、小さな値を新しい配列に割り当てます.同時に、ポインタは自己増加します.
    import java.util.*;
    public class Merge
    {
        public static void main(String[] args){
            int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
            int[] temp = new int[arr.length];
            sort(arr,0,arr.length-1,temp);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void sort(int[] arr,int left,int right,int[] temp){
            
            if(left < right){
                int mid = (left + right) / 2;
                sort(arr,left,mid,temp);
                sort(arr,mid + 1,right,temp);
                merge(arr,left,mid,right,temp);
                
            }    
        }
    
        public static void merge(int[] arr,int left,int mid,int right,int[] temp){
            
            int i = left , j = mid + 1;
    
            for(int k = left;k<=right;k++){
                temp[k] = arr[k];        //   arr[left .. right]   temp[left .. right]
            }
    
            for(int k = left;k <= right;k++){
                if(i > mid)
                    arr[k] = temp[j++];
                else if(j > right)
                    arr[k] = temp[i++];
                else if(temp[i] < temp[j])
                    arr[k] = temp[i++];
                else 
                    arr[k] = temp[j++];
            }
        }
    }

    クイックソート:


    高速ソートは、1つの配列を2つのサブ配列に分割し、2つの部分を独立にソートする分治的ソートアルゴリズムです.
    集計ソートとの違い:
  • 集計ソートは、配列を2つのサブ配列に分けてそれぞれソートし、使用するサブ配列を集計して配列全体をソートすることである.
  • であり、高速ソートは、2つのサブ配列が整列すると、配列全体が整列する
  • である.
    特徴:
  • その場でソート(小さな補助スタックのみ)
  • 時間複雑度O(Nlogn)
  • は、シーケンス(5 3 3 4 3 8 9 10 11)
  • のように不安定である.
    import java.util.*;
    public class Quick
    {
        public static void main(String[] args){
            int[] arr = new int[]{1,6,43,2,3,65,98,54,2,8,0,9};
            sort(arr,0,arr.length-1);
            System.out.println(Arrays.toString(arr));
        }
        
        public static void sort(int[] arr,int left,int right){
            
            merge(arr,left,right);
        }
    
        public static void merge(int[] arr,int left,int right){
            
            if(left < right){
                int i = left , j = right , t = arr[i];   //    (left)     
                while( i < j){
                    while(arr[j] >= t && i < j)    //    ,       t  
                        j--;
                    arr[i] = arr[j];
                    while(arr[i] <= t && i < j){   //    ,       t  
                        i++;
                    }
                    arr[j] = arr[i];    
                }
                //   (  )t     i,  i       t,i       t
                arr[i] = t;
                merge(arr,left,i-1);
                merge(arr,i+1,right);
            }
        }
    }
    

    まとめ


    安定したアルゴリズム:
  • バブルソート、挿入ソート、集計ソート、その他不安定
  • 時間の複雑さ:
  • 発泡、選択、挿入:O(N^2)
  • 高速、ヒープ、集計:O(Nlogn)であり、集計には追加の空間O(N)
  • が必要である
    速い列の基準の3種類の選択
  • 固定位置:第1または最後のいずれかを選択し、この選択方式は秩序化シーケンスに遭遇した場合、効率が低く、O(N^2)
  • である.
  • ランダム位置:基準値として、並べ替えられるシーケンスの任意の数を選択します.
  • 三数取中法:第一の値、最後の値、第N/2の値、すなわち中間数を基準値とし、これは三種類の中で最も効率的である.

  • 高速配列の最適化:
  • 並べ替え配列の長いを一定の大きさに分割する後、挿入並べ替え
  • を試みる.
    最適化の理由:並べ替えられるシーケンスの長さが小さい場合や、基本的に秩序化されている場合、高速配列の効率は挿入が良いか.
  • 三方向分割:多数の重複要素を持つ配列について、配列を分割要素より小さく、等しい、およびより大きい3つの部分に分割できます.3方向分割高速ソートは、いくつかの異なるプライマリ・キーのみのランダム配列に対して、線形時間内にソートを完了することができる.