标签: stable-sort

NumPy 的np.argsort能够通过传递参数进行稳定排序kind = 'stable'。

也不np.argsort支持反向（降序）顺序。

如果需要不稳定行为，则可以通过 轻松建模降序desc_ix = np.argsort(a)[::-1]。

我正在寻找高效/简单的解决方案来降序稳定排序 NumPy 的a任何可比较的数组dtype。请参阅我在上一段中对“稳定性”的含义。

对于任何数值的情况，dtype可以通过对数组的否定版本进行排序来轻松完成稳定的降序参数排序：

print(np.argsort(-np.array([1, 2, 2, 3, 3, 3]), kind = 'stable'))
# prints: array([3, 4, 5, 1, 2, 0], dtype=int64)

但我需要支持任何类似的，dtype包括np.str_和np.object_。

只是为了澄清 - 也许对于降序排列的经典含义stable意味着相等的元素是从右到左枚举的。如果是这样，那么在我的问题中，含义stable + descending有所不同 - 元素的相等范围应该从左到右枚举，而彼此之间的相等范围按降序排列。即应该像上面的最后一个代码一样实现相同的行为。也就是说，我想要某种意义上的稳定性，就像 Python 在下一个代码中实现的那样：

print([e[0] for e in sorted(enumerate([1,2,2,3,3,3]), key = lambda e: e[1], reverse = True)])
# …

我有一个结构向量，每个结构都有一个数字 ID，我用它来对向量项进行排序。我希望对 ID 进行排序，但在排序后也按照它们在原始向量中的顺序显示。让我解释...

假设你有一个像这样的向量（忽略结构）：

vector<int> items = {
    1,
    2,
    5, // First 5
    8,
    9,
    6,
    5, // Second 5
    4,
    7,
    3,
    5, // Third 5
    10
};

排序后我希望向量看起来像这样：

vector<int> items = {
    1,
    2,
    3,
    4,
    5, // First 5
    5, // Second 5
    5, // Third 5
    6,
    7,
    8,
    9,
    10
};

请记住，这些项目实际上是结构。多个可以具有相同的 ID，但其他属性的值不同。现在，我认为结构在排序后没有可预测的顺序。有没有办法保证这种输出？我可以向结构添加另一个属性来指示其原始顺序，并以某种方式在排序算法中使用它吗？

我使用C++ stable_sort使用比较器函数按升序对我的类对象的向量进行排序,但排序不稳定.解决这个问题的方法是反转迭代并反转比较器中的逻辑.但是无法理解为什么它不能正常工作.码:

using namespace std;
class Pair{
    string str;
    int num;
public:
    Pair(string s, int n):str(s), num(n)
    {}
    Pair(const Pair &a)
    {
        str = a.str;
        num = a.num;
    }
    int Num()
    {
        return num;
    }
    string Str() const{
        return str;
    }
    void set(string s, int n)
    {
        str = s;
        num=n;
    }
    void print() const{
        cout<<"\n"<<num<<" "<<str;
    }
};

bool comparator( Pair a,  Pair b)
{
    return a.Num()<=b.Num();
}

int main() {
    int n;
    cin >> n;
    vector<Pair> arr;
    for(int …

这里看起来像3在两行之后的空格打破了数字排序并让字母排序开始，所以11< 2：

$ echo -e '3 2\n3 11' | sort -n
3 11
3 2

在man sort，我读

       -s, --stable
              stabilize sort by disabling last-resort comparison

Run Code Online (Sandbox Code Playgroud)

这意味着没有 -s一个不得已的比较是完成（之间的关系，因为-s不影响非关系）。

所以问题是：这种最后的比较是如何完成的？如果有必要回答问题，欢迎参考源代码。

这个答案 Unix从实验中推断出关系的排序是按字典顺序排列的。

标准/POSIX 是否对此有任何说明？

与一般的快速排序算法不同,我可以使用额外的数组来执行稳定的快速排序.我知道如何随机选择枢轴并相应地进行分区,但我无法弄清楚如何利用附加阵列使其稳定.

我刚刚阅读了Table.sort上的官方Lua文档,并注意到它说:

"[Table.sort]算法不稳定 ;也就是说,被给定顺序认为相等的元素可能会通过排序改变它们的相对位置."

任何想法什么时候Table.sort会在Lua变得稳定？

它是有史以来好叫stable_sort的,而不是sort标量类型(如int,long等)默认的比较？

如果是这样,你应该什么时候这样做？

如果没有,那么为什么标准库不转发这样的调用sort呢？这会不会更快？