标签: stable-sort

考虑以下问题.

我们给出了一组属于两个类的元素:红色或蓝色.我们必须重新排列数组的元素,以便所有蓝色元素首先出现(并且所有红色元素都会出现).必须以稳定的方式完成重新排列,这意味着必须保留蓝色元素的相对顺序(红色元素的相对顺序).

是否有一个聪明的算法可以就地执行上述重新排列？

当然,非现场解决方案很简单.

一个明显的就地解决方案是将任何稳定的排序算法应用于阵列.然而,在阵列上使用完整的排序算法直观地感觉就像是一种过度杀伤,特别是考虑到我们只处理两类元素这一事实.

任何想法都非常感激.

如何稳定排序数组？我想要排序的值可能有很多重复,我不确定ruby使用哪种排序算法.我认为插入排序对我来说效果最好.

例:

a = [[:a, 0], [:b, 1], [:c, 0], [:d, 0]]
a.sort_by { |x, y| y }  # => [[:a, 0], [:d, 0], [:c, 0], [:b, 1]]

寻找

[[:a, 0], [:c, 0], [:d, 0], [:b, 1]]

给定一个n个元素的数组，是否有一个排序算法

1. 排序最多O(n log n)时间（并且可选地，在最好的情况下， O(n)时间）
2. 是稳定的
3. 占用O(1)辅助空间

我发现的所有排序算法仅满足以下标准中的两个：

• 冒泡排序满足2和3
• 归并排序满足1和2
• 堆排序满足1和3

有没有一种算法可以满足这三个标准？

MATLAB的内置函数accumarray接受函数fun作为第四个参数.

A = accumarray(subs,val,sz,fun);

这适用fun于val具有相同下标的元素的每个子集subs.但文件说明:

如果下标subs未按其线性索引排序,则fun不应取决于其输入数据中值的顺序.

我们如何实现一个没有这个限制的稳定版本accumarray,但是会保证子集采用与给定的相同的顺序val？

例:

subs = [1:10,1:10];
val = 1:20;
accumarray(subs(:), val(:), [], @(x)x(end)).'

这样做的预计产出将是11:20,如果accumarray是稳定的.实际上输出是:

ans =
    11    12    13    14     5     6     7    18    19    20

我们的实施应该产生:

accumarrayStable(subs(:), val(:), [], @(x)x(end)).'`
ans =
    11    12    13    14    15    16    17    18    19    20

我认为问题标题足够清楚:是否可以在C++中使用stable_sort()一个std :: list？或者我必须将其转换为std :: vector？

我问,因为我尝试了一个简单的例子,它似乎需要RandomAccessIterators,链表没有.那么,我如何稳定排序std :: list()？

编辑:示例代码,给我一个错误:

#include <list>
#include <algorithm>
// ...
list<int> the_list;
stable_sort(the_list.begin(), the_list.end());

g ++给了我大约30行错误(粘贴时间太长),其中一些错误指的是RandomAccessIterators(以及一些名为_merge_sort_loop的东西).这有点奇怪,因为我已经看到链接列表的一些合并排序实现,它们几乎是"顺序的".

以下两个代码片段之间有什么区别.

vector<int> a;
// initialization code
sort( a.rbegin(), a.rend() );

和

vector<int> a;
// same initialization as above
sort(a.begin(), a.end(), comp);

其中comp是下面给出的布尔函数

bool comp( int i, int j)
{
    return i>j;
}

为了说明,下面的代码给出了WA,而这段代码为SPOJ问题XMAX提供了AC.AC和WA之间的唯一区别是使用的sort()版本.

从引用的各种来源我知道内置的C函数,stable_sort是稳定的但qsort是不稳定的.如果是这种情况,我们为什么要使用qsort呢？这不是多余的吗？为什么不使用stable_sort呢？

所以,实际上我需要的是在排序之后保留旧数组的索引.所以例如,如果我输入[2,4,1,5,7,9,6]那么输出是[2,0,1,3,6,4,5].我已经使用了qsort,如果没有重复的元素,它的效果非常好.

如果存在重复元素,有时会将第一个重复元素放在最后.例如,如果输入是[5,4,6,5,2,1,3],我想要输出的是[5,4,6,1,0,3,2].那么,5哪个索引0放在5哪个之前有索引3.但是,qsort有时使用输出[5,4,6,1,3,0,2].

你能帮我解决这个问题吗？或者我应该创建自己的排序功能？你能帮我创建一下吗？

这是我的代码:

#include <stdlib.h>

int* sortidx(double *X,int n)
{
    int *idx,i,j;

    int cmp(const void *a,const void *b)
    {
        return X[*(int*)a]>=X[*(int*)b]?1:-1;
    }

    idx=(int*)calloc(n,sizeof(int));

    for(i=0;i<n;i++)
    {
        idx[i]=i;
    }

    qsort(idx,n,sizeof(int),cmp);

    return idx;
}

在.NET中是否有任何内置的稳定排序例程？

我知道C++在"算法"下有一个内置的排序例程std::sort().同样,我们有什么东西可以和C#一起使用吗？

另外,.NET中是否有内置交换功能？

我正在做一个简单的StringList.sort,但是Delphi使用的QuickTort不是一个稳定的排序,这意味着它可能会改变具有相同键的记录的相对顺序.

我需要使用稳定的排序.对我来说,实现这个最简单的方法是什么？

Mike W的答案可能是最简单的方法,无需进行太多的代码更改.

谢谢,迈克.