c# - 这个排序算法有名字吗？

Question

长话短说，我想出了这个算法，但我怀疑我是否发明了什么东西。那么这个叫什么名字呢？

我知道它在多个领域有很多限制。例如，此实现无法对高于 UInt16 的数字进行排序，并且限制为最大 int.MaxValue 出现次数。我也可能在某处遇到一些数组边界问题。它已经像蛋糕一样吃掉 RAM :)

实际算法是在 CustomSort 方法中实现的。剩下的就是我用来测试的代码。

  class Program
    {
        static Random r = new Random((int)DateTime.Now.Ticks);

        static int[] GetRandomIntegers(int count)
        {
            int[] result = new int[count];
            for (int i = 0; i < count; i++)
            {
                int randomNumber = r.Next(0, UInt16.MaxValue);
                result[i] = randomNumber;
            }
            return result;
        }

        public static int[] CustomSort(int[] itemsToSort)
        {
            // Consider each number in the array to sort as a "memory address" or index of a huge array
            // which has a default value of zero and gets incremented every time that number is encountered
            // Example:
            // Array to sort: 5, 2, 2, 7, 5, 1, 3
            // Create an array of at most 7 dimensions. 
            //      Since that number takes time to find, bind the algorithms limit of maximum numbers to UInt16 and skip that step. Prefer more ram over processor time :)
            // First item, 5 encountered - Take index 5 in result array and add one, result is 1
            // Second item, 2 encountered - Take index 2 in result array and add one, result is 1
            // Third item, 2 encountered - Take index 2 in result array and add one, result is 2
            // Loop until done
            // Now the temp array will contain how many times each number was encountered. The array index is the number itself, and traversing the array from 0 to N
            // will provide the count of how many times that number was encountered
            // For each number not encountered the value at index will stay 0 and just consume RAM :)

            int[] temp = new int[UInt16.MaxValue];
            for (int i = 0; i < itemsToSort.Length; i++)
            {
                temp[itemsToSort[i]]++;
            }

            // Final step, create resulting sorted array by looping over the temp array and creation of that many items as the value of the current index
            int[] result = new int[itemsToSort.Length];
            int current = 0;
            for (int i = 0; i < UInt16.MaxValue; i++)
            {
                int count = temp[i];
                for (int j = 0; j < count; j++)
                {
                    result[current] = i;
                    current++;
                }
            }
            return result;
        }

        static void Main(string[] args)
        {
            Stopwatch watch = new Stopwatch();
            watch.Start();

            int[] sortMe = GetRandomIntegers(1000000000);
            int[] arraySorted = new int[sortMe.Length];
            watch.Stop();
            Console.WriteLine($"Random generation of '{sortMe.Length}' elements took: {watch.Elapsed}");

            Array.Copy(sortMe, 0, arraySorted, 0, sortMe.Length);
            watch.Restart();
            Array.Sort(arraySorted);
            watch.Stop();
            Console.WriteLine("Array sort(Heap/Quicksort) took: " + watch.Elapsed);

            watch.Restart();
            int[] mySorted = CustomSort(sortMe);
            watch.Stop();
            Console.WriteLine("Custom sort took: " + watch.Elapsed);

            watch.Restart();
            bool isEqual = Enumerable.SequenceEqual(mySorted, arraySorted);
            watch.Stop();
            Console.WriteLine($"Equality check: {isEqual} took: {watch.Elapsed}");
            Console.WriteLine("Done");

            Console.ReadLine();
        }
    }

Answer 1

你想出的算法是counting sort !