C++におけるsort()およびqsort()(不完全紹介)

5066 ワード

普段アルゴリズム問題とojをブラシするとき、ソートアルゴリズムは最もよく使われるアルゴリズムの一つである.また,各アルゴリズムブックのディレクトリにおいても,通常,各ソートアルゴリズムを先頭に置くことが重要であることが分かる.多くの人がアルゴリズムの本の中で泡を出して、急速にソートする方法を学んだことがあるかもしれませんが、その原理も大体知っています.実際に適用すると、泡のソートが最も簡単で、もちろん複雑度も最高です.....(ガウドナーが言ったように、「バブルソートは魅力的な名前といくつかの面白い理論問題を招いたという事実以外に、推薦に値するものはないようだ」).理想的には最も効率的(nlogn)と言えるでしょう.しかし、急速なソートは泡のソートのように理解と記憶がよくなく、毎回自分で思い出してテンプレートコードを叩く必要があります...考えてみれば面倒なことだ.しかし、C++には速い列の関数があります.考えてみれば素晴らしいことだ.
現在、sort()とqsort()のいくつかの使い方を紹介していますが、完全ではなく、試合でよく使われる内容を羅列しているだけです.
sort関数:実はsort()は高速ソートとは呼ばれず、スマートソートと呼ぶべきである.通常は、速列を使用しますが、速列が悪化すると、自動的に他のソートに調整されて補助されます.最も効率的なソートです.C++のalgorithmライブラリにあります.
sort(begin,end); 
/* [begin, end]              
sort()        ,        ,                */

eg.  :
int _main()
{
    int a[20],i;
    for(i=0;i<20;i++)
         cin>>a[i];
    sort(a,a+20);  //     
    for(i=0;i<20;i++)
    cout<<a[i]<<endl;
    return 0;
}

ここのソートは昇順ですが、降順する場合はどうすればいいですか?次に、比較関数を作成して実装するコードを示します.
int cmp(int a,int b)
{
      return a<b;   //    ;  return a>b,    
 
}
 
int main()
{
     int a[20],i;
     for(i=0;i<20;i++)
       cin>>a[i];
     sort(a,a+20,cmp);
     for(i=0;i<20;i++)
       cout<<a[i]<<endl;
     return 0;
}

実はただ整型と実型の配列に対する昇順、降順のソートを実現するために、もっと簡単な方法があって、自分で関数を編む必要はありません.標準ライブラリには既成のものがあるので、テンプレートに基づく比較関数の対象を提供して、直接使うことができます.ここで使うのはgreaterとless.
  • 昇順:sort(begin,end,less();
  • 降順:sort(begin,end,greater();
  • int main()
    {
          int a[20],i;
          for(i=0;i<20;i++)
              cin>>a[i];
          sort(a,a+20,greater<int>());//      ,   less<int>()
          for(i=0;i<20;i++)
              cout<<a[i]<<endl;
          return 0;
    }
    

    次はqsort()です.
    qsort(quicksort)は、あなたが与えた比較関数に基づいて配列を迅速にソートし、ポインタ移動によってソート機能を実現します.ソート後の結果は元の配列に残ります.
    qsortとcompareの使い方は以下の通りです.
    void qsort( void *base, size_len, size_data, int compare);
    
    int compare (const void *elem1, const void *elem2 ) ;

    compare関数:
    1 int compare(const void *a , const void *b )
    2 
    3 {
    4   return *(int *)a - *(int *)b;  //    
    5 
    6 //return *(int *)b - *(int *)a; //    
    7 
    8 }

    上はInt型のソートで、文字型ならintをcharに変更します.double型は次のとおりです.
    1 int cmp(const void*a,const void*b)
    2 {
    3     return *(double*)a>*(double*)b?1:-1;//  
    4 
    5   //return *(double*)b>*(double*)a?1:-1;   
    6 }