ああ!アルゴリズム読書ノート|第1章ソート

序論:感覚アルゴリズム導論この本は今のところ私のような菜鳥にはあまり向いていない.そこでネット上で《ああ!アルゴリズム》のこの本を理解することを始めて、この本は确かにとても简単で、私の大きい2学の《データの构造とアルゴリズムの分析》よりずっと简単で、この授业は私は80余り点数を试験しました.知識は温故知新で、この本は分かりやすいですが、細かい時間で読んで、教材を温める時間があるつもりです.アルゴリズムの聖典である「アルゴリズム導論」については、もうちょっと待つ必要があります.一つは難しいからです.二つ目は厚いので、今のところそんなに時間がありません.
この本はCで书いたので、まずCを勉强することをお勧めします.C言语についてもノートを书いています.基本的に基本的な文法を読んでから、私のノートと基础的なCアルゴリズムの例題を消化すれば、Cに入ることができます.
私が使っているコンパイラはXcodeですが、この本の著者は、正直に言うといくつかのコードが友好的ではありません.例えば、多くのユーザーが提示していないので、実行効果もあまり考えていないので、原書のコードに対して個人的な最適化を行います.
また、ブログを書くのは確かに時間の無駄ですね.一年生の学生に向いています.私はできるだけこの本のノートを完成しましょう.
第1章ソート
第1バケツのソート
11個のバケツがあれば、0~10番です.ここではn個の0~10の間の整数があり、数字0は番号0のバケツに、数字1は番号1のバケツに、順番にこれでいいので、最後にバケツごとの数字の個数を統計します.
例:n個の0~1000の整数を入力し、それらを小さいものから大きいものに並べ替える.

#include
int main()
{
    int book[1001],i,j,t,n;
    for(i=0;i<=1000;i++)
        book[i]=0;
    scanf("%d",&n);   //     n，      n  
    printf("   %d 0~1000     
",n);
    for(i=1;i<=n;i++) //    n  ，      
    {
        scanf("%d",&t); //         t 
        book[t]++;       //    ，    t         （   +1）
    }
    for(i=1000;i>=0;i--)  //      1000~0  
        for(j=1;j<=book[i];j++)  //              
            printf("%5d",i);
    printf("
");
    return 0;
}

アルゴリズム時間複雑度はO(2＊(M＋N),すなわちO(M＋N)である.
第2節発泡ソート
バブルソートの基本思想:隣接する2つの要素を比較するたびに、順序が間違っている場合は交換します.小さいほど後ろに寄る.

#include
int main()
{
    int a[100],i,j,t,n;
    printf("             ：");
    scanf("%d
",&n);      //     n,      n  
    for(i=1;i<=n;i++)     //    n     a 
        scanf("%d",&a[i]);
    //         
    for(i=1;i<=n-1;i++)   //n    ，   n-1   
    {
        for(j=1;j<=n-i;j++)
        {
            if(a[j]

バブルソートアルゴリズムの核心は二重ネストサイクルである.時間的複雑度はO(N^2)である.
第3節高速アルゴリズム

#include
int a[101],n;

void quicksort(int left,int right)
{
    int i,j,t,temp;
    if(left>right)
        return;
    
    temp=a[left];
    i=left;
    j=right;
    while(i!=j)
    {
        while(a[j]>=temp && i

高速ソートの最悪時間複雑度はO(N^2)であり,平均複雑度はO(Nlogn)であった.
第四節小ふんは本を買う
シナリオに相当してn個の整数(1~1000)を入力して出力を並べ替え、重複する数字をフィルタリングする必要がある.
方法1:まず重くして、それから小さい順に出力します.アルゴリズム思想はバケツソートに用いられた.

#include
int main()
{
    int a[1001],n,i,t;
    for(i=1;i<=1000;i++)
        a[i]=0;
    
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&t);
        a[t]=1;
    }
    for(i=1;i

方法2:小さいものから大きいものに並べ替えて、出力するときにやり直します.アルゴリズム思想はバブルソートを用いた.

#include
int main()
{
    int a[101],n,i,j,t;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    //      
    for(i=1;i<=n-1;i++)
    {
        for(j=1;j<=n-j;i++)
        {
            if(a[j]>a[j+1])
            { t=a[j];a[j]=a[j+1];a[j+1]=t; }
        }
    }
    //  
    printf("%d ",a[1]);
    for(i=2;i<=n;i++)
    {
        if(a[i]!=a[i-1])
            printf("%d ",a[i]);
    }
    return 0;
}

心得:この章のアルゴリズムはとても简単で、教材の中で私が学んだソートアルゴリズムは少なくとも7、8种类あるでしょう.これらのアルゴリズムを理解するのは难しくありません.各アルゴリズムを熟練して把握し,実際の問題解決に応用することが難点であり,実際の情景を分析して最適なアルゴリズムを選択する.