アルゴリズム→並べ替え→並べ替え、並べ替え、基数並べ替え

1、並べ替え
正規化順序付け:正規化技術を利用して順序付けを実施し、いくつかの順序付けられたサブシーケンスを一つの順序付けられたシーケンスに統合することは、安定した順序付け2つの正規化アルゴリズムである.二つの順序付けられたシーケンスを一つの順序付けられたシーケンスに統合する.具体的なプロセスは、i,jは、それぞれ2つのワードシーケンスを指し、その中の最小値を取得する度に、i,jは、シーケンスの次の要素を指し、すべての要素が新しいシーケンスに順序付けされるまで移動する.
正規並べ替えは2種類に分けられています.ボトムアップの帰結アルゴリズムとボトムアップの帰結アルゴリズムです.
自己ボトムアップの正規化アルゴリズム:シーケンス中の要素を2つに結合し、新たな秩序秩序秩序秩序秩序を獲得し、2つのマージを行い、最終的には正規化と並べ替えシーケンスを得る.具体的には次の3つの関数があります.void merge(vector&vec,int low,int m,int high);両方のアルゴリズムを統合し、lowは開始位置であり、mは境界位置であり、highは終了位置(いずれも下付き値)void mergonce(vector&vec、int len)である.ボトムアップの帰結、1つのアルゴリズム、lenはサブシーケンス長void mergsort(vector&vec)である.ボトムアップの正規化順序付け関数というアルゴリズムは複数の正規化演算を行う必要があり、それぞれの呼び出しmere関数は2つのシーケンスを結合し、性質によっては、後の各必要なサブシーケンスが少なくなる.プレゼンテーションアニメーション:http://student.zjzk.cn/course_ware/data_structure/web/flash)/guibingpaixu.httmのボトムアップ・ソートアルゴリズムは効率的ですが、可読性は低いです.
分割された思想を用いて、直下に帰順して並べ替えます.つまり、各シーケンスの中点を境界として、それぞれ両側に帰合し、両要素が帰結するまで送ります.最終的には、元に戻すことができ、順序を並べ替えることができます.
具体的なアルゴリズムの実装はコードを参照してください.

#include <iostream>
#include <vector>
using namespace std;
const int N = 20;    //           #define N 20 

void disp(vector<int> vec);   //    ,
void merge(vector<int> &vec,int low, int m, int high);   //      ,low     ，m     ，high     （     ）
void mergeonce(vector<int> &vec, int len);  //       ，    ，len      
void mergesort(vector<int> &vec);    //           
void mergesort2(vector<int> &vec,int low, int high);   //           


int main()
{
    vector<int> vec1(N),vec2;
    int a[N] = {2 ,19 ,3 ,25 ,4 ,0,8,22,10,2,9,45,12,16,21,41,6,18,34,10};
    //int a[N] = {0,1,2,3,4,5,6,7,8,9,10,1,2,3,4,15,16,17,18,19};
    for(int i = 0; i < N; i++)
        vec1[i] = a[i];
    vec2 = vec1;
    disp(vec1);
    disp(vec2);
    mergesort(vec1);      //         
    mergesort2(vec2, 0, 19);   //         
    disp(vec1);
    disp(vec2);
    return 0;
}

void disp(vector<int> vec)   //    
{
    cout << "     ：";
    for(int i = 0; i < N; i++)
        cout << vec[i] << " ";
    cout << endl;
}

void merge(vector<int> &vec,int low, int m, int high)
{
    int i,j,p = 0;
    vector<int> vecr(high+1);
    //int *vecr = new int[high+1]; //           ，     delete [] vecr;
    i = low;
    j = m+1;
    while(i<=m && j<=high)
        vecr[p++] = (vec[i] < vec[j]) ? vec[i++] : vec[j++];
    while(i<=m)
        vecr[p++] = vec[i++];        //   1      ，        vecr 
    while(j<=high)
        vecr[p++] = vec[j++];        //   2      ，        vecr 
    for(p = 0, i = low; i<=high; p++, i++)     //     ，    vec 
        vec[i] = vecr[p];
}

void mergeonce(vector<int> &vec, int len)
{
    int i;
    for(i = 0; i+2*len < N; i = i+2*len)
        merge(vec,i,i+len-1,i+2*len-1);
    if(i+len-1 < N-1)  //      ，        len
        merge(vec,i,i+len-1,N-1);
}

void mergesort(vector<int> &vec)
{
    int len;
    for(len = 1; len < N-1; len*=2)
        mergeonce(vec,len);
}

void mergesort2(vector<int> &vec,int low, int high)
{
    int mid;
    if(low < high)
    {
        mid = (low+high)/2;
        mergesort2(vec, low, mid);    //    
        mergesort2(vec, mid+1, high);
        merge(vec, low, mid, high);
    }
}

2、基数並べ替え
基数並べ替え(Radix Sort)は箱の並べ替えの改良と普及である.は、安定しています.複数のキーワードを利用してシーケンスを並べ替えます.例えば、10進数、15、23は、まずビット数を利用して並べ替えてから、10桁を並べ替えてもいいです.
基本的な考え方は、下位から上位に順番にKj(j=d-1,d-2,…,0)を箱順に並べます.d箱の並べ替えに必要な箱の数は基数rdで、これは「基数並べ替え」の名前の由来です.基数概念:単キーワードの各成分の取値範囲を設定すると、C 0≦kj≦Crd-1の可能な取値の個数rdを基数と呼びます.基数の選択とキーワードの分解はキー宇の種類によって違います.(1)キーワードが十進数の整数なら、個、十等位で分解します.基数rd=10、C 0=0、C 9=9、dは最長整数の桁数です.(2)キーワードが小文字の英語文字列であれば、rd=26,Co='a',C 25='z',dは文字列の最大長さとなります.プレゼンテーションアニメーション:http://student.zjzk.cn/course_ware/data_structure/web/flash)/jishuplaixu.httm
以下のコードは、0〜99の整数を並べ替えるために実装されています.ここでは、ポインタ配列を使用して箱を表しています.各箱はキューであり、要素は先進的な先駆的な性質を持っています.全部で10個です

#include <iostream>
#include <vector>
#include <deque> //        
using namespace std;
const int N = 20;    //           #define N 20 

void disp(vector<int> vec);   //    
void radixsort(vector<int> &vec);   //   0-99   

int main()
{
    vector<int> vec1(N),vec2;
    int a[N] = {2 ,19 ,3 ,25 ,4 ,0,8,22,10,2,9,45,12,16,21,41,6,18,34,10};
    //int a[N] = {0,1,2,3,4,5,6,7,8,9,10,1,2,3,4,15,16,17,18,19};
    for(int i = 0; i < N; i++)
        vec1[i] = a[i];
    //vec2 = vec1;
    disp(vec1);
    radixsort(vec1);
    disp(vec1);
    return 0;
}

void disp(vector<int> vec)   //    
{
    cout << "     ：";
    for(int i = 0; i < N; i++)
        cout << vec[i] << " ";
    cout << endl;
}

void radixsort(vector<int> &vec)    //    ，         ，         
{
    int i,j,t;
    //deque<int>de;
    deque<int> *deq[10];    //    ，          deque<int>   
    for(j = 0; j<10; j++)   //    
        deq[j] = new deque<int>;
    for(i = 0; i<N; i++)    //       
    {
        t = vec[i]%10;     //       
        deq[t]->push_front(vec[i]);   //  ,        
        //(*deq[t]).push_front(vec[i]);        ，        
    }
    i = 0;
    for(j = 0; j<10; j++)    //        
    {
        while(!(deq[j]->empty())){
            vec[i] = deq[j]->back();
            deq[j]->pop_back();
            i++;
        }
    }
    for(i = 0; i<N; i++)   //        
    {
        t = vec[i]/10;
        deq[t]->push_front(vec[i]);
    }
    i = 0;
    for(j = 0; j<10; j++)    //        
    {
        while(!(deq[j]->empty())){
            vec[i] = deq[j]->back();
            deq[j]->pop_back();
            i++;
        }
        delete deq[j];
    }
}