stable-sort

4热度

2回答

所以，实际上我需要的是在排序后保留旧数组的索引。因此，例如，如果我输入[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有时会输

1热度

2回答

如何使用O（n）额外空间实现稳定的快速排序算法？

与一般的快速排序算法不同，我可以使用额外的数组来执行稳定的快速排序。我知道如何随机选择分区和相应的分区，但我无法弄清楚如何使用附加数组来使其稳定。

4热度

3回答

如何将以下非稳定排序算法转换为稳定？

考虑n表示标记牌为红色或蓝色 i=1; j=n; while(i<n) { if(a[i]==RED) i++; if(a[j]==BLUE) j--; swap(a[i],a[j]); } 如何使这个原地算法稳定，我能得到一个为O（n^2）解决问

5热度

1回答

如何进行稳定排序？

如何稳定地对数组进行排序？我想要排序的值可能有很多重复项，我不确定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,

4热度

2回答

如何stable_sort没有复制？

为什么stable_sort需要复制构造函数？（swap应该就够了吧？）或者说，我该如何stable_sort一个范围没有复制任何元素？ #include <algorithm> class Person { Person(Person const &); // Disable copying public: Person() : age(0) { } i

3热度

1回答

是否有可能稳定排序O（n日志n）与恒定辅助空间的数组？

鉴于Ñ元件的阵列，有一个排序算法，排序在至多为O（n log n）的时间（并且可选地，O（n）的时间最好情况）是稳定需要O（1）若干辅助空间铝升排序算法我发现满足只有两个这些标准：冒泡排序满足2和3只合并排序满足1和2只堆排序满足1和3 是否有一个满足所有三个标准的算法？

1热度

2回答

选择排序。如何做选择排序作为稳定的算法？

我有这种选择排序算法的障碍。如何做到稳定这个实现？我认为它不可能/ int selection_sort1 (int ai_numbers[], const int ci_count) { int counter = 0; int i, minIndex, j; for (i = 0; i < ci_count; i++) { minInde

19热度

4回答

为什么heapsort不稳定？

我想知道为什么heapsort不稳定。我已经使用了这个，但没有找到一个好的，直观的解释。我明白稳定排序的重要性 - 它允许我们根据多个关键字进行排序，这可能非常有益（例如，进行多次排序，每次排序都基于不同的关键字，因为每种排序都会保留相对关系元素的顺序，先前的排序可以加起来给出按多个标准排序的元素的最终列表）。但是，为什么不会保存这个呢？感谢您的帮助！

0热度

4回答

如何正确排序这些类型的数组？

我遇到了这种麻烦。我有一个包含这样的值的数组： array = [ {SortTime : 123456, Operation : Assigning}, {SortTime : 4567 , Operation: Assigning}, {SortTime : 123456 , Operation: Assigned} ]; 所以，如果我比较数组[0]和数组[2]我想保持顺序，使我以前的“已

2热度

1回答

稳定的排序会产生显着差异的一个稳定示例（或某个业务用例）

我想知道稳定排序会产生巨大影响的情况。以前的JAVA版本对collections.sor API进行合并排序，对Array.sort进行稳定排序时，使用了quicksort。 Java的当前版本使用Tim Sort，它又是一个稳定的排序。所以现在如果你会看到大多数流行的语言，比如Python，Java，Scala都在使用Tim Sort。我想知道Tim Sort在使用中的稳定排序有多重要。推