Как отсортировать список на лету как можно быстрее

Question

Я ищу способ сортировки списка как можно быстрее, так как это произойдет триллионы раз.

l oop генерирует десятичные значения, а затем строка будет помещена в "sortedLIST". ». Здесь я хочу, чтобы самое низкое десятичное значение было вверху списка, а самое высокое десятичное значение внизу списка.

В этом сценарии. Как мы можем сделать это как можно быстрее?

Спасибо!

void sortfunction()
{
    //The decimal values will actually dynamically be calculated in this loop in reality
    List<String> sortedLIST = new List<String>();
    Random random = new Random(); 
    double rand = 0; 
    double num = 0; 
    String str = "";

    for (int i = 0; i < 500000; i++)
    {
        rand = random.Next(0, 99);
        num = rand / 100;
        str = num + "|hello1|hello2|hello3";

        //Is it possible to sort the values on the FLY here directly somehow with the LOWEST at the top. 
        //So insert them at the correct index right away somehow or if there is faster approach?
        sortedLIST.Add(str);
    }
}

Answer 1

Как я уже упоминал в комментариях, вам не нужно добавлять префикс строки к каждому элементу, вы можете просто добавить его, когда что-то вычеркните из списка. Это означает, что вы можете сохранить список как список int, а не string.

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

Вот код:

void sortfunction()
{
    const int numberOfItems = 500000;

    var sortedList = new List<double>(numberOfItems);
    Random random = new Random(); 

    for (int i = 0; i < numberOfItems; i++)
    {
        var rand = random.Next(0, 99);
        var num = rand / 100d;

        sortedList.Add(num);
    }

    sortedList.Sort();
}

Answer 2

Использовать рекурсию с алгоритмом сортировки слиянием:

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

namespace Merge_sort
{    
    class Program
    {
        static void Main(string[] args)
        {
            List<int> unsorted = new List<int>();
            List<int> sorted;

            Random random = new Random();

            Console.WriteLine("Original array elements:" );
            for(int i = 0; i< 10;i++){
                unsorted.Add(random.Next(0,100));
                Console.Write(unsorted[i]+" ");
            }
            Console.WriteLine();

            sorted = MergeSort(unsorted);

            Console.WriteLine("Sorted array elements: ");
            foreach (int x in sorted)
            {
                Console.Write(x+" ");
            }
            Console.Write("\n");
        }


        private static List<int> MergeSort(List<int> unsorted)
        {
            if (unsorted.Count <= 1)
                return unsorted;

            List<int> left = new List<int>();
            List<int> right = new List<int>();

            int middle = unsorted.Count / 2;
            for (int i = 0; i < middle;i++)  //Dividing the unsorted list
            {
                left.Add(unsorted[i]);
            }
            for (int i = middle; i < unsorted.Count; i++)
            {
                right.Add(unsorted[i]);
            }

            left = MergeSort(left);
            right = MergeSort(right);
            return Merge(left, right);
        }

        private static List<int> Merge(List<int> left, List<int> right)
        {
            List<int> result = new List<int>();

            while(left.Count > 0 || right.Count>0)
            {
                if (left.Count > 0 && right.Count > 0)
                {
                    if (left.First() <= right.First())  //Comparing First two elements to see which is smaller
                    {
                        result.Add(left.First());
                        left.Remove(left.First());      //Rest of the list minus the first element
                    }
                    else
                    {
                        result.Add(right.First());
                        right.Remove(right.First());
                    }
                }
                else if(left.Count>0)
                {
                    result.Add(left.First());
                    left.Remove(left.First());
                }
                else if (right.Count > 0)
                {
                    result.Add(right.First());

                    right.Remove(right.First());    
                }    
            }
            return result;
        }
    }
}

источник: https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-7.php

Answer 3

Используя System.Linq, вы можете быстро отсортировать список с помощью OrderBy (IEnumerable, Fun c) . Это быстро, особенно когда дело доходит до сравнения int или string.

List.OrderBy(a=> a);