是否可以在O(N)中重新排列数组？

Question

如果我有一个N大小的对象数组,并且我有1 ... N范围内的唯一数字数组,是否有任何算法按照数字列表指定的顺序就地重新排列对象数组,并且但是在O(N)时间呢？

上下文:我正在对大小相当大的对象进行快速排序算法,因此在索引上进行交换比在对象本身上进行交换更快,并且只在最后一次传递中移动对象.我只是想知道我是否可以做最后一次传递而不为单独的数组分配内存.

编辑:我不是问如何在O(N)时间内进行排序,而是如何在O(1)空间的O(N)时间内进行后排序重排.很抱歉没有说清楚.

Answer 1

我认为这应该做到:

static <T> void arrange(T[] data, int[] p) {
    boolean[] done = new boolean[p.length];        
    for (int i = 0; i < p.length; i++) {
        if (!done[i]) {
            T t = data[i];
            for (int j = i;;) {
                done[j] = true;

                if (p[j] != i) {
                    data[j] = data[p[j]];
                    j = p[j];
                } else {
                    data[j] = t;
                    break;
                }
            }                
        }
    }
}

注意:这是Java.如果您使用没有垃圾回收的语言执行此操作,请务必删除done.

如果您关心空间,可以使用BitSet done.我假设您可以为每个元素支付额外的一点,因为您似乎愿意使用排列数组,这是该数量的几倍.

该算法复制T n + k次的实例,其中k是置换中的循环数.您可以通过跳过p [i] = i的那些i来将其减少到最佳副本数.

Answer 2

你的意思是你有一个对象数组O [1..N]然后你有一个数组P [1..N]包含数字1..N的排列,最后你想得到一个数组对象的O1使得所有k = 1..N的O1 [k] = O [P [k]]？

例如,如果你的对象是字母A,B,C ......,Y,Z,你的数组P是[26,25,24,..,2,1]是你想要的输出Z,Y,.. .C,B,A？

如果是,我相信你可以使用O(1)额外的内存在线性时间内完成.反转数组的元素是此方案的特例.一般来说,我认为您需要考虑将置换P分解为循环,然后使用它来移动原始数组O []的元素.

如果这就是你要找的东西,我可以详细说明.

编辑:其他人在我睡觉时已经提出了很好的解决方案,所以不需要在这里重复.^ _ ^

编辑:我的O(1)额外的空间确实不完全正确.我只考虑"数据"元素,但事实上你还需要为每个置换元素存储一位,所以如果我们精确,我们需要O(log n)额外位.但大部分时间使用标志位(如JF Sebastian所建议的)都很好,所以在实践中我们可能不需要比现有的更多的东西.

Answer 3

方法是遵循排列的"置换周期",而不是从左到右索引数组.但是,由于你必须从某个地方开始,每次需要一个新的排列周期时,搜索unpermuted元素是从左到右:

// Pseudo-code
N : integer, N > 0 // N is the number of elements
swaps : integer [0..N]
data[N] : array of object
permute[N] : array of integer [-1..N]  denoting permutation (used element is -1)
next_scan_start : integer;

next_scan_start  = 0;

    while (swaps < N )
    {
        // Search for the next index that is not-yet-permtued.  
        for (idx_cycle_search = next_scan_start; 
             idx_cycle_search < N;
             ++ idx_cycle_search)
            if (permute[idx_cycle_search] >= 0)
                break;

        next_scan_start = idx_cycle_search + 1;

        // This is a provable invariant.  In short, number of non-negative
        // elements in permute[] equals (N - swaps)
        assert( idx_cycle_search < N );

        // Completely permute one permutation cycle, 'following the
        // permutation cycle's trail'  This is O(N)
        while (permute[idx_cycle_search] >= 0)
        {
             swap( data[idx_cycle_search], data[permute[idx_cycle_search] )
             swaps ++;

             old_idx = idx_cycle_search;
             idx_cycle_search = permute[idx_cycle_search];
             permute[old_idx] = -1;  
             // Also '= -idx_cycle_search -1' could be used rather than '-1'
             // and would allow reversal of these changes to permute[] array
        }
    }