0

假设我们有以下二维整数数组：

1 3 3 1
1 0 2 2
2 0 3 1
1 1 1 0
2 1 1 3

我试图创建一个实现，用户可以将数组本身和字符串作为输入。上面示例中的字符串示例03将意味着用户希望根据第一列和第四列对数组进行排序。

所以在这种情况下，排序的结果如下：

1 1 1 0
1 3 3 1
1 0 2 2
2 0 3 1
2 1 1 3

我不太了解 STL 函数中使用的比较函数sort，但是在搜索后我创建了以下简单实现：

我创建了一个名为Comparator.h

   class Comparator{

     private:
      std::string attr;

     public:
      Comparator(std::string attr) { this->attr = attr; }

      bool operator()(const int* first, const int* second){
       std::vector<int> left;
       std::vector<int> right;
       size_t i;
       for(i=0;i<attr.size();i++){
                left.push_back(first[attr.at(i) - '0']);
                right.push_back(second[attr.at(i) - '0']);
        }
        for(i=0;i<left.size();i++){
                if(left[i] < right[i]) return true;
                else if(left[i] > right[i]) return false;
        }
        return false;
      }

     };

我需要知道字符串中的信息，所以我需要有一个类，这个字符串是一个私有变量。在operatorI 内部有两个参数first和second，每个参数都指向一行。现在有了这些信息，我创建了一个left和一个right向量，其中在left向量中我只有对first排序很重要并且由字符串变量指定的行号，在right向量中我只有second重要的行号到排序并由字符串变量指定。

然后我进行所需的比较并返回真或假。用户可以通过在类中调用这个函数来使用这个Sorting.cpp类：

void Sorting::applySort(int **data, std::string attr, int amountOfRows){

  std::sort(data, data+amountOfRows, Comparator(attr));

 }

这是一个使用示例：

int main(void){
    //create a data[][] variable and fill it with integers
    Sorting sort;

sort.applySort(data, "03", number_of_rows);
}

我有两个问题：

第一个问题

我的实施能变得更好吗？我使用了额外的变量，比如left和right向量，然后我有一些 for 循环，这给排序操作带来了一些额外的成本。

第二个问题

由于额外的成本，排序的时间复杂度会变差多少？我知道 STLsort是O(n*logn)您n要排序的整数的数量。这里n有不同的含义，n是行数，每行最多可以有m整数，而这些整数又可以Comparator通过覆盖operator函数并使用额外的变量（向量）和 for 循环在类中找到。

因为我不确定 STL 是如何sort实现的，所以我只能做一些估计。我最初的估计是对排序很重要的列数在O(n*m*log(n))哪里m，但我不能 100% 确定它。

先感谢您

4

3 回答 3

2

你当然可以改进你的比较器。无需复制列然后进行比较。而不是这两个push_back调用，只需比较值并根据它们是小于、大于还是等于返回 true、返回 false 或继续循环。

复杂性的相关部分sort是O(n * log n)比较（在 C++11 中。C++03 并没有给出很好的保证），其中n是被排序的元素的数量。因此，只要您的比较器是O(m)，您的估计就可以对n行进行排序。因为attr.size() <= m，你是对的。

于 2013-03-16T14:12:21.833 回答
1

第一个问题：你不需要 left 和 rigth - 你一个接一个地添加元素，然后以相同的顺序迭代向量。因此，与其将值推送到向量然后对其进行迭代，不如简单地使用在第一个周期中生成它们的值，如下所示：

    for(i=0;i<attr.size();i++){
            int left = first[attr.at(i) - '0'];
            int right = second[attr.at(i) - '0'];
            if(left < right) return true;
            else if(left > right) return false;
    }

第二个问题：时间复杂度可以提高吗？不适用于使用直接比较的排序算法。另一方面，您在这里解决的问题有点类似于radix sort。所以我相信你应该能够在 O(n*m) 中进行排序，其中 m 是排序标准的数量。

于 2013-03-16T14:09:22.003 回答
1

1）首先，您应该在构造函数中将字符串转换为整数数组。验证值小于列数。

（您也可以有另一个将整数数组作为参数的构造函数。一个轻微的改进是允许负值表示该列的排序顺序是相反的。在这种情况下，值将是 -N..- 1 , 1..N)

2) 不需要中间的左、右数组。

于 2013-03-16T14:10:22.153 回答