c# - 这个排序算法有名字吗?
问题描述
长话短说,我想出了这个算法,但我怀疑我发明了什么。那么这个叫什么名字呢?
我知道它在多个领域有很多限制。例如,此实现不能对高于 UInt16 的数字进行排序,并且仅限于 int.MaxValue 出现的最大值。我也可能在某处遇到一些数组边界问题。而且它已经像蛋糕一样吃内存了:)
实际算法在 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();
}
}
解决方案
您提出的算法是计数排序!
推荐阅读
- javascript - 从 AWS Lambda 提取检索旧数据
- javascript - 在表单按钮 onclick 后应用 Html 样式更改时不会坚持
- python-3.x - 在 Python 3 中经常调用的函数之外定义一个变量
- mysql - 在 CTE 的递归部分中使用 ROW_NUMBER() 是否有替代方法?
- python - 计算过滤器中 SQLAlchemy 关系的数量
- c++ - 用户将字符串输入字符串向量并对其进行验证
- java - Java:我们可以使用多 HashMap 对结果集进行分组吗
- .net-core - AddHttpClient 配置的 HttpClient.Timeout 被忽略
- r - 在原始数据中的日期之外填充数周
- azure-active-directory - 如何在 Azure Active Directory 中确定每个应用程序的权限范围