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

Question

考虑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）解有人能提出O（n）解吗？

Answer 1

如果允许我们使用额外的内存，只需进行两次扫描：

第一道：

count = 0
foreach a[i] == RED
    b[count ++] = a[i]
    i ++

第二道：

foreach a[i] == BLUE
    b[count ++] = a[i]
    i ++

最后复制a = b

总的来说，时间复杂度将是O(3n) = O(n)。

Answer 2

O（n2）中的一种方法：

a） 将每个元素的索引附加到元素本身。

｛"RED1"、"RED2"、"BLUE3"、"BLUE4"｝

b） 交换函数应考虑最后一个字符索引指示符，当您尝试交换两个RED或两个BLUE时。

例如：当你试图交换两个RED时->只有当indexOfFirst（RED）>indexOfSecond（RED

BLUE也是如此。

注意：您需要添加一些额外的逻辑来查找它是蓝色还是红色。

Answer 3

计数排序

如果你只有蓝色和红色你在数蓝色元素和红色元素

[b1 r1 r2 b2 b3 r3 r4 b4 r5]

在for循环中，你可以计算你的元素你有blue: 4 red: 5

那么您就知道结果表是[ r r r r r b b b b]你可以知道索引范围，其中是红色元素和蓝色元素（最后一个红色元素是{red_count}-1，最后一个蓝色元素是｛red_count｝+{blue_count}-1）将这些值保存到redIndex和blueIndex

制作第二个表，在for循环中从末尾搜索元素，最后一个是r5，它是红色的，那么他的索引应该是4，然后递减redIndex

[b1 r1 r2 b2 b3 r3 r4 b4 __] blueIndex:8 
[__ __ __ __ r5 __ __ __ __] redIndex:3
[b1 r1 r2 b2 b3 r3 r4 __ __] blueIndex:7 
[__ __ __ __ r5 __ __ __ b4] redIndex:3
[b1 r1 r2 b2 b3 r3 __ __ __] blueIndex:7 
[__ __ __ r4 r5 __ __ __ b4] redIndex:2
.....

排序项目O（2n）的更快方法，但当各种数据