using System; namespace Apewer.Internals { // 快速排序。 internal class QuickSorter { private const int IntrosortSizeThreshold = 16; private const int QuickSortDepthThreshold = 32; private T[] keys; private T[] items; private Comparison comparison; private QuickSorter(T[] keys, T[] items, Comparison 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 comparison) { var instance = new QuickSorter(array, null, comparison); instance.Sort(0, array.Length); } } }