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
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);
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|