Как отсортировать ArrayList, чтобы в центре был самый большой элемент?

Question

Необходимо отсортировать ArrayList таким образом, чтобы центр имел самый большой элемент и хвосты по бокам.

Например:

0 2 31 0 4 5 3 0 2 4 1

Я хочу:

0 1 2 3 4 5 4 3 2 1 0

Как этого достичь?Мой метод выглядит следующим образом, я сортирую по возрастанию, но нужно, как я описал выше.

public void generateSpeedFly(int timesec, double Speed){
        Random r = new Random();
        listSpeed = new ArrayList<>(timesec);
        listSpeed.add(0,0.);
        for (int i = 1; i <= timesec-4; i++) {
            listSpeed.add((double) r.nextInt((int) Speed));
        }
        Collections.sort(listSpeed);
        listSpeed.add(listSpeed.size(), Speed);
        minSpeed = listSpeed.get(0);
        maxSpeed = listSpeed.get(listSpeed.size() - 1);
        for (int i = 0; i < listSpeed.size(); i++){
            TotalSpeed += listSpeed.get(i);
        }
        average = TotalSpeed / listSpeed.size();
        TotalSpeed = 0;
    }

Answer 1

// init
Integer[] result = new Integer[arr.length];
Integer[] arr = {0, 2, 3, 1, 0, 4, 5, 3, 0, 2, 4, 1};
List<Integer> listSorted = Arrays.asList(arr);

// simple sort, O(N*log(N))
Collections.sort(listSorted);

// fill result array O(n) 
int size = listSorted.size();
for(int i = 0; i < size / 2 ; i++) {
    result[size / 2 - i ] = listSorted.get(size - i * 2 - 1);
    if(size / 2 + i + 1 < size) {
        result[size / 2 + i + 1] = listSorted.get(size - i * 2 - 2);
    }
}

Результат {0 1 2 3 4 5 4 3 2 1 0, O (N * log (N))

Answer 2

Предлагаю использовать временный массив.Требуется O(n) памяти, но она работает.

public static void sort(int[] arr) {
    int[] tmp = Arrays.stream(arr).sorted().toArray();

    for (int i = 0, l = 0, r = arr.length - 1; i < tmp.length; i++) {
        if (i % 2 == 0)
            arr[l++] = tmp[i];
        else
            arr[r--] = tmp[i];
    }
}

Подумав некоторое время, я нашел подходящее решение без использования O(n) памяти, но немного медленнее:

public static void sort(int[] arr) {
    Arrays.sort(arr);

    for (int l = 1, r = arr.length - 1; l < r; l++, r--) {
        // shift 1 position left
        int tmp = arr[l];
        System.arraycopy(arr, l + 1, arr, l, r - l);
        arr[r] = tmp;
    }
}

Тест: Оба решения дают одинаковый результат:

Вход: [ 0, 2, 3, 1, 0, 4, 5, 3, 0, 2, 4, 1 ]

Выход: [ 0, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0 ]

Answer 3

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

Если мы возьмем ваш пример:

0 2 3 1 0 4 5 3 0 2 4 1

Две части будут:

0 2 3 1 0 4
53 0 2 4 1

Сортируем первый по возрастанию, а второй по убыванию:

0 0 1 2 3 4
5 4 3 2 1 0

И мы наконец получаем:

0 0 1 2 3 4 5 4 3 2 1 0

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

1. Мы сортируем весь массив
2. Возьмем каждый элемент по очереди и поочередно выдвигаем их вперед и назад на выходе
3. Разделите вывод на две части: левую и правую
4. Соберите две части в обратном порядке

Снова взяв пример:

00 0 1 1 2 2 3 3 4 4 5

Шаг 1:

вход: 0 1 1 2 2 3 3 4 4 5
выход: 00

Шаг 2:

вход: 1 2 2 3 3 4 4 5
выход: 0 0 0 1

Шаг 3:

ввод: 2 3 3 4 4 5
вывод: 1 0 0 0 1 2

Шаг 4:

вход: 3 4 4 5
выход: 2 1 0 0 0 1 2 3

В итоге получаем:

5 4 3 2 1 0 00 1 2 3 4

На данном этапе это прямо противоположно тому, что мы хотим.Итак, мы разделим:

Слева: 5 4 3 2 1 0
Справа: 0 0 1 2 3 4

И, наконец, мы получим:

0 0 1 2 3 4 5 4 3 2 1 0

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

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