1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
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);
}
}
}
}
}
}
|
