algorithm - 如何将以下不稳定的排序算法转换为稳定的？

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

如果允许我们使用额外的内存，只需进行 2 遍扫描:

第一关:

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)。