В С#, как упорядочить элементы в списке, где "наибольшие" значения находятся в середине списка

Ответ 1

Соответствующая структура данных - это LinkedList, потому что она позволяет вам эффективно добавлять в любой конец:

        LinkedList<int> result = new LinkedList<int>();

        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        Array.Sort(array);

        bool odd = true;

        foreach (var x in array)
        {
            if (odd)
                result.AddLast(x);
            else
                result.AddFirst(x);
            odd = !odd;
        }

        foreach (int item in result)
            Console.Write("{0} ", item);

Никаких дополнительных шагов копирования, никаких шагов реверсирования,... только небольшие накладные расходы на node для хранения.

Ответ 2

Версия Iterator С#

(Очень простой код, удовлетворяющий всем условиям.)

Одна функция, чтобы управлять ими всеми! Не использует промежуточную коллекцию хранилищ (см. yield). Заказывает большие числа либо в середине, либо в стороны в зависимости от аргумента. Он реализован как С# -тератор

// Pass forward sorted array for large middle numbers,
//  or reverse sorted array for large side numbers.
//
public static IEnumerable<long> CurveOrder(long[] nums) {

    if (nums == null || nums.Length == 0)
        yield break; // Nothing to do. 

    // Move forward every two.
    for (int i = 0;  i < nums.Length;  i+=2)
        yield return nums[i];

    // Move backward every other two. Note: Length%2 makes sure we're on the correct offset.
    for (int i = nums.Length-1 - nums.Length%2;  i >= 0;  i-=2)
        yield return nums[i];
}

Пример использования

Например, с массивом long[] nums = { 1,2,3,4,5,6,7,8,9,10,11 };

Начните с прямого порядка сортировки, чтобы поднять высокие числа в середину.

Array.Sort(nums); //forward sort
// Array argument will be:  { 1,2,3,4,5,6,7,8,9,10,11 };
long[] arrLargeMiddle = CurveOrder(nums).ToArray();

Производит: 1 3 5 7 9 11 10 8 6 4 2

Или, Начните с обратного порядка сортировки, чтобы нажимать большие числа на стороны.

Array.Reverse(nums); //reverse sort
// Array argument will be:  { 11,10,9,8,7,6,5,4,3,2,1 };
long[] arrLargeSides = CurveOrder(nums).ToArray();

Производит: 11 9 7 5 3 1 2 4 6 8 10

Значительные пространства имен:

using System;
using System.Collections.Generic;
using System.Linq;

Примечание. Итератор оставляет решение до вызывающего абонента о том, следует ли использовать промежуточное хранилище. Вызывающий может просто генерировать цикл foreach по результатам.

Вариант метода расширения

Необязательно изменить заголовок статического метода, чтобы использовать этот модификатор public static IEnumerable<long> CurveOrder(this long[] nums) { и поместить его в статический класс в вашем пространстве имен;
Затем вызовите метод заказа непосредственно на любом длинном экземпляре массива [] так:

Array.Reverse(nums); //reverse sort
// Array argument will be:  { 11,10,9,8,7,6,5,4,3,2,1 };
long[] arrLargeSides = nums.CurveOrder().ToArray();

Просто какой-то (незаменимый) синтаксический сахар, чтобы немного смешать вещи для удовольствия. Это можно применить к любым ответам на ваш вопрос, которые принимают аргумент массива.

Ответ 3

Что-то вроде этого?

public IEnumerable<int> SortToMiddle(IEnumerable<int> input)
{
    var sorted = new List<int>(input);
    sorted.Sort();
    var firstHalf = new List<int>();
    var secondHalf = new List<int>();

    var sendToFirst = true;
    foreach (var current in sorted)
    {
        if (sendToFirst)
        {
            firstHalf.Add(current);
        }
        else
        {
            secondHalf.Add(current);
        }
        sendToFirst = !sendToFirst;
    }
    //to get the highest values on the outside just reverse 
    //the first list instead of the second
    secondHalf.Reverse();
    return firstHalf.Concat(secondHalf);
}

Для вашего конкретного (общего) случая (при условии уникальных ключей):

public static IEnumerable<T> SortToMiddle<T, TU>(IEnumerable<T> input, Func<T, TU> getSortKey)
{
    var sorted = new List<TU>(input.Select(getSortKey));
    sorted.Sort();
    var firstHalf = new List<TU>();
    var secondHalf = new List<TU>();

    var sendToFirst = true;
    foreach (var current in sorted)
    {
        if (sendToFirst)
        {
            firstHalf.Add(current);
        }
        else
        {
            secondHalf.Add(current);
        }
        sendToFirst = !sendToFirst;
    }
    //to get the highest values on the outside just reverse 
    //the first list instead of the second
    secondHalf.Reverse();
    sorted = new List<TU>(firstHalf.Concat(secondHalf));

    //This assumes the sort keys are unique - if not, the implementation 
    //needs to use a SortedList<TU, T>
    return sorted.Select(s => input.First(t => s.Equals(getSortKey(t))));

}

И принимая не уникальные ключи:

public static IEnumerable<T> SortToMiddle<T, TU>(IEnumerable<T> input, Func<T, TU> getSortKey)
{
    var sendToFirst = true;
    var sorted = new SortedList<TU, T>(input.ToDictionary(getSortKey, t => t));
    var firstHalf = new SortedList<TU, T>();
    var secondHalf = new SortedList<TU, T>();

    foreach (var current in sorted)
    {
        if (sendToFirst)
        {
            firstHalf.Add(current.Key, current.Value);
        }
        else
        {
            secondHalf.Add(current.Key, current.Value);
        }
        sendToFirst = !sendToFirst;
    }
    //to get the highest values on the outside just reverse 
    //the first list instead of the second
    secondHalf.Reverse();
    return(firstHalf.Concat(secondHalf)).Select(kvp => kvp.Value);
}

Ответ 4

Я мог бы пойти на что-то вроде этого

static T[] SortFromMiddleOut<T, U>(IList<T> list, Func<T, U> orderSelector, bool largestInside) where U : IComparable<U>
{
    T[] sortedArray = new T[list.Count];

    bool add = false;
    int index = (list.Count / 2);
    int iterations = 0;

    IOrderedEnumerable<T> orderedList;
    if (largestInside)
        orderedList = list.OrderByDescending(orderSelector);
    else
        orderedList = list.OrderBy(orderSelector);

    foreach (T item in orderedList)
    {
        sortedArray[index] = item;
        if (add)
            index += ++iterations;
        else
            index -= ++iterations;

        add = !add;
    }

    return sortedArray;
}

Обратные вызовы:

int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int[] sortedArray = SortFromMiddleOut(array, i => i, false);
foreach (int item in sortedArray)
    Console.Write("{0} ", item);

Console.Write("\n");

sortedArray = SortFromMiddleOut(array, i => i, true);
foreach (int item in sortedArray)
    Console.Write("{0} ", item);

Поскольку он является общим, он может быть списком Foo, и селектор заказов может быть f => f.Name или все, что вы хотите бросить на него.

Ответ 5

Самое быстрое (но не самое ясное) решение, вероятно, просто вычислить новый индекс для каждого элемента:

        Array.Sort(array);

        int length = array.Length;
        int middle = length / 2;
        int[] result2 = new int[length];

        for (int i = 0; i < array.Length; i++)
        {
            result2[middle + (1 - 2 * (i % 2)) * ((i + 1) / 2)] = array[i];
        }

Ответ 6

Простейшее решение - закажите список по убыванию, создайте два новых списка, в первую очередь, каждый элемент с нечетным индексом, в другой каждый даже индексированный элемент. Переверните первый список, затем добавьте второй к первому.

Ответ 7

Хорошо, я не собираюсь подвергать сомнению ваше здравомыслие здесь, так как я уверен, что вы не зададите вопрос, если не было веской причины: -)

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

sortedlist = list.sort (descending)
biginmiddle = new list()
state = append
foreach item in sortedlist:
    if state == append:
        biginmiddle.append (item)
        state = prepend
    else:
        biginmiddle.insert (0, item)
        state = append

Это даст вам список, где большие предметы находятся посередине. Другие предметы будут раздуваться из середины (в чередующихся направлениях) по мере необходимости:

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

Чтобы получить список, в котором большие элементы находятся на концах, просто замените начальную сортировку на восходящую.

Сортированные и окончательные списки могут быть просто указателями на фактические элементы (поскольку вы заявляете, что они не простые целые числа) - это минимизирует как дополнительные требования к хранению, так и копирование.

Ответ 8

Может быть, это не лучшее решение, но здесь отличный способ...

Пусть Product[] parr будет вашим массивом.

Отказ от ответственности Это java, мой С# ржавый. Неподтвержденный код, но вы получаете идею.

int plen = parr.length
int [] indices = new int[plen];
for(int i = 0; i < (plen/2); i ++)
    indices[i] = 2*i + 1;   // Line1
for(int i = (plen/2); i < plen; i++)
    indices[i] = 2*(plen-i); // Line2

for(int i = 0; i < plen; i++)
{
    if(i != indices[i])
        swap(parr[i], parr[indices[i]]);
}

Второй случай, Что-то вроде этого?

int plen = parr.length
int [] indices = new int[plen];
    for(int i = 0; i <= (plen/2); i ++)
       indices[i] = (plen^1) - 2*i;
    for(int i = 0; i < (plen/2); i++)
       indices[i+(plen/2)+1] = 2*i + 1;


for(int i = 0; i < plen; i++)
{
    if(i != indices[i])
        swap(parr[i], parr[indices[i]]);
}