这个排序算法在c#中的名称是什么?
问题描述:
public static int[] Sort(int[] ints)
{
var dictionary = new IndexedDictionary<int, int>();
foreach (var i in ints)
{
dictionary.Add(i, i);
}
for (int i = 0; i <= ints.Length - 1; i++)
{
var indexValue = dictionary[i].Key;
dictionary[indexValue - 1].Value = indexValue;
}
return dictionary.Values();
}
它是一个桶排序?我已经看到了一些排序,他们看起来比这更复杂。另外请忽略IndexedDictionary类 - 它是一个自定义类,允许通过索引获取值。这个排序算法在c#中的名称是什么?
编辑:CompuChip - 如果你想看到的IndexedDictionary:
public class IndexedDictionary<T, TY>
{
public class DicObject<T, Y>
{
public T Key { get; set; }
public Y Value { get; set; }
}
private HashSet<DicObject<T, TY>> list = new HashSet<DicObject<T, TY>>();
public void Add(T o, TY u)
{
list.Add(new DicObject<T, TY>{Key = o, Value = u});
}
public DicObject<T, TY> this[int i] {
get{return list.ElementAt(i);}
}
public T[] Keys()
{
return list.Select(x => x.Key).ToArray();
}
public TY[] Values()
{
return list.Select(x => x.Value).ToArray();
}
}
它不是关键的。
答
这是pigeon hole sorting的一种形式,但它仅限于能够排序具有从1到上的无差异值的集合。 (比如你尝试阵列{4,3,2}
排序就会死机。)
所以,它适用于任何集合,它做同样的事情:
public static int[] Sort(int[] ints) {
return Enumerable.Range(1, ints.Length).ToArray();
}
的IndexedDictionary
仅仅是一个复杂以及以任意顺序迭代项目的缓慢方式,并按照相同的任意顺序将每个值放在适当位置,以便最终进行排序。你可以做同样的事情更简单,更快地规则阵列:
public static int[] Sort(int[] ints) {
int[] result = new int[ints.Length];
foreach (int value in ints) {
result[value - 1] = value;
}
return result;
}
对于与不具有具有1的最低值,并连续收集工作的实现,你会创建一个数组从最低值到最高值,并将其中的值,然后按顺序收集它们:
public static int[] Sort(int[] ints) {
int min = ints.Min();
int max = ints.Max();
int?[] pigeonHoles = new int?[max - min + 1];
foreach (int value in ints) {
pigeonHoles[value - min] = value;
}
int[] result = new int[ints.Length];
int index = 0;
foreach (int? value in pigeonHoles) {
if (value.HasValue) {
result[index++] = value.Value;
}
}
return result;
}
答
我不知道如何忽略IndexedDictionary
,因为它似乎是算法的关键,但假设它像一个标准字典一样工作,我会认为这基本上是一种插入排序 - 您将所有值都放入一个字典,它将它插入正确的位置以保持其键的排序,最后,您可以提取所有按正确顺序排列的值。然而,所有的努力都是隐形的,因为它在Dictionary
类中。
一个标准类的条款类似的解决方案会是这样的
public static IEnumerable<int> Sort(int[] ints)
{
var dictionary = new Dictionary<int, bool>();
foreach (var i in ints)
{
dictionary.Add(i, false);
}
return dictionary.Keys;
}
(虽然这并不发生数超过一次处理)。
排序什么属性是什么? – Gnqz
我不知道我们怎么可以忽略'IndexedDictionary',因为它似乎是你的算法的关键,但假设它像一个标准字典一样工作,我会认为这基本上是一个插入排序 - 你把所有的值放入一个字典将其插入正确的位置以保持其键的排序。 – CompuChip
这似乎给字典增加了新的值,你确定这只是*一个*排序*实现? –