Сортировать список BigDecimals разбираемого из строк, в то время как maintainig порядка чисел, где значения равны

Question

Я прочитал в списке строк, которые представляют собой число в различных форматах

Я разбор этих чисел BigDecimals и сортировка их.

Затем я распечатываю номера в исходном формате.

Проблема в том, что мне необходимо поддерживать порядок чисел, которые не совпадают, что не происходит в моем текущем коде.

import java.math.BigDecimal; 
import java.util.*; 
class Solution{ 

    public static void main(String []args){ 
     //Input 
     Scanner sc= new Scanner(System.in); 
     int n=sc.nextInt(); 
     String []s=new String[n+2]; 
     for(int i=0;i<n;i++){ 
      s[i]=sc.next(); 
     } 
     sc.close(); for (int i = 0; i < n -1; i++) { 
      for (int k = (i + 1); k < n; k++) { 
       if (new BigDecimal(s[i]).compareTo(new BigDecimal(s[k])) < 0) { 
        String tempValue = s[i]; 
        s[i] = s[k]; 
        s[k] = tempValue; 
       } 
      } 
     } 

Входной

9 
-100 
50 
0 
56.6 
90 
0.12 
.12 
02.34 
000.000 

Выход

90 
56.6 
50 
02.34 
.12 
0.12 (Wrong order here) 
0 
000.000 
-100 

Ожидаемый результат

90 
56.6 
50 
02.34 
0.12 
.12 
0 
000.000 
-100 

Решение

for (int i = 0; i < n; i++) { 
     for (int j = 1; j < (n - i); j++) { 
     String temp=""; 
     if(new BigDecimal(s[j-1]).compareTo(new BigDecimal(s[j])) < 0) { 
      temp = s[j-1]; 
      s[j-1] = s[j]; 
      s[j] = temp; 
     } 
     } 

Answer 1

Проблема в том, что алгоритм сортировки выбора, который вы используете, нестабилен. То есть, он не гарантирует, что элементы с равным значением сохраняют свой относительный порядок в списке. Рассмотрим этот простой список предметов: [5.0, 5, 3, 6].

Если вы хотите отсортировать это в порядке убывания, то после первого прохождения выбора сортировки у вас будет: [6, 5, 3, 5.0].5.0 был заменен на 6. Предметы 5.0 и 5 теперь не в порядке, и они останутся такими.

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

Answer 2

Я бы предложил другой подход, используя лучшие абстракции. Вы можете использовать Map<BigDecimal, String>. Карта Значение: строка, введенная пользователем. Карта ключ: объект BigDecimal, который вы получаете, анализируя эту строку.

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

Что-то вроде:

Map<BigDecimal, String> stringsByValue = new HashMap<>(); 
stringsByValue.put(... 

for (BigDecimal value : Collections.sort(stringsByValue.keySet())) { 
    String originalInput = stringsByValue.get(value); ... 

Возможно, что требует некоторой настройки, чтобы сохранить первоначальный заказ на равных значений.

Answer 3

Применение com.google.gson.internal.LinkedTreeMap

Карта сопоставимых ключей к значениям. В отличие от TreeMap, этот класс использует порядок вставки для порядка итерации. Порядок сравнения используется только как оптимизация для эффективной вставки и удаления.

В java есть LinkedHashMap.

Хеш таблица и реализация связанного списка интерфейса Map, с предсказуемым порядком итерации ...

Но это не упорядочено.