不同的排序令 - 分而治之？

Question

我正试图以不同的方式重新安排对象列表.在这里,我将使用整数,但可以在此列表中的任何内容.

以下示例代码按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

Answer 1

让我看看我是否理解这个问题.让我们以更多项目为例:

这是你想要的订单？

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  

更直观明显; 如果"在中间"的东西总是优先于"极端"的东西,那么极端应该是最后的,而不是第一个.