37 lines
1.1 KiB
C#
37 lines
1.1 KiB
C#
static class QuickSort
|
|
{
|
|
private static readonly Random _rnd = Random.Shared;
|
|
|
|
public static List<T> Sort<T>(List<T> source, Comparer<T> comparer)
|
|
{
|
|
if (source.Count < 2)
|
|
return source;
|
|
|
|
var referenceIndex = _rnd.Next(source.Count);
|
|
var reference = source[referenceIndex];
|
|
var less = new List<T>();
|
|
var equal = new List<T>();
|
|
var more = new List<T>();
|
|
|
|
for (var i = 0; i < source.Count; i++)
|
|
{
|
|
var value = source[i];
|
|
if (comparer.Compare(value, reference) < 0)
|
|
less.Add(value);
|
|
else if (comparer.Compare(value, reference) > 0)
|
|
more.Add(value);
|
|
else if (comparer.Compare(value, reference) == 0)
|
|
equal.Add(value);
|
|
}
|
|
less = Sort(less, comparer);
|
|
more = Sort(more, comparer);
|
|
var index = 0;
|
|
foreach (var item in less)
|
|
source[index++] = item;
|
|
foreach (var item in equal)
|
|
source[index++] = item;
|
|
foreach (var item in more)
|
|
source[index++] = item;
|
|
return source;
|
|
}
|
|
} |