表格单元/ 2d数组排序算法

Question

是否有一种算法可以帮助对下面的左表(这是多维标量或对象数组的抽象)进行排序，以便结果将与右边的表一样，因为在正确的表中可能有有限的可用深度(例如，最多30行)？

​

​

问题的更复杂的版本(单元格中的第一个键优先于另一个)：

​

​

编辑：和其他层次的复杂性(合并行/级别，如果这样做是安全的，以防止冗余)：

​

​

Answer 1

一种可能的解决办法是：

#include <vector>
#include <iostream>
#include <algorithm>

using Column = std::vector<int>;
using Matrix = std::vector<Column>;

Column max_col(const Matrix &m) {
    return *std::max_element(m.begin(), m.end(),
                             [](auto& lhs, auto& rhs)
                             {
                                 return lhs.size() < rhs.size();
                             });
}

bool is_element_in_next_rows(const Matrix &m, int element,Column::size_type row) {
    for (auto& col : m) {
        if (row >= col.size()) continue; // out of range
        if (*std::lower_bound(col.begin()+row+1,col.end(),element) == element) {
            return true;
        }
    }
    return false;
}

int min_element_in_row(const Matrix &m, Column::size_type row) { 
    int min_element = max_col(m)[row];
    for (auto& col : m) {
        if (row >= col.size()) continue; // out of range
        if (col[row] != 0) min_element = std::min(min_element, col[row]);
    }
    return min_element;
}

void print_elements(const Matrix &m) {
    for (auto& i : m) {
        for (auto& j : i) {
            std::cout << j << " ";
        }
        std::cout << std::endl;
    }
}

void organize_elements(Matrix &m) {
    for (auto& col : m) {
        std::sort(col.begin(),col.end());
    }
    auto current_max_col = max_col(m);
    for (Column::size_type row{0}; current_max_col.begin()+row!=current_max_col.end(); ++row) {
        int min_element = min_element_in_row(m,row);
        for(auto& col : m) {
            if (row >= col.size()) continue; // out of range
            int candidate = col[row];
            if (candidate > min_element) {
                if (is_element_in_next_rows(m,candidate,row)) {
                    col.insert(col.begin()+row,0);
                }
            }
        }
        current_max_col = max_col(m);
    }
}

int main() {

    Column c1 = {5,6,8};
    Column c2 = {2,5,3,1,4,6};
    Column c3 = {8,7,2,4,5,3,1};

    Matrix m;
    m.push_back(c1);
    m.push_back(c2);
    m.push_back(c3);

    std::cout << "original: \n";
    print_elements(m);
    organize_elements(m);
    std::cout << "organized: \n";
    print_elements(m);
    return 0;
}

其产出如下：

original: 
5 6 8 
7 2 5 3 1 4 6 
8 7 2 4 5 3 1 
organized: 
0 0 0 0 5 6 8 
1 2 3 4 5 6  
1 2 3 4 5 7 8 

包含对是很容易的，只需更改它们的比较函数。我不知道这是不是你的意思。它还可以进一步优化，这是一个快速的解决方案，可能满足您的需要或激励您为更好的。

Answer 2

每个列中的元素是否限制了列的深度？如果是这样，只需遍历多维数组的每一列，并将元素放在相应的行中。如果您分配了更多的内存，或者可以通过交换(仍然是O(n))就地执行，那么这样做很简单。您可以在事后应用更复杂的分组。