From 8938c3447d88e31f77f20553ed185fc8e64c9ac8 Mon Sep 17 00:00:00 2001 From: chai Date: Tue, 22 Jun 2021 14:58:53 +0800 Subject: +misc --- Assets/Algorithms/Sorting.cs | 159 ------------------------------------------- 1 file changed, 159 deletions(-) delete mode 100644 Assets/Algorithms/Sorting.cs (limited to 'Assets/Algorithms/Sorting.cs') diff --git a/Assets/Algorithms/Sorting.cs b/Assets/Algorithms/Sorting.cs deleted file mode 100644 index c4bdc70..0000000 --- a/Assets/Algorithms/Sorting.cs +++ /dev/null @@ -1,159 +0,0 @@ -using System; -using System.Collections; -using System.Collections.Generic; -using AlgorithmCollection; - -//https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95 -namespace AlgorithmCollection.Sorting -{ - - // 排序主要关注稳定性和效率 - // *稳定性，相同值的元素相对位置在排序前后是否改变 - // *效率，时间复杂度和空间复杂度 - public static class SortingHelper - { - - // 选择合适的算法排序 - public static void Sort(T[] data, bool bDescent = false, bool bStable = false) where T : IComparable, IEquatable - { - int n = data.Length; - } - - #region 归并排序 - // 归并排序 | 稳定 | 分治法 - // T(n) = O(nlogn) 渐进最优 - // S(n) = O(n) 需要大小为n的额外空间 - public static void MergeSort(T[] data, bool descent = false) where T : IComparable, IEquatable - { - T[] temp = new T[data.Length];// 需要额外的临时空间 - _MergeSort(data, 0, data.Length - 1, descent, temp); - } - - // 归并排序，非递归 - public static void MergeSort_NoneRecursion(T[] data, bool descent = false) where T : IComparable, IEquatable - { - T[] temp = new T[data.Length];// 需要额外的临时空间 - int s = 1; - int n = data.Length; - for(int seg = 1; seg < n; seg += seg) //步长1,2,4,8... - { - for(int start = 0; start < n; start += seg * 2) - { - int left = start, right = Algorithms.Min(start + seg * 2 - 1, n - 1); - int mid = Algorithms.Min(start + seg - 1, n - 1); - _Merge(data, left, mid, right, descent, temp); - _CopyTo(temp, data, left, right); - } - } - } - - private static void _MergeSort(T[] data, int left, int right, bool descent, T[] temp) where T : IComparable, IEquatable - { - // 这是一个O(logn)的分治算法，对于每此分治，会有一个O(n)的合并算法，所以归并排序复杂度是O(nlogn) - if (left < right) - { - int middle = (left + right) / 2; - _MergeSort(data, left, middle, descent, temp); - _MergeSort(data, middle + 1, right, descent, temp); - _Merge(data, left, middle, right, descent, temp);// 把left~right部分合并到temp中 - _CopyTo(temp, data, left, right); // 把合并后的temp部分复制回去 - } - } - - private static T[] _Merge(T[]data, int left, int middle, int right, bool descent, T[] temp) where T : IComparable, IEquatable - { - // 这是一个O(n)的合并算法 - int l = left, r = middle + 1; - int i = 0; - while(l <= middle || r <= right) - { - if(l > middle) - { - temp[i++] = data[r++]; - continue; - } - if(r > right) - { - temp[i++] = data[l++]; - continue; - } - if (descent && data[l].CompareTo(data[r]) > 0 || !descent && data[l].CompareTo(data[r]) < 0) - { - temp[i++] = data[l]; - l++; - } - else - { - temp[i++] = data[r]; - r++; - } - } - return temp; - } - - private static void _CopyTo(T[] src, T[] dst, int from, int to) - { - for (int i = from; i <= to; ++i) - dst[i] = src[i - from]; - } - - #endregion - - #region 快速排序 - // 快速排序 | 不稳定 | 原地排序 | 分治法 - // 平均T(n)=O(nlogn)，最坏T(n)=O(n²) - // S(n)=O(1) - public static void QuickSort(T[] data, bool descent = false) where T : IComparable, IEquatable - { - _QuickSort(data, descent, 0, data.Length - 1); - } - private static void _QuickSort(T[] data, bool descent, int start, int end) where T : IComparable, IEquatable - { - if(start < end) - { - int p = _Partion(data, descent, start, end); - _QuickSort(data, descent, start, p - 1); - _QuickSort(data, descent, p + 1, end); - } - } - private static int _Partion(T[] data, bool descent, int start, int end) where T : IComparable - { - T v = data[start]; - int i = start; - int j = end + 1; - while(true) - { - while ((descent && data[++i].CompareTo(v) >= 0 - || !descent && data[++i].CompareTo(v) <= 0) && i < end) ; - while ((descent && data[--j].CompareTo(v) <= 0 - || !descent && data[--j].CompareTo(v) >= 0) && j > start) ; - if (i >= j) - break; - Algorithms.Swap(ref data, i, j); - } - Algorithms.Swap(ref data, start, j); - return j; - } - #endregion - - // 冒泡排序，稳定 - // O(n²) - public static void BubbleSort(T[] data, bool descent = false) where T : IComparable, IEquatable - { - int n = data.Length; - for(int i = 0; i < n; ++i) - { - for(int j = 0; j < n - i - 1; ++j) - { - if (descent && data[j].CompareTo(data[j + 1]) < 0 - || !descent && data[j].CompareTo(data[j + 1]) > 0) - { - Algorithms.Swap(ref data, j, j + 1); - } - } - } - } - - } - -} \ No newline at end of file -- cgit v1.1-26-g67d0