ソートアルゴリズムちゃんぽんの山ソート

ソートアルゴリズムちゃんぽんメイン記事転送ゲート
ヒープのソート

#include 
#include 
/*
     
     :o(nlgn)
     :o(nlgn)
  :o(n)
   :o(lgn)
   
*/
using namespace std;

void swap(int &a,int &b){int c = a;a = b;b = c;}

int Max(const vector<int> &a,int n,int i){
    if(2*i + 2 > n) return i;//         
    if(2*i + 3 > n) {
        //         
        if(a[i] >= a[2*i + 1]) return i;
        else return 2*i + 1;
    }
    if(a[i] >= a[2*i + 1] && a[i] >= a[2*i + 2]) return i;
    if(a[2*i + 1] >= a[i] && a[2*i + 1] >= a[2*i + 2]) return 2*i + 1;
    return 2*i + 2;
}

void heapify(vector<int>&a,int n,int i)//lgn,    
{
    //   
    //n     
    //i     
    int cur = i;
    while(true){
        int tmp = Max(a,n,cur);
        if(tmp == cur) break;
        swap(a[cur],a[tmp]);
        cur = tmp;
    }
}

//    
void buildHeap(vector<int> &a) //n
{
    for(int i = a.size()/2 - 1;i >= 0;i --){
        heapify(a,a.size(),i);
    }
}

//     
void heapSort(vector<int> &a)
{
    buildHeap(a);
    for(auto c : a) cout << c << " ";
    cout << endl;
    for(int i = a.size() - 1;i > 0;i --){
        swap(a[i],a[0]);
        heapify(a,i,0);
        for(auto c : a) cout << c << " ";
        cout << endl;
    }
}

int main()
{
    vector<int> a = {4,1,3,2,16,9,10,14,8,7};
    heapSort(a);
    for(auto c : a) cout << c << " ";
    return 0;
}

基本概念
最大ヒープ:任意のノードのキー値が子供のノードのキー値よりも常に大きい

最小ヒープ:任意のノードに対するキー値は、子供ノードのキー値よりも常に小さい.

思考エンジンスタックソートは、その名の通り、このようなデータ構造を利用してソートの目的を達成する.ここでは主に3つの主要な操作を運用しています:スタックを建てて、スタックを維持して、スタックの順序付け.
質問説明:シーケンスA[1..n]A[1.n]A[1.n]A[1..n]を非降順にソートします.

ヒープ構築:元のシーケンスを最大(小)ヒープに生成するプロセス.ノードn 2ノードfrac{n}{2}ノード2 nからノード1ノード1ノード1まで、そのノードをルートノードとするサブツリーの最大(小)ヒープ特性を順次維持する.メンテナンスヒープ:ルートノードのみがヒープの性質を破壊したため、調整案は以下の通りです.

サブツリーのルートノードを先頭ノード、ノードC u rノードCurノードCur

とする.

(最大スタックを例に)ノードC u rノードCurが子供のノードより小さい場合、子供のノードと交換し、ノードC u rノードCurをこの子供で更新する.

は、ノードC u rノードCurノードCurが子供のノードよりも大きいまで2 2 2 2を繰り返し、このとき形成されるスタックが最大スタックとなる.

ヒープのソート:1.元のシーケンスA[1..n]A[1.n]A[1.n]A[1.n]を最大スタックにします.2.A[1]A[1]A[1]とA[n]A[n]A[n]の元素を交換すると、A[n]A[n]A[n]はシーケンスの最大値を保存し、A[1.n−1]A[1.n−1]A[1.n−1]A[1.n−1]はA[1]A[1]A[1]のみが最大スタック特性を満たさないスタックとなり、スタックA[1.n−1]A[1.n−1]A[1.n[1]A[1.n−1]をスタックメンテナンスする.3.A[1]A[1]A[1]A[1]とA[n−1]A[n−1]A[n−1]…A[2]A[2]を順次交換し、A[1.n]A[1.n]A[1.n]A[1.n]A[1.n]A[1.n]を全てソートするように2 2 2 2 2 2 2 2を繰り返し操作する.
なお、メンテナンスの過程において、ノードiノードiをルートノードとするサブスタックのうち、ノードiノードiノードiのみが最大(小)スタック特性を満たさないことが分かった.

時間複雑度スタック並べ替えの時間複雑度は非常に興味深い問題であり、中のいくつかの数学的背景は後で一つ一つ指摘し、関連する証明を与える.全体の構想はアルゴリズム導論第3版の相応の内容に由来する.

メンテナンススタック:ここでメンテナンススタックの時間的複雑さはサブツリーの高さに関係することが容易に観察できる(サブツリールートノードが子供のノードと置換する場合、サブツリーの高さを置換することができるのは最大でサブツリーの高さを置換することしかできないので、推定時間的複雑度o(l o g n)o(logn)o(logn)、下面は数学的証明:T(n)≦T(2 3 n)+o(1)、3層最大ヒープで最後の層が半満の場合のみ等⇒T(n)=o(l o g n)T(n)leq T(frac{2}{3}n)+o(1)\かつ3層最大ヒープで最後の層が半満の場合のみ等\Rightarrow T(n)=o(logn)≦T(32 n)+o(1)3層の最大スタックで最後の層が半分になったときだけ待つ⇒T(n)=o(logn)こちらではなぜ2 3 nfrac{2}{3}n 32 nが他ではないのかを指摘するが,ここではまず最後の層が半分になったと仮定すると,最後の層(h h層と記す)のノード個数が1 3 nfrac{1}{3}n 31 nとなり,では,ルートノードの左サブツリーのノード総数は2 3 nfrac{2}{3}n 32 nであり,スタックのメンテナンス中にルートノードの左サブツリー(2 3 nfrac{2}{3}n 32 n個のノード)または右サブツリー(1 3 nfrac{1}{3}n 31 n個のノード)のみが動作することになり,上記不等式が成立することは明らかである.

スタックを構築するこの時間の複雑さはピットであり,コード自体から直接観察すると,A[1..i..1 n]A[1..i...frac{1}{2}n]A[1..i.21 n]ノードごとにo(l o g n)o(logn)o(logn)程度の複雑さが必要であり,これによりo(n l o g n)o(nlogn)o(nlogn)o(nlogn)がパンパンと顔を打つ.スタックの全高さをH=l o g nとするとT(n)=Σ h = 1 H l o g ( 2 H − h + 1 − 1 ) 2 h − 1 ≈ Σ h=1 H l o g(2 H−h+1)2 h−1であり、ここでl o g(2 H−h+1−1)は高さhのノードの所要時間複雑度を表し、2 h−1はh層ノード総数⇒T(n)=Σ h=1 H[(H+1)2 h−1−h 2 h−1]=(H+1)(2 H−1)−(H−1)2 H+1=2 H+1−H=n−l o g n=o(n)スタックの全高さをH=lognとすると\T(n)=Sigma_{h=1}^Hlog(2^{H-h+1}-1)2^{h-1}\approx\Sigma_{h=1}^Hlog(2^{H−h+1})2^{h−1},\ここでlog(2^{H−h+1}−1)は高さhのノードの所要時間複雑度を表し,2^{h−1}はh層ノードの総個数\Rightarrow T(n)=Sigma_を表す{h=1}^H[(H+1)2^{h−1}−h 2^{h−1}]quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad\quad\quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquad=o(n)quadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadquadスタックの総高さをH=lognとするとT(n)=Σh=1H​log(2H−h+1−1)2h−1≈Σh=1 H log(2 H−h+1)2 h−1であり、log(2 H−h+1−1)は高さhのノードの所要時間複雑度を表し、2 h−1はh層ノード総数⇒T(n)=Σh=1 H[(H+1)2 h−1−h 2 h−1]=(H+1)(2 H−1)−(H−1)2 H+1=2 H+1−H=n−logn=o(n)ここでの証法とアルゴリズム導論は若干異なっているが,方法は問題なく,興味のあるペンフレンドは検証できる.しかし、なぜo(n l o g n)o(nlogn)o(nlogn)に達しなかったのでしょうか.式の結果から,ほとんどのノードはo(l o g n)o(logn)o(logn)の複雑さに達しず,ここで縮水をもたらす.ではなぜl o g n logn lognが少なくなったのか、ここではl i m n→∞l o g n n/2 l o g(n/2)だと推測します!lim_{n\rightarrow\infin }\frac{logn^{n/2}}{log(n/2)!} limn→∞​log(n/2)!lognn/2限界による.

スタックのソートこの中には何の露もなく、直接外層o(n)o(n)o(n)、内層o(l o g n)o(logn)o(logn)o(logn)が発生しなかった理由については、詳細な証明はしていませんが、個人的な推定では、スタックはn/2 n/2 n/2 n/2から始まり、スタックはn n nから始まり、上記のl o g n logn lognはこれ以上消去できないため、証明と積み上げ証明は同じだ.

スタックのソートはデータ分布によって速い列のように劣化することはなく、優れたアルゴリズムであり、不安定であるが、人は元の場所であり、なぜ速い列に取って代わらないのかを考える中で、後埋め坑(なんとなく多くの穴を掘ったような気がする)

を考慮する

空間複雑度スタック並べ替えは、追加の空間

を必要としない、アドレス性並べ替えに属する.

安定性は、高速ソートおよび簡単な選択ソートと同様に不安定である.

ソートアルゴリズムちゃんぽんメイン記事転送ゲート