集計ソート(C+)--速度と空間の有機的な結合

集計ソート

集計ソート(C++)--速度と空間有機結合

集計ソート--上から下へ

集計ソート--下から

挿入ソートと集計ソート性能PK試合

集計ソート(C+)-速度と空間の有機的な結合
このアルゴリズムを速度と空間の有機的な結合と呼ぶのは、このアルゴリズムがO(nlogn)時間賦値度の効率を達成するとともに、外部の空間を借りてソートできるためである.データ比較の際だけホストにデータを格納して行う必要があり、他の場合はデータを外部記憶に格納することができるためである.もちろんこの場合、多くのデータの読み取りと書き込みが多くなり、効率に大きな影響を与えるが、能力はまだある.したがって、O(nlogn)アルゴリズムの効率を最大限に発揮するには、内部の記憶空間を使用するか、最適化する必要がある.アルゴリズムはトップダウンとボトムアップの2種類に分けられる~~
  集計ソートがO(nlogn)に達することができるのは、主にデータ構造における二分法を用いて、膨大なデータを2つのセグメントに分割し、2つのデータしかないまで分割し続け、比較を終え、2つのデータと他の2つのデータを比較し、比較を終え、4つのデータと他の4つのデータを比較し、すべてのデータが統合されるまで、すべてのデータが他のデータと比較されるO(n 2)方法と比較すると、時間効率が大幅に向上し、もちろんデータ量が膨大な場合である.
並べ替え→上から下へ
  自顶向下用的就是递归,将大数组递归拆分两段到两个比较,因为递归的特性,思路和代码体现就是从大到小地进行递归,所以是自顶向下;
  実装では3つの方法に関し,3つ目の方法mergeSortTopDownから上を見ると,2つ目の方法を区別することに注意する_mergeSortTopDown;

//     
template 
void __merge(T arr[], T arrTemp[], int L, int Mid, int RightEnd) {
    int i = L;
    int j = Mid+1;
    // k              
    int k = L;
    //                 
    while(i<=Mid && j<=RightEnd) {
        //    L Mid，   Mid+1 RightEnd
        // ++    ，    ，  k、i 1
        if(arr[i]
// L         ，RightEnd    
void __mergeSortTopDown(T arr[], T arrTemp[], int L, int RightEnd) {
    //           ，           ，     ，          (L=RightEnd)     
    if (L < RightEnd) {
	    int Mid = (L + RightEnd) / 2;
	    //           
	    __mergeSortTopDown(arr,arrTemp,L,Mid);
	    __mergeSortTopDown(arr,arrTemp,Mid+1,RightEnd);
	    __merge(arr,arrTemp,L,Mid,RightEnd);
    }
}

//     ，    ，          
//              ，       
template 
// mergeSortTopDown      ，__mergeSort       
void mergeSortTopDown(T arr[], int n) {
    int L = 0;
    int RightEnd = n-1;
    // arrTemp                 ，                         ，
    //                ，                ，        
    T* arrTemp = new T[n];

    __mergeSortTopDown(arr,arrTemp,L,RightEnd);

    delete[] arrTemp;
}

上位から下位への並べ替えの最適化:

データ量が20個以下の場合は挿入ソート:すべてのアルゴリズムはO(n 2)でもO(nlogn)でも前に定数(例えばO(Anlongn)、Aは定数)があるが、nが大きい場合はこの係数は無視され、このnが小さい場合、この係数は影響を及ぼし、集計ソート前の定数は大きく、したがって、複雑なアルゴリズムで大部分のデータを並べた後、挿入ソート(特にnが小さい場合、シーケンスが基本的に秩序化される可能性も大きい)に変更してソートする.

集計を行う場合、左と右の2つの部分はすでに秩序化されているので、左の部分の右境界データが右の部分の左境界データより小さい場合、集計操作を行う必要はないので、if文を加えて判断することができ、基本秩序化シーケンスに対して効率を大幅に向上させることができる.しかし、ランダムシーケンスでは、ifが毎回無駄なことをしている場合、if文による時間の消費は効率を低下させる可能性があります.

インタフェースメソッドとマージメソッドは変更されず、上のものを多重化する.

//              
template 
// L         ，RightEnd    
void __mergeSortTopDown(T arr[], T arrTemp[], int L, int RightEnd) {
    //    ：            20       
    if(RightEnd-L<=20) {
        insertSortTool(arr,L,RightEnd);
        return;
    }
    //           ，           ，     ，          (L=RightEnd)     
    //if (L < RightEnd) {
    int Mid = (L + RightEnd) / 2;
    __mergeSortTopDown(arr,arrTemp,L,Mid);
    __mergeSortTopDown(arr,arrTemp,Mid+1,RightEnd);
    //    ：    
    //                ，                          
    //                     ，  if        
    if(arr[Mid] > arr[Mid+1])
        __merge(arr,arrTemp,L,Mid,RightEnd);
    //}
}

並べ替え→下から上へ
  自底向上用的时回溯,回溯在内存使用上要比递归少,因为递归中每一次递归使用自己的方法都要占据内存;ここで遡及はfor文のネスト使用を用いた.上から下へ反対に、1つのデータのグループから、つまり最初は2つのデータを比較し、それから2を乗じて、このようにします.下から上へ統合インタフェースを必要とせず、直接呼び出せばよい.また、マージの方法は上記と同様に、繰り返しリストされない

//     ，      
template 
void mergeSortBottomUp(T arr[], int n) {
    T* arrTemp = new T[n];
	//  1       
    for(int i=1;i

下から上への並べ替えの最適化の実現:最適化の構想は上から下へと同じで、データ量が小さい場合はまず挿入で並べ替えてから、境界は先に比較してから並べ替えるかどうかを決定します

//     ，      
//                    
template 
void mergeSortBottomUp(T arr[], int n) {
    T* arrTemp = new T[n];
    //    ：      20       ，  20        ，           
    for(int i=0;iarr[j+i])
                __merge(arr,arrTemp,j,j+i-1,min(j+2*i-1,n-1));

    delete[] arrTemp;
}

挿入ソートと集計ソート性能PK試合
試合のルール:

は100万個のデータを並べ替えた.

分乱数シーケンスと基本秩序シーケンスの2試合.

基本秩序シーケンスの非秩序データ数は200個である.

すべてのソート法が最適化されています.

は、上から下へ挿入ソート、上から下へ集計ソート、下から上へ集計ソートである.

     ：
insertSort:530.557
mergeSortTopDown:0.135
mergeSortBottomUp:0.138
      ：
insertSort:0.007
mergeSortTopDown:0.005
mergeSortBottomUp:0.004

試合結果:

は、ランダムな100万個のデータに直面した場合、O(logn 2)の挿入ソートとO(nlongn)の集計ソートは1つのlevel上にないことは間違いない.しかし、基本的な秩序シーケンスに直面すると、挿入ソートは都市に戻ったと言える.また、集計ソートはデータ量が低い場合に挿入ソートを用いるため、挿入ソートはランダムな大量のデータに直面した場合に主ソート方法としては使用できないが、補助は鉄棒である.

最適化後のトップダウンとボトムアップアップの時間差は多くなく、あまり差はありません.しかし、トップダウンは再帰的なため、メモリの消費量が大きい.