diff options
| author | chai <chaifix@163.com> | 2021-06-21 22:59:39 +0800 |
|---|---|---|
| committer | chai <chaifix@163.com> | 2021-06-21 22:59:39 +0800 |
| commit | 5d81d8d8b4062def695c27fa02f67625871e8dce (patch) | |
| tree | 1ab1a4b48b029e5f84d73cf0a6e7140782eb27e9 /Assets/Algorithms/Sorting.cs | |
| parent | cc475a8b16b0e9323623c6532e114dceeb64353a (diff) | |
*misc
Diffstat (limited to 'Assets/Algorithms/Sorting.cs')
| -rw-r--r-- | Assets/Algorithms/Sorting.cs | 159 |
1 files changed, 159 insertions, 0 deletions
diff --git a/Assets/Algorithms/Sorting.cs b/Assets/Algorithms/Sorting.cs new file mode 100644 index 0000000..c4bdc70 --- /dev/null +++ b/Assets/Algorithms/Sorting.cs @@ -0,0 +1,159 @@ +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 |