简而言之，我想出了这个算法，但我怀疑我没有发明什么新东西。那么这叫什么名字呢？
我知道它在多个领域有很多限制。例如，此实现无法对高于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();
}
}