using System using System Collections Generic using System Linq using

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace BlockSort
{
public static class Sort
{
public static void BlockSort<T>(IList<KeyValuePair<int, T> > ar)
{
if (ar == null || ar.Count < 2) return;
int xmin = ar[0].Key;
int xmax = ar[0].Key;
foreach (KeyValuePair<int, T> tp in ar)
{
xmin = Math.Min(xmin, tp.Key);
xmax = Math.Max(xmax, tp.Key);
}
int n = xmax - xmin + 1;
int[] S = new int[n];
int[] E = new int[n];
foreach (KeyValuePair<int, T> tp in ar)
{
++E[tp.Key - xmin];
}
for (int i = 1; i < n; ++i)
{
S[i] = E[i - 1];
E[i] += E[i - 1];
}
for (int i = 0; i < n; ++i)
{
while (S[i] != E[i])
{
if (ar[S[i]].Key - xmin == i)
{
++S[i];
}
else
{
KeyValuePair<int, T> tp = ar[S[i]];
ar[S[i]] = ar[S[tp.Key - xmin]];
ar[S[tp.Key - xmin]++] = tp;
}
}
}
}
}
class Program
{
static void Main(string[] args)
{
KeyValuePair<int, string>[] ar = new KeyValuePair<int, string>[]{
new KeyValuePair<int, string>(7, "1abc"),
new KeyValuePair<int, string>(6, "2ghi"),
new KeyValuePair<int, string>(7, "3def"),
new KeyValuePair<int, string>(5, "4abc"),
new KeyValuePair<int, string>(1, "5abc"),
new KeyValuePair<int, string>(12, "6def")
};
Sort.BlockSort(ar);
foreach (KeyValuePair<int, string> x in ar)
{
Console.WriteLine("[" + x.Key.ToString() + ";" + x.Value.ToString() + "]");
}
}
}
}