c++ - 如何使用 STL 容器实现库排序算法？

Question

我正在尝试实现这个排序算法:http://en.wikipedia.org/wiki/Library_sort .我有一些函数 grupBul 用于查找合适的组，grupSirala 用于对每个组进行排序。我必须留下一些空白并将它们包含在另一个数据结构的 vector 中。

我该如何执行此操作？到目前为止，我有这段代码:

#include "librarySort.h"
#include <iostream>
#include <vector>
#include <math.h>
#include "sort.h"
using namespace std;

#define EPSILON 10 //Epsilon sabiti
#define GRUPDEFBOYUT 20 //Gruplarin baslangiç boyutu

//gruplar[grupno][degerler] grupboyutu->[0] minimumeleman->[1] maksimumeleman->[2]
vector<vector<int> > gruplar;

int grupBul(vector<int*> &dizi,int sayi){
    for(int i=0;i<gruplar.size();i++){
        if(*dizi[gruplar[i][1]]<sayi && *dizi[gruplar[i][2]]>sayi){
            return gruplar[i][2];
        }
    }

    for(int i=gruplar.size()-1;i>=0;i--){
        if (*dizi[gruplar[i][2]]<sayi){
            return gruplar[i][2];
        }
    }
    if(*dizi[gruplar[0][1]]>=sayi){
        return gruplar[0][2];
    }
}

int maxBul(vector<int*> &dizi,int baslangic,int son){
    int max=*dizi[baslangic];
    int index=baslangic;
    for(int i=baslangic+1;i<son;i++){
        if(*dizi[i]>max){
            max=*dizi[i];
            index=i;
        }
    }

    return index;
}

int minBul(vector<int*> &dizi,int baslangic,int son){
    int min=*dizi[baslangic];
    int index=baslangic;
    for(int i=baslangic+1;i<son;i++){
        if(*dizi[i]<min){
            min=*dizi[i];
            index=i;
        }
    }

    return index;
}

void ilkGruplariOlustur(vector<int*> &dizi,int son){
    int grupboyut=0;
    int grupno=0;
    for(int i=0;i<5;i++){
        vector<int> grup;

        grup.push_back(GRUPDEFBOYUT);
        grup.push_back(minBul(dizi,grupboyut,GRUPDEFBOYUT+grupboyut));
        grup.push_back(maxBul(dizi,grupboyut,GRUPDEFBOYUT+grupboyut));

        gruplar.push_back(grup);

        /*for(int j=0;j<EPSILON;j++)
            dizi.push_back(NULL);*/
        grupboyut+=GRUPDEFBOYUT;
        grupno++;
    }
}

void grupSirala(vector<int*> &dizi,int baslangic,int son){
    int j = 0;
    int mover;

    for ( int i = baslangic + 1 ; i < son ; i++ ) {
        mover = *dizi[i];
        j = i-1;

        while ( ( j >= 0 ) && ( *dizi[j] > mover) ){
            *dizi[j+1] = *dizi[j];
            j--;
        }
        *dizi[j+1] = mover;
    }
}

void bosluklariOlustur(vector<int*> &dizi){
}

int librarySort( int *data , unsigned int size) {
    int kok_n=(int)sqrt((double)size);
    int boyut=size;

    vector<int*> sirali_dizi;

    for(int i=0;i<kok_n;i++){
        sirali_dizi.push_back(new int(*(data+i)));
    }

    ilkGruplariOlustur(sirali_dizi,0);
    for(int i=0;i<sirali_dizi.size();i++)
        cout << *sirali_dizi.at(i)<< " ";

    for(int a = 0;a<10;a++)
        sirali_dizi.push_back(NULL);
    grupSirala(sirali_dizi,0,kok_n);

    for(int i=0;i<5;i++){
        for(int j=0;j<3;j++)
            cout << gruplar[i][j] << " ";
    }
    /*
    cout<<endl<<"Sirali dizi"+i<<endl;
    for(int t=0;t<20*(i+1)+EPSILON;t++)
        cout << *sirali_dizi.at(t)<< " ";
    cout<<endl;
    }
    cout<<endl;
    cout<<endl;
    cout<<endl;

    grupSirala(sirali_dizi,0,sirali_dizi.size());*/
    for(int i=0;i<sirali_dizi.size();i++)
        cout << *sirali_dizi.at(i)<< " ";

    return 0;
}

Answer 1

嗯，vector 有一个 resize允许您在插入数据之前基本上预设 vector 大小的方法。然后从那里您将能够使用 operator[]在适当的空间插入数据。

附带说明一下，如果我正在处理这个项目/家庭作业，我个人不会使用 STL。