不同的排序顺序——分而治之

本文关键字：分而治之 顺序 排序 | 更新日期: 2023-09-27 18:15:17

我正在尝试以不同的方式重新排列对象列表。这里我将使用整数，但可以是列表中的任何值。

下面的示例代码将1,2,3,4,5,6,7,8按以下顺序排序:1,8,2,7,3,6,4,5

首先。最后的第二。倒数第二等等。它可能有点笨拙，但它工作。

现在我要做的是以另一种顺序输出列表，这样它就会一直分成两部分。我认为这可能被称为分而治之，但在尝试/看了一些递归排序代码等之后。我不太清楚如何在这里实现它。

我希望这些数字能这样排序。

1,8,4,2,6,3,5,7

第一，最后，中间，前一半一半，后一半一半等

所以换句话说，我要做的是把一组数字分成两半…然后把每一半分成两半。等等:

1 2 3 4 5 6 7 8
1                      (first item)
              8        (last item)
      4                (mid item)
  2                     (mid of first half) 
          6              (mid of second half)
    3                    (mid of 1st chunk)
        5                (mid of 2nd chunk)
           7             (mid of 3rd chunk)

如果有人能告诉我怎么做，用这个简单的例子，那就太好了。

 static void Main(string[] args)
    {
        List<int> numberlist = new List<int>();
        numberlist.Add(1);
        numberlist.Add(2);
        numberlist.Add(3);
        numberlist.Add(4);
        numberlist.Add(5);
        numberlist.Add(6);
        numberlist.Add(7);
        numberlist.Add(8);
        int rev = numberlist.Count-1;
        int fwd = 0;
        // order 1,8,2,7,3,6,4,5
        for (int re = 0; re < numberlist.Count; re++)
        {
            if (re % 2 == 0)
            {
                Console.WriteLine(numberlist[fwd]);
                fwd++;                       
            }
            else
            {
                Console.WriteLine(numberlist[rev]);
                rev--;
            }
        }
        Console.ReadLine();
    }

更多的示例范围和输出，从左到右，从上到下:

1 2 3 4 5 6 7
1           7
      4
  2     5
    3     6
1 2 3 4 5 6 7 8 9 10 11 12
1                       12
          6 
    3           9 
  2   4     7     10
        5     8      11

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1                                   16
              8 
      4                 12
  2       6       10          14
    3   5   7   9    11    13    15

不同的排序顺序——分而治之

让我看看我是否理解这个问题。让我们使用更多条目的例子:

这是你想要的订单吗?
ABCDEFGHIJKLMNOPQ
A               Q  
        I
    E       M
  C   G   K   O
 B D F H J L N P

这看起来很简单。创建一个名为"Interval"的数据结构，它有两个字段:最大下限和最小上限。也就是说，在区间以下的最大的元素和在区间以上的最小的元素是什么。算法是这样的:

Input: the size of the array.
Yield the first item -- if there is one
Yield the last item -- if it is different from the first item.
Make a queue of intervals.
Enqueue the interval (0, array.Length - 1) 
While the queue is not empty:
    Dequeue the queue to obtain the current item.
    Is the interval empty? If so, skip this interval
    Otherwise, the interval has a GLB, a LUB, and a value in the middle.
    Yield the middle of the interval
    Enqueue the interval (bottom, middle)
    Enqueue the interval (middle, top)

让我们看看上面的例子。我们有阵列ABCDEFGHIJKLMNOPQ。

Yield A
Yield Q
Enqueue A-Q. The queue is now A-Q
Is the queue empty? No.
Dequeue the queue. It is now empty.
current is A-Q
Is the current interval empty? no.
The middle is I.
Yield I.
Enqueue A-I. The queue is now A-I.
Enqueue I-Q. The queue is now A-I, I-Q.
Is the queue empty? No.
Dequeue the queue. It is now I-Q.
current is A-I.
Is the current interval empty? No.
The middle is E.
Yield E.
Enqueue A-E. The queue is now I-Q, A-E.
Enqueue E-I. The queue is now I-Q, A-E, E-I
Is the queue empty? No.
Dequeue. The queue is now A-E, E-I
current is I-Q
The middle is M
Yield M.
Enqueue I-M
Enqueue M-Q.  The queue is now A-E, E-I, I-M, M-Q
OK, let's start skipping some steps here. The state of the queue and the yields are:
Yield C
E-I, I-M, M-Q, A-C, C-E
Yield G
I-M, M-Q, A-C, C-E, E-G, G-I
Yield K
M-Q, A-C, C-E, E-G, G-I, I-K, K-M
yield O
A-C, C-E, E-G, G-I, I-K, K-M, M-O, O-Q
yield B
C-E, E-G, G-I, I-K, K-M, M-O, O-Q, A-B, B-C
OK, skip more steps...
Yield D, F, H, J, L, N, P
Queue is now A-B, B-C, C-D, D-E, ... P-Q
Every interval is now empty, so we skip all of htem and we are done.

有意义吗?

这里的技巧是注意您想要的顺序是宽度优先访问树。你只需要能够"看穿"数组到你想要遍历的树结构。

顺便说一下，顺序似乎有点奇怪。大多数情况下，排序似乎是"将范围分成两部分，先产生每个范围的中间部分"。那么为什么两个极端是第一个，而不是最后一个呢?我会找到排序:

ABCDEFGHIJKLMNOPQ
        I
    E       M
  C   G   K   O
 B D F H J L N P
A               Q

更直观;如果"中间"的事情总是优先于"极端"的事情，那么极端应该放在最后，而不是前面。

我可以演示一个类似的选择;结果与您的顺序略有不同。

取0 ~ 7，用二进制表示:000 001 010 011 100 101 110 111 .

现在，反转它们:000 100 010 110 001 101 011 111 .

在十进制中，这得到0 4 2 6 1 3 5 7。从第一个元素开始，然后是其余元素的一半，然后是1/4和3/4，最后是所有奇数元素。

显然这个过程只适用于2的精确幂

相关文章：