lyd読書ノート0 x 05ソート(上)

長いですね.複雑ですね.の
ソートアルゴリズム
第1クラスO(n 2)O(n 2)アルゴリズム:選択、挿入、発泡第2クラスO(nlogn)O(nl o g n)アルゴリズム:スタック、集計、高速排出第3クラス玄学アルゴリズム:カウント、基数、バケツ列ですが、私はよく勉強したことがありません.だからまず一番基礎的なところから始めます.

選択ソート:シーケンスから最小を選択するたびに一番前に配置し、繰り返し実行します.

挿入ソート:前のk個がソートされていると仮定すると、新しい数を見つけることができます.二分法によるルックアップがO(n 2)O(n 2)のままである場合,ルックアップ後の移動配列はO(n)O(n)であるからである.

ヒルソート:ソートの変種を挿入します.ヒルソートの実行プロセスは、1つのシーケンスについて、まずk個離れた数のセットを選択する.例えば、n=10、k=5 n=10、k=5を選択すると、[1,6],[2,7],[3,8],[4,9],[5,10][1,6],[2,7],[3,8],[4,9],[5,10]の数を選択し、各要素のセットをそれぞれ挿入ソートし、マージする.次に、k=2 k=2を選択し、[1,3,5,7,9][1,3,5,7,9]および[2,4,6,8,10][2,4,6,8,10]を挿入ソートしてマージします.このように,最終k=1 k=1の場合,挿入ソート作業量は大幅に減少する.kを増分と呼び,kがこのように倍増すればその複雑さは依然としてO(n 2)O(n 2)である.実際,増分の選択はヒルソートの複雑さに重要な影響を及ぼす.1つの一般的な選択はHibbard増分,an＝2 n−1 a n＝2 n−1であり,その時間的複雑さはO(nn−−−−√)O(n)である.

バブルソート:配列にアクセスし、反対の要素に遭遇すると交換できる人がいないまで交換します.

カウントソート:値ドメイン内のソート、1つの配列を開いて値の数を維持し、配列をスキャンすればよい.複雑度O(n+m)O(n+m)O(n+m)で、mは値ドメインである.

基数ソート:hashテーブルを作成するのと同様です.私たちは1つの位置を基準にバケツに入れて、それからバケツごとに取り出した元素を10桁単位でバケツに入れます.のこのように再帰すればよい.二つに分けられます.一つはMSDで、もう一つはLSDです.LSDの複雑さはO(d(n＋r))O(d(n＋r)),dはビット数,rは基数である.

バケツソート:値ドメインをmと仮定し、kバケツにデータを分散し、バケツをソートします.ソートの複雑さを挿入する場合は、Θ(n+n2k) Θ (n+n 2 k)データが均一でランダムに分布することを前提とする.k=nk=nの複雑度がO(n)O(n)である場合,k増大はアルゴリズム効率を著しく変化させ,k=nk=nのときカウントソートに劣化させる.実際、いくつかのまとめを行うと、カウントソートはバケツソートがkを選択する場合であり、バケツ内のデータがバケツソートプロセスを再帰的に呼び出すと、このソートはベースソートであることがわかります.

二叉並べ替えツリー並べ替え:二叉並べ替えツリーに挿入すればよい.平均O(nlogn)O(nl o g n)はO(n 2)O(n 2)に劣化する可能性がある.罪羊の木やtreapなどのバランス木の代わりにO(nlogn)O(nl o g n)に安定させることもできますが、時間のオーバーヘッドが増加します.

スタックソート:スタックに追加し、要素を削除し続け、スタックの性質、複雑度O(nlogn)O(n l o g n)を維持します.推奨:https://www.cnblogs.com/chenweichu/articles/5710567.html http://www.cnblogs.com/chenweichu/articles/5710635.html

分治ソート:個人的に最も優雅なソートアルゴリズムは、一つもないと思います.数列を分割し、サブ数列をソートし、最後にマージします.複雑度O(nlogn)O(nl o g n)は,参照後の逆シーケンス対を実現する.

クイックソート:数を選択し、それより大きいものを前面に配置します.そうでない場合は、このプロセスを再帰的に処理します.選択した数はランダムにできます.

りさんか
ここには不思議なブラックテクノロジーがあります.の

for(int i = 1; i <= n; ++i) b[i]=a[i];
sort(b+1,b+n+1);
int un=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+un+1,a[i])-b;

cf 670 Cは怠け者なのでmapを開いて、map離散化ででたらめをすればいいことに気づいた.

#include 
#include 
#include 
using namespace std;

#define N 200003

int n, t, cnt;
int aud[N];
int ansy, anss, arr;
struct node {
    int voice, sub; 
}movie[N];
map<int, int> m;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; ++i) cin>>aud[i];
    cin>>t;
    for(int i = 1; i <= t; ++i) cin>>movie[i].voice;
    for(int i = 1; i <= t; ++i) cin>>movie[i].sub;
    for(int i = 1; i <= n; ++i) 
        if(!m.count(aud[i]))
            m.insert(make_pair(aud[i], 1));
        else ++m[aud[i]];
    for(int i = 1; i <= t; ++i) {
        if(!m.count(movie[i].voice)) { 
            if(ansy == 0) 
                ansy = 0, 
                anss = (m.count(movie[i].sub) ? m[movie[i].sub] : 0), arr = i;
            }
        else {
            if(m[movie[i].voice] > ansy) 
                ansy = m[movie[i].voice], 
                anss = (m.count(movie[i].sub) ? m[movie[i].sub] : 0), 
                arr = i;
            if(m[movie[i].voice] == ansy && m.count(movie[i].sub) && m[movie[i].sub] > anss) 
                anss = m[movie[i].sub], arr = i;             
        } 
    }
    cout<

とてもsabiではありませんか.の24秒かかります.のそして階下の大物を見てみると、upperを使えばboundマイナスlower_boundで値が出るなるほど
参考資料
https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin https://www.cnblogs.com/chengxiao/p/6104371.html http://blog.csdn.net/foliciatarier/article/details/53891144 https://www.cnblogs.com/dwj411024/p/5978821.html http://blog.csdn.net/cauchyweierstrass/article/details/49919559 https://www.cnblogs.com/jingmoxukong/p/4311237.html