【分割】連結ソート(集計ソート)-HSU 1106ソート

タイトル
HDU 1106ソート
もんだいぶんせき
この問題は5をスペースと見なし、文字列から整数を分け、整数を小さい順に出力すればよいということです.(実はこのテーマを借りて合併ソート(集計ソート)を熟知しているだけで、問題を考えているだけならそんなに面倒ではなく、sortを直接書けばいいのです)
アルゴリズム#アルゴリズム#
アルゴリズムコア
この問題では、ソート部分で集計ソートを採用します.集計ソートとも呼ばれます.集計ソート(集計ソート)とは、1組の数を2組の数の差が少ない数に分けて、それぞれ2組の数をソートしてから集計すればいいです.連結ソートは再帰的に実現され、再帰は最終的に各グループに1つの数しかないので、この数は明らかに秩序化され、その後上に連結され、2つの数の秩序化シーケンスが得られ、最終的に数列全体が秩序化されるまで上に連結されます.
アルゴリズムフロー
文字列の中の整数を分けた部分についてはあまり紹介しませんが、具体的にはコードを見てください.集計ソートについて説明します.b[]:並べ替え結果を一時保存する配列;a[]:ソート対象配列;l:開始要素の下付き文字を並べ替えます.r:中止要素の下付き文字をソートする;i:前のシーケンス[l,mid]の制御変数;j:後のシーケンス[mid+1,r]の制御変数;k:b[]の制御変数;まず、マージ関数について説明します.前のシーケンスと後のシーケンスはマージソートされているので、2つのシーケンスは最初から見ればいいです.iとjが指す要素を比較して、小さいものをb[]に入れ、変数の後移動(iまたはj、そしてk)を制御して、2つのシーケンスの1つがすべてb[]に入るまで、別のシーケンスの残りの要素をb[]に入れればいいです.次にソート関数をマージします.ここでは2つのパラメータlとrを入力したり、3つにa[]を追加したりすることができますが、a[]をグローバル配列として定義しているので、2つを転送すればいいです.lの場合
コード実装

#include
#include
using namespace std;
const int maxn=1005;

int a[maxn];//         

void Merge(int l,int mid,int r)//  
{
    int b[maxn];
    memset(b,0,sizeof(b));
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)//         
    {
        if(a[i]mid// の  を う
{
while(j<=r)
b[k++]=a[j++];
}
else
{
while(i<=mid)
b[k++]=a[i++];
}
for(i=l,j=0; j>s)
{
memset(a,0,sizeof(a));
int i,j=0;
bool flag=false;
for(i=0; i