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

Question

我正在尝试实现这个排序算法：http://en.wikipedia.org/wiki/Library_sort。我有一些函数用于找到合适的分组（grupBul）和对每个分组进行排序（grupSirala）。我需要留下一些空隙并将它们包含在另一个数据结构的向量中。

我该如何操作呢？目前我的代码是：

#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;
}

- droidmachine

---

由于代码是用外语编写的，几乎无法理解和提供帮助。这就是为什么你应该始终只使用英语编写代码（和注释）的原因。 - Konrad Rudolph

Answer 1

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

顺便说一句，如果我在这个项目/作业上工作，我个人不会使用STL。

- Keith

---

你的意思是你使用自己的向量库？ - droidmachine

如果你的意思是创建类似于STL向量的东西，那么不行。我会使用new[]（注意方括号）和delete运算符自己进行内存分配/释放。 - Keith