Как отсортировать большие числа, хранящиеся в строковом массиве?

Question

Мне нужно отсортировать большие числа, хранящиеся в виде строки в строковом массиве, но мой алгоритм и метод сортировки массива .net не работают.

Я пытался преобразовать число в long или ulong, но это исключение переполнения.

Вот код, который я пробовал:

string[] unsorted = { "1","2","100","12303479849857341718340192371",
                      "3084193741082937","3084193741082938","111","200" };

for (int index = 0; index < unsorted.Length - 1; index++)
{
    for (int count = 0; count < unsorted.Length - index - 1; count++)
    {
        if (string.Compare(unsorted[count], unsorted[count + 1]) == 1)
        {
            string temp = unsorted[count];
            unsorted[count] = unsorted[count + 1];
            unsorted[count + 1] = temp;
        }
    }
}

Также используется следующий метод:

 Array.Sort(unsorted);

Массив должен быть правильно отсортирован.

Answer 1

Вы можете использовать BigInteger.Parse и использовать Linq's OrderBy. Например:

var sorted = unsorted.Select(BigInteger.Parse).OrderBy(e => e).ToArray();

Если вам нужно вернуть его в виде строки:

var sorted = unsorted.Select(BigInteger.Parse).OrderBy(e => e).Select(e => e.ToString()).ToArray();

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

• Pro: читаемый
• Против: Вероятно, не самое эффективное решение.

Answer 2

Попробуйте следующее:

string[] unsorted = { "1","2","100","12303479849857341718340192371",
                      "3084193741082937","3084193741082938","111","200" };

var groups = unsorted.OrderBy(x => x.Length).GroupBy(x => x.Length).ToArray();
List<string> results = new List<string>();
foreach (var group in groups)
{
    string[] numbers = group.ToArray();
    for(int i = 0; i < numbers.Count() - 1; i++)
    {
        for(int j = i + 1; j < numbers.Count(); j++)
        {
            if(numbers[i].CompareTo(numbers[j]) == 1)
            {
                string temp = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = temp;
            }
        }
    }
    results.AddRange(numbers);
}

Answer 3

У вас нет массива чисел, у вас есть массив строк. Таким образом, они сортируются по алфавиту.

Один из вариантов - использовать класс BigInteger для хранения их в виде чисел:

BigInteger[] unsorted = { 
    BigInteger.Parse("1"),
    BigInteger.Parse("2"), 
    BigInteger.Parse("100"),
    BigInteger.Parse("12303479849857341718340192371"),
    BigInteger.Parse("3084193741082937"),
    BigInteger.Parse("3084193741082938"),
    BigInteger.Parse("111"),
    BigInteger.Parse("200")
};

В противном случае, если вы хотите сохранить их в виде строк, вы можете добавить их в нули с нулями, чтобы согласовать длины, чтобы сработала буквенно-цифровая сортировка:

string[] unsorted = { 
    "00000000000000000000000000001",
    "00000000000000000000000000002",
    "00000000000000000000000000100",
    "12303479849857341718340192371",
    "00000000000003084193741082937",
    "00000000000003084193741082938",
    "00000000000000000000000000111",
    "00000000000000000000000000200"
};

Если вы выберете первое, просто измените типы в вашем блоке if, чтобы они также были BigInteger.

Answer 4

Опираясь на ответ @ jdweng , но еще больше сокращая его, устраняя «ручную» сортировку пузырьков:

string[] result =
    unsorted.OrderBy(x => x.Length)
    .GroupBy(x => x.Length)
    .SelectMany(x => x.OrderBy(y => y))
    .ToArray();

Или другой вариант той же темы:

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

...

string[] result =
    unsorted.OrderBy(x => x, Comparer<string>.Create((a, b) => a.Length == b.Length ? a.CompareTo(b) : a.Length - b.Length))
    .GroupBy(x => x.Length)
    .SelectMany(x => x)
    .ToArray();

(Как отмечается в комментарии @ fester под ответом @ jdweng, этот подход не будет надежно работать, если некоторые строки представляют собой числа с предопределенными нулями, например, например, " 00123 ".)

Answer 5

Еще один вариант:

    static void Main(string[] args)
    {
        List<string> unsorted = new List<string>(new string[] {"1","2","100","12303479849857341718340192371",
                        "3084193741082938","3084193741082937", "111","200" });

        unsorted.Sort((x, y) => (x.Length != y.Length ? x.Length.CompareTo(y.Length) : x.CompareTo(y)));

        foreach(string number in unsorted)
        {
            Console.WriteLine(number);
        }
        Console.Write("Press Enter to quit");
        Console.ReadLine();
    }

Answer 6

Система должна быть похожа на следующую. Вы можете передать значения в массиве в массив, а затем проанализировать их все в BigInteger с помощью цикла for. И, наконец, вы можете отсортировать список:

BigInteger[] unsorted; 
var bigIntegers = new List<System.Numerics.BigInteger>();

  for (int index = 0; index < unsorted.Length - 1; index++)
  {
  bigIntegers[i] = BigInteger.Parse[i]
  }

bigIntegers.sort();

Answer 7

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

var result = unsorted.Select(e => decimal.Parse(e)).OrderBy(e => e);

Answer 8

Если мы хотим отсортировать очень большие числа, хранящиеся в виде строк, без изменения строки на BigInteger, лучше сначала отсортировать их по длине, а затем по лексикографическому порядку. Мы можем увидеть пример кода ниже:

using System;
using System.Linq;
public class Test
{
   public static void Main()
   {
     string[] unsorted = { "1","2", "100","12303479849857341718340192371",
                       "3084193741082937","3084193741082938","111","200" };

      unsorted.OrderBy(s => s.Length).ThenBy(s => s);
      Console.WriteLine("Sorted numbers are:");
      foreach (var x in unsorted) {
           Console.WriteLine(x);
      }
   }
}

Примечание. Чтобы использовать функции OrderBy и ThenBy, мы должны включить в нашу программу using System.Linq.