You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

294 lines
8.3 KiB

using System;
namespace Apewer.Internals
{
// 快速排序。
internal class QuickSorter<T>
{
private const int IntrosortSizeThreshold = 16;
private const int QuickSortDepthThreshold = 32;
private T[] keys;
private T[] items;
private Comparison<T> comparison;
private QuickSorter(T[] keys, T[] items, Comparison<T> comparison)
{
this.keys = keys;
this.items = items;
this.comparison = comparison;
}
private void SwapIfGreaterWithItems(int a, int b)
{
if (a != b && comparison(keys[a], keys[b]) > 0)
{
T temp1 = keys[a];
keys[a] = keys[b];
keys[b] = temp1;
if (items != null)
{
T temp2 = items[a];
items[a] = items[b];
items[b] = temp2;
}
}
}
private void Swap(int i, int j)
{
T temp1 = keys[i];
keys[i] = keys[j];
keys[j] = temp1;
if (items != null)
{
T temp2 = items[i];
items[i] = items[j];
items[j] = temp2;
}
}
private void Sort(int left, int length)
{
// if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) IntrospectiveSort(left, length);
DepthLimitedQuickSort(left, length + left - 1, 32);
}
private void DepthLimitedQuickSort(int left, int right, int depthLimit)
{
do
{
if (depthLimit == 0)
{
Heapsort(left, right);
break;
}
int i = left;
int num = right;
int median = GetMedian(i, num);
SwapIfGreaterWithItems(i, median);
SwapIfGreaterWithItems(i, num);
SwapIfGreaterWithItems(median, num);
T temp1 = keys[median];
do
{
for (; comparison(keys[i], temp1) < 0; i++)
{
}
while (comparison(temp1, keys[num]) < 0)
{
num--;
}
if (i > num)
{
break;
}
if (i < num)
{
T temp2 = keys[i];
keys[i] = keys[num];
keys[num] = temp2;
if (items != null)
{
T temp3 = items[i];
items[i] = items[num];
items[num] = temp3;
}
}
i++;
num--;
}
while (i <= num);
depthLimit--;
if (num - left <= right - i)
{
if (left < num)
{
DepthLimitedQuickSort(left, num, depthLimit);
}
left = i;
}
else
{
if (i < right)
{
DepthLimitedQuickSort(i, right, depthLimit);
}
right = num;
}
}
while (left < right);
}
private void IntrospectiveSort(int left, int length)
{
if (length >= 2)
{
IntroSort(left, length + left - 1, 2 * FloorLog2(keys.Length));
}
}
private void IntroSort(int lo, int hi, int depthLimit)
{
while (hi > lo)
{
int num = hi - lo + 1;
if (num <= 16)
{
switch (num)
{
case 1:
break;
case 2:
SwapIfGreaterWithItems(lo, hi);
break;
case 3:
SwapIfGreaterWithItems(lo, hi - 1);
SwapIfGreaterWithItems(lo, hi);
SwapIfGreaterWithItems(hi - 1, hi);
break;
default:
InsertionSort(lo, hi);
break;
}
break;
}
if (depthLimit == 0)
{
Heapsort(lo, hi);
break;
}
depthLimit--;
int num2 = PickPivotAndPartition(lo, hi);
IntroSort(num2 + 1, hi, depthLimit);
hi = num2 - 1;
}
}
private int PickPivotAndPartition(int lo, int hi)
{
int num1 = lo + (hi - lo) / 2;
SwapIfGreaterWithItems(lo, num1);
SwapIfGreaterWithItems(lo, hi);
SwapIfGreaterWithItems(num1, hi);
T temp = keys[num1];
Swap(num1, hi - 1);
int num2 = lo;
int num3 = hi - 1;
while (num2 < num3)
{
while (comparison(keys[++num2], temp) < 0)
{
}
while (comparison(temp, keys[--num3]) < 0)
{
}
if (num2 >= num3)
{
break;
}
Swap(num2, num3);
}
Swap(num2, hi - 1);
return num2;
}
private void Heapsort(int lo, int hi)
{
int num = hi - lo + 1;
for (int num2 = num / 2; num2 >= 1; num2--)
{
DownHeap(num2, num, lo);
}
for (int num3 = num; num3 > 1; num3--)
{
Swap(lo, lo + num3 - 1);
DownHeap(1, num3 - 1, lo);
}
}
private void DownHeap(int i, int n, int lo)
{
T temp1 = keys[lo + i - 1];
T temp2 = (items != null) ? items[lo + i - 1] : default;
while (i <= n / 2)
{
int num = 2 * i;
if (num < n && comparison(keys[lo + num - 1], keys[lo + num]) < 0)
{
num++;
}
if (comparison(temp1, keys[lo + num - 1]) >= 0)
{
break;
}
keys[lo + i - 1] = keys[lo + num - 1];
if (items != null)
{
items[lo + i - 1] = items[lo + num - 1];
}
i = num;
}
keys[lo + i - 1] = temp1;
if (items != null)
{
items[lo + i - 1] = temp2;
}
}
private void InsertionSort(int lo, int hi)
{
for (int i = lo; i < hi; i++)
{
int num = i;
T temp1 = keys[i + 1];
T temp2 = (items != default) ? items[i + 1] : default;
while (num >= lo && comparison(temp1, keys[num]) < 0)
{
keys[num + 1] = keys[num];
if (items != null)
{
items[num + 1] = items[num];
}
num--;
}
keys[num + 1] = temp1;
if (items != null)
{
items[num + 1] = temp2;
}
}
}
private static int FloorLog2(int n)
{
int num = 0;
while (n >= 1)
{
num++;
n /= 2;
}
return num;
}
private static int GetMedian(int low, int hi)
{
return low + (hi - low >> 1);
}
public static void Sort(T[] array, Comparison<T> comparison)
{
var instance = new QuickSorter<T>(array, null, comparison);
instance.Sort(0, array.Length);
}
}
}