+misc

1 files changed, 0 insertions, 159 deletions

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>(T[] data, bool bDescent = false, bool bStable = false) where T : IComparable, IEquatable<T>

-        {

-            int n = data.Length;

-        }

-

-        #region 归并排序

-        // 归并排序 | 稳定 | 分治法

-        // T(n) = O(nlogn) 渐进最优

-        // S(n) = O(n) 需要大小为n的额外空间

-        public static void MergeSort<T>(T[] data, bool descent = false) where T : IComparable, IEquatable<T>

-        {

-            T[] temp = new T[data.Length];// 需要额外的临时空间

-            _MergeSort(data, 0, data.Length - 1, descent, temp);

-        }

-

-        // 归并排序，非递归

-        public static void MergeSort_NoneRecursion<T>(T[] data, bool descent = false) where T : IComparable, IEquatable<T>

-        {

-            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>(T[] data, int left, int right, bool descent, T[] temp) where T : IComparable, IEquatable<T>

-        {

-            // 这是一个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>(T[]data, int left, int middle, int right, bool descent, T[] temp) where T : IComparable, IEquatable<T>

-        {

-            // 这是一个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>(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>(T[] data, bool descent = false) where T : IComparable, IEquatable<T>

-        {

-            _QuickSort(data, descent, 0, data.Length - 1);

-        }

-        private static void _QuickSort<T>(T[] data, bool descent, int start, int end) where T : IComparable, IEquatable<T>

-        {

-            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>(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>(T[] data, bool descent = false) where T : IComparable, IEquatable<T>

-        {

-            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