如何排序整数数组为负数，零，正一部分不改变相对位置？ [英] How to sort an integer array into negative, zero, positive part without changing relative position?

问题描述

给出一个O（n）的算法，作为输入数组S，然后把s转换三套：底片，零和阳性。将展示如何在地方，那就是实现这一点，不分配新的内存。而且你必须保持数的相对顺序。 例如： {-1，4,0，-2，1,2} ==> {-1，-2，0，4，1，2}

我不知道是否没有这样的解决方案退出。我能想出的最好的解决方案是：

解决方法1：使用一个额外的整型数组，然后遍历整个数组拿到底片，然后为0，那么阳性

。

解决方案2：不要让数量的相对顺序。然后循环数组两次：

 模板＆LT; typename的类型＆GT;
无效Partion（类型*数组，诠释开始，诠释年底，V型，INT和放大器; L，INT和放大器; R）
{
    L =开始;
    对于（INT I =开始;！I =结束; ++ I）
    {
        如果（阵列[1]  - ; 5）
            掉期（数组[我]，数组并[+]）;
    }
    R =升;
    对于（诠释J = 1;！J =结束; ++ j）条
    {
        如果（阵列[J] == V）
            掉期（阵列[J]，数组[R ++]）;
    }
}
 

解决方案

这是荷兰国旗问题研究了Edsger Dijkstra算法。这是在很有意思无稳定解决这个问题的了解，运行在O（n）时间及O（1）空间（或者至少，在我最后一次检查文献中，没有已知的解决方案问题的存在）。

Give an O(n) algorithm which takes as input an array S, then divides S into three sets: negatives, zeros, and positives. Show how to implement this in place, that is, without allocating new memory. And you have to keep the number's relative sequence. for example: {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

I am not sure whether or not such an solution exits. The best solutions I can think out are:

Solution 1: Using an extra integer array, then traverse the whole array to get negatives, then 0s, then positives.

Solution 2: Do not keep number's relative sequence. Then loop the array two times:

    template <typename Type>  
void Partion(Type *array, int begin, int end, Type v, int &l, int &r) 
{  
    l = begin;  
    for (int i=begin; i!=end; ++i)  
    {  
        if (array[i] < v)  
            swap(array[i], array[l++]);  
    }  
    r = l;  
    for (int j=l; j!=end; ++j)  
    {  
        if (array[j] == v)  
            swap(array[j], array[r++]);  
    }  
} 

解决方案

This is an instance of the Dutch national flag problem studied by Edsger Dijkstra. It's interesting in that no stable solution to this problem is known that runs in O(n) time and O(1) space (or at least, the last time I checked the literature, no known solution to the problem exists).

这篇关于如何排序整数数组为负数，零，正一部分不改变相对位置？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！