代码拉取完成,页面将自动刷新
namespace Algorithms.Sorters.String;
/// <summary>
/// Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating
/// and distributing elements into buckets according to their radix.
/// Radix sorts can be implemented to start at either the most significant digit (MSD)
/// or least significant digit (LSD).
/// MSD radix sorts are most suitable for sorting array of strings with variable length
/// in lexicographical order.
/// </summary>
public class MsdRadixStringSorter : IStringSorter
{
/// <summary>
/// Sort array of strings using MSD radix sort algorithm.
/// </summary>
/// <param name="array">Array to sort.</param>
public void Sort(string[] array) => Sort(array, 0, array.Length - 1, 0, new string[array.Length]);
private static void Sort(string[] array, int l, int r, int d, string[] temp)
{
if (l >= r)
{
return;
}
const int k = 256;
var count = new int[k + 2];
for (var i = l; i <= r; i++)
{
var j = Key(array[i]);
count[j + 2]++;
}
for (var i = 1; i < count.Length; i++)
{
count[i] += count[i - 1];
}
for (var i = l; i <= r; i++)
{
var j = Key(array[i]);
temp[count[j + 1]++] = array[i];
}
for (var i = l; i <= r; i++)
{
array[i] = temp[i - l];
}
for (var i = 0; i < k; i++)
{
Sort(array, l + count[i], l + count[i + 1] - 1, d + 1, temp);
}
int Key(string s) => d >= s.Length ? -1 : s[d];
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。