Различные порядки сортировки - разделяй и властвуй?

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-я половина на полпути и т. Д.

Другими словами, я пытаюсь разделить набор чисел пополам... Затем для каждой половины по очереди делим их пополам.И так далее:

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  

более интуитивно очевидно; если вещи «посередине» всегда имеют приоритет над вещами «на крайностях», то крайности должны идти последними, а не первыми.

Answer 2

Я могу продемонстрировать подобный выбор;это приводит к немного другому порядку, чем ваш.

Возьмите числа от 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. Итак, вы начинаете с первого элемента, затем на полпути через остальные элементы, затем четверть и три четверти, а затем, наконец, все нечетные номераelements.

Очевидно, что эта процедура работает только для точных степеней двух.