#java #arrays #algorithm #sorting #merge
Вопрос:
В настоящее время у меня есть алгоритм сортировки слиянием с использованием Java, но я пытаюсь изменить его, чтобы отсортировать вторую половину в порядке убывания. Он также должен иметь временную сложность O(n).
Например:
Ввод: 34, 12, 7, 43, 55, 97, 41, 28, 2, 62
Выход: 2, 7, 12, 28, 34, 97, 62, 55, 43, 41
Комментарии:
1. Отсортируйте массив, а затем переверните вторую половину. Реверсирование массива равно O(n). Начальная сортировка-O(nlogn). Таким образом, выполнение обратного шага после завершения сортировки не влияет на временную сложность и мало влияет на время выполнения.
2. (Это должно быть (на одну итерацию) быстрее, чтобы заказать половинки по отдельности. И вы могли бы избежать обратного хода.)
Ответ №1:
В java 1.8 мы можем сделать это так. мы можем оптимизировать его дальше. 🙂
public static void main(String[] args) { Streamlt;Integergt; streamObj = Stream.of(34, 12, 7, 43, 55, 97, 41, 28, 2, 62); Listlt;Integergt; list1 = streamObj.collect(Collectors.toList()); int middleIndex = list1.size()/2; System.out.println(middleIndex); Listlt;Integergt; firstHalf = list1.subList(0,middleIndex).stream().sorted().collect(Collectors.toList()); Listlt;Integergt; secondHalf = list1.subList(middleIndex,list1.size()).stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList()); System.out.println("firstHalf" firstHalf "nsecondHalf" secondHalf); firstHalf.addAll(secondHalf); System.out.println(firstHalf); }