アルゴリズム

title:アルゴリズム開編date:2016-10-14 13:53 tags:アルゴリズムthumbnail:http://img2.imgtn.bdimg.com/it/u=4054526222762120886&fm=21&gp=0.jpg
アルゴリズムの冒頭で紹介されている:Algorithmは、問題を解決するための戦略的メカニズムをシステムの方法で説明することを意味し、問題解決のための正確かつ完全な説明である.
一番速くて簡単な並べ替え
まず問題を見ます
クラスには5人の学生がいます.それぞれ5点、3点、5点、8点、2点を取っています.点数を大きいから小さいまで並べ替えて8、5、5、3、2です.何かいい方法がありますか?プログラムを作成して、コンピュータに5つの点数をランダムに読み込ませてから、この5つの点数を大から小まで出力します.古い道のプログラマーはいろんな泡ができて、リングをします.これはかなり深いです.先を見てください.
私たちは一次元配列を利用してこの問題を解決できます.a[11]の配列を作成します.このように下付きはそれぞれa[0]->a[10]と表示します.それぞれ0点、1点…10点を表します.点数が出るたびに、対応する下付き位置+1で、最後に印刷すれば、私たちの現在の要求に満足できます.

int main(int argc, const char * argv[]) {
  
  int a[11];
  int scannedNumber;
  
  for (int i = 0; i < 11; i ++) {
    a[i] = 0;
  }
  
  for (int j = 0; j < 5; j ++) {
    scanf("%d", &scannedNumber);
    a[scannedNumber] ++;
  }
  
  for (int k = 10; k >= 0; k --) {
    for (int l = 0; l < a[k]; l ++) {
      printf("%d", k);
    }
  }
  
  return 0;
}

この並べ替えアルゴリズムは、樽並べ替えと呼ばれています.各点数は桶のようになっています.出現するたびに、桶の中に何かを追加します.次に、データ範囲が0から100までの任意の数の数字を、大きいから小さいまで並べ替えてみます.

int main(int argc, const char * argv[]) {
  int book[101], scannedNumber;
  int inputCount;
  
  for (int i = 0; i < 101; i ++) {
    book[i] = 0;
  }
  
  printf("Enter numbers you want:");
  scanf("%d", &inputCount);
  
  for (int j = 0; j < inputCount; j ++) {
    scanf("%d", &scannedNumber);
    book[scannedNumber] ++;
  }
  
  for (int k = 100; k >= 0; k --) {
    for (int l = 0; l < book[k]; l ++) {
      printf("%d ", k);
    }
  }
  
  return 0;
}

同様に問題はないです.コードの6行目はM回(Mはバレルの個数)、14行目はN回(入力した数字の個数)、19行はM＋N回循環していますので、時間の複雑度はO(2＊(M＋N))となります.時間の複雑度を言う時は、小さな定数を無視できます.最終的な時間の複雑さは以下の通りです.

O(M+N)

これは非常に速い並べ替えアルゴリズムです.実はこれは本物の樽の並べ替えではありません.樽の並べ替えは実際にはもっと複雑で、これは簡略化版しか計算できません.基本的にはまだ真の意味のアルゴリズムとは言えません.上の処理はその点数を出力した学生の情報に触れると少し問題があります.私たちは点数を出力しただけです.だから第二節を引き出します:泡が立って並べ替えます.
泡の並べ替え
単純化されたバージョンのバケツの並べ替えは、使用範囲の制限だけではなく、スペースの無駄です.並べ替えが必要な範囲が0～21000万円なら、21001の変数を申請します.私たちはこのように多くの桶で数字ごとに出現する回数を保存します.すぐに3つの数字(1、1999、1999999)だけを並べ替えても、2000001個の桶が必要です.もったいないです.まだ止まらないです.浮動小数点型なら?新しいアルゴリズムに接触し、泡を立てて並べ替えます.この2つの問題をうまく解決できます.泡の並べ替えの基本的な考え方は、隣接する2つの要素が、順序が間違っていれば位置を交換することである.もし私たちが

12, 35, 99, 18, 76

これらの数は大きいから小さいまで並べ替えて、小さいほど後ろに寄ってきます.
まず、1位と2位の大きさを比べると、12は35より小さいことが分かりました.だから、交換位置、交換後:

35, 12, 99, 18, 76

そして、上記の方法で引き続き比較して、2位と3位は….

35, 99, 12, 18, 76

続き:3位と4位:

35, 99, 18, 12, 76

続き:4位と5位:

35, 99, 18, 76, 12

4回の比較を経て、一番小さい数字はもう最後の方になりました.一人の方が大きいのは前に行って変えます.バブルのようなので、 といいます.ここに来て、私達はただその中の一つの数字を位置に戻して、上の過程を引き続き繰り返します.第1位と第2位、第2位と第3位、第3位と第4位を比較し続けます.彼はもう最小です.第二の比較後:

99, 35, 76, 18, 12

次の何回もこのようにして、いくつかの数字があって、比較の回数はn-1回です.泡の原則は、比較するたびに1つの配列だけを位置合わせします.次にコードの実現:

int main(int argc, const char * argv[]) {
  int a[20], scannedNumber, input;
  
  scanf("%d", &input);
  
  for (int i = 1; i <= input; i ++) {
    scanf("%d", &scannedNumber);
    a[i] = scannedNumber;
  }
  
  //   INPUT   ，      INPUT-1   
  for (int i = 1; i <= input - 1; i ++) {
    
    // INPUT-I    ，        ，        
    for (int j = 1; j <= input - i ; j ++) {
      
      //   
      if ( a[j] < a[j + 1] ) {
        int temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
      }
    }
  }
  
  for (int i = 1; i <= input; i ++) {
    printf("%d ", a[i]);
  }
  
  return 0;
}

上のコードを少し修正すれば、前の桶の並べ替えではできない生徒情報と浮動小数点の問題を解決できます.

struct Student {
  char name[20];
  float score;
};

int main(int argc, const char * argv[]) {
  
  struct Student s[100];
  int scannedNumber;
  
  scanf("%d", &scannedNumber);
  
  for (int i = 1; i <= scannedNumber; i ++) {
    scanf("%s %f", s[i].name, &s[i].score);
  }
  
  //       
  for (int j = 1; j <= scannedNumber - 1; j ++) {
    for (int k = 1; k <= scannedNumber - j; k ++) {
      if (s[k].score < s[k+1].score) {
        struct Student temp = s[k];
        s[k] = s[k + 1];
        s[k + 1] = temp;
      }
    }
  }
  
  for (int l = 1; l <= scannedNumber; l ++) {
    printf("%s, %.2f
", s[l].name, s[l].score);
  }
  
  return 0;
}

完璧に解決しました.入力:

dylan 81.5
alice 64.6
peter 91.4
bobo 31.9
amy 67

出力:

peter, 91.40
dylan, 81.50
amy, 67.00
alice, 64.60
bobo, 31.90

泡の並べ替えの中心部分は入れ子循環であり、泡の循環の複雑さは以下の通りであることが分かります.

O(N^2)

これは非常に複雑な時間で、泡の並べ替えは魅力的な名前を除いて、複雑な時間で見て、何かオススメがありますか?
クイックソート
泡の並べ替えは私達の勉強の最初のアルゴリズムと言えますが、時間の浪費が非常に多いです.計算機が10億回/秒を実行すると仮定して、桶の並べ替えは10億+1の位置が必要ですが、0.1 sだけ必要です.泡の並べ替えには1千万秒が必要です.次に私たちは高速の並べ替えを知る.まず、快速並べ替えの核心方法を覚えます.基準数は左の一番目の数で、基準数は左の方が全部小さくて、右の方が全部それより大きいです.だから2つの起点は、一番左、一番右側です.センターに向かって触発し、右側を先に(左を基準数として、必ず右から左に、まず何のために説明するかを考えてください)、右から左に基準数の小さい数字を探して、左から右に基準数の大きい数字を探して、彼らを交換します.左右で会うときは、現在の数字と基準数の位置を交換します.基準数が位置を確認したら、基準数は左、右が2つのサブ列に分かれています.再帰を使用しましたので、このような数列があると仮定して、過程をシミュレーションしてみます.

6, 1, 2, 7, 9, 3, 4, 5, 10, 8

私達は一番左の6を初期基準数として、左から右に6より大きい数を探して、右から左に6より小さい数字を探して交換しています.右から左に1番目の6より小さい数字は5で、左から右に1番目の6より大きい数字は7で、彼らの位置を交換しています.

6, 1, 2, 5, 9, 3, 4, 7, 10, 8

続いて、前を探し続けて、左を右に9を見つけました.右に4を見つけました.だから彼らを交換します.

6, 1, 2, 5, 4, 3, 9, 7, 10, 8

前に進むといけないです.2人がぶつかってしまいました.この時、基準数とこの数字を交換する場所:

3, 1, 2, 5, 4, 6, 9, 7, 10, 8

このように、基準数字6はすでに位置に戻り、左は6より小さい数字であり、右は6より大きい数字である.次に、左と右の二つの数列を処理します.

3, 1, 2, 5, 4
9, 7, 10, 8

最初のシーケンスを処理します.3は基準数です.

   i→      ←j
3, 1, 2, 5, 4
       
2, 1, 3, 5, 4
       
  1： 2, 1   -> 1, 2

  2： 5, 4   -> 4, 5

右から先に始まるので、2の位置で衝突し、交換位置で結果が得られます.みんな自分で分析してみます.最終ソートが終了しました.そして上の思想に基づいてコードを書きます.

int a[11];
int count = 10;
void sort(int left, int right);

int main(int argc, const char * argv[]) {
  
  for (int i = 1; i <= count; i ++) {
    scanf("%d", &a[i]);
  }
  
  sort(1, count);
  
  for (int j = 1; j <= count; j ++) {
    printf("%d ", a[j]);
  }
  
  return 0;
}

void sort(int left, int right) {
  if ( left > right ) {
    return;
  }
  
  //      
  int refNum = a[left];
  
  //       
  int lPoint = left;
  int rPoint = right;
  
  //         ，     
  while (lPoint != rPoint) {
    //       ，        ,     ，      ，       ，rPoint      ，    ，        ，rPoint            
    while (a[rPoint] >= refNum && lPoint < rPoint) {
      rPoint --;
    }
    
    //    ，        ，    
    while (a[lPoint] <= refNum && lPoint < rPoint ) {
      lPoint ++;
    }
    
    //     
    if ( lPoint < rPoint ) {
      int temp = a[lPoint];
      a[lPoint] = a[rPoint];
      a[rPoint] = temp;
    }
  }
  
  //       ，    ，             ，            
  a[left] = a[lPoint];
  a[lPoint] = refNum;
  //     ，      ，         
  sort(left, lPoint - 1);
  sort(lPoint + 1, right);
  
  return ;
}

以上の問題を振り返ってみましょう.
基準数字は左にあります.左から先に始めて、基準数字より大きい数字を探しています.

3, 1, 2, 6, 7

上のように、数字6を見つけた時、左に止まって、右から探してみたら、直接衝突しました.

6, 1, 2, 3, 7

でも右から始めると

2, 1, 3, 6, 7

締め括りをつける
並べ替えのアルゴリズムはまだたくさんあります.数え方、基数、挿入、まとめ、積み上げなどは後からゆっくりと触れます.もちろん、早く並ぶ時間の複雑さはどう計算しますか?私達は考えてみます.最悪の場合は泡が出るように、隣の2つの数字が絶え間なく交換されます.

O(N^2)

一番早いのは複雑度です.

O(NLogN)

キーワードの比較と交換はホッピングで行われるので,高速秩序化は不安定な秩序化法である.
練習します
不定数量の数字を並べ替えて、1秒以内に完成することを要求します.
この問題を取ったら、私達が関心を持っているのは1 s以内で、数字は定量的ではないはずです.上で提供した時間の複雑さによって言います.現在の範囲がスーパー大きいと、バケツの並べ替えは基本的に不可能です.そんなに大きい配列は申請できないので、数字がスーパー多いと、発泡体の並べ替え時間の複雑さは9, 7, 10, 8です.コードが省略されました
本論文は終了する.