Chemmy's Blog

chengming0916@outlook.com

发表于 更新于 分类于 ，

C#排序算法的比较

首先通过图表比较不同排序算法的时间复杂度和稳定性。

排序方法

平均时间

最坏情况

最好情况

辅助空间

稳定性

直接插入排序

O(n2)

O(n2)

O(n)

O(1)

是
冒泡排序

O(n2)

O(n2)

O(n)

O(1)

是
简单选择排序

O(n2)

O(n2)

O(n2)

O(1)

是
希尔排序-

O(nlog2n)~O(n2)

O(nlog2n)~O(n2)

O(1)

否
快速排序

O(nlog2n)

O(n2)

O(nlog2n)

O(log2n)

否
堆排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(1)

否
2-路归并排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(n)

是
基数排序O(d(n + rd))O(d(n + rd))O(d(n + rd))O(rd)是

注：1. 算法的时间复杂度一般情况下指最坏情况下的渐近时间复杂度。

        2. 排序算法的稳定性会对多关键字排序产生影响。

下面通过C#代码说明不同的排序算法

插入排序

时间复杂度：平均情况—O(n2) 最坏情况—O(n2) 辅助空间：O(1) 稳定性：稳定

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

希尔排序(shell)

时间复杂度：理想情况—O(nlog2n) 最坏情况—O(n2) 稳定性：不稳定

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

冒泡排序

时间复杂度：平均情况—O(n2) 最坏情况—O(n2) 辅助空间：O(1) 稳定性：稳定

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

快速排序

时间复杂度：平均情况—O(nlog2n) 最坏情况—O(n2) 辅助空间：O(log2n) 稳定性：不稳定

快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。

选择排序

时间复杂度：平均情况—O(n2) 最坏情况—O(n2) 辅助空间：O(1) 稳定性：不稳定

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

堆排序

时间复杂度：平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间：O(1) 稳定性：不稳定

我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法

归并排序

时间复杂度：平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间：O(n) 稳定性：稳定

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

发表于 更新于 分类于 ，

冒泡排序算法（C#实现） - Eric Sun - 博客园

Excerpt

简单的冒泡排序算法，代码如下：//冒泡排序（从数组的起始位置开始遍历，以大数为基准：大的数向下沉一位）privatestaticvoid BubbleSortFunction(int[] array) { try { int length = array.Length; int temp; bool

简单的冒泡排序算法，代码如下：

复制代码

1
<span>//</span><span>冒泡排序（从数组的起始位置开始遍历，以大数为基准：大的数向下沉一位）</span><span><br></span><span>private</span><span>static</span><span>void</span><span> BubbleSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> length </span><span>=</span><span> array.Length;<br>                </span><span>int</span><span> temp;<br>                </span><span>bool</span><span> hasExchangeAction; </span><span>//</span><span>记录此次大循环中相邻的两个数是否发生过互换（如果没有互换，则数组已经是有序的）</span><span><br></span><span><br>                </span><span>for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>0</span><span>; i </span><span>&lt;</span><span> length </span><span>-</span><span>1</span><span>; i</span><span>++</span><span>)    </span><span>//</span><span>数组有N个数，那么用N-1次大循环就可以排完</span><span><br></span><span>                {<br>                    hasExchangeAction </span><span>=</span><span>false</span><span>;  </span><span>//</span><span>每次大循环都假设数组有序</span><span><br></span><span><br>                    </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span>0</span><span>; j </span><span>&lt;</span><span> length </span><span>-</span><span> i </span><span>-</span><span>1</span><span>; j</span><span>++</span><span>)    </span><span>//</span><span>从数组下标0处开始遍历，（length - i - 1 是刨除已经排好的大数）</span><span><br></span><span>                    {<br>                        </span><span>if</span><span> (array[j] </span><span>&gt;</span><span> array[j </span><span>+</span><span>1</span><span>])    </span><span>//</span><span>相邻两个数进行比较，如果前面的数大于后面的数，则将这相邻的两个数进行互换</span><span><br></span><span>                        {<br>                            temp </span><span>=</span><span> array[j];<br>                            array[j] </span><span>=</span><span> array[j </span><span>+</span><span>1</span><span>];<br>                            array[j </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp;<br>                            hasExchangeAction </span><span>=</span><span>true</span><span>;   </span><span>//</span><span>发生过互换</span><span><br></span><span>                        }<br>                    }<br><br>                    </span><span>if</span><span> (</span><span>!</span><span>hasExchangeAction) </span><span>//</span><span>如果没有发生过互换，则数组已经是有序的了，跳出循环</span><span><br></span><span>                    {<br>                        </span><span>break</span><span>;<br>                    }<br>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

复制代码

。。。。。

posted @ 2011-08-17 16:02  Eric Sun  阅读(7637)  评论()  编辑  收藏  举报

发表于 更新于 分类于 ，

C# 经典排序算法大全

Excerpt

文章浏览阅读84次。C# 经典排序算法大全选择排序using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace sorter{ public class SelectionSorter { private int min; …_c# case复杂排序

C# 经典排序算法大全

选择排序

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
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class SelectionSorter

{

private int min;

public void Sort(int[] arr)

{

for (int i = 0; i < arr.Length - 1; ++i)

{

min = i;

for (int j = i + 1; j < arr.Length; ++j)

{

if (arr[j] < arr[min])

{

min = j;

}

}

int t = arr[min];

arr[min] = arr[i];

arr[i] = t;

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

SelectionSorter selSor = new SelectionSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

冒泡排序

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
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class EbullitionSorter

{

public void Sort(int[] arr)

{

int i, j, temp;

bool done = false;

j = 1;

while ((j < arr.Length) && (!done))

{

done = true;

for (i = 0; i < arr.Length - j; i++)

{

if (arr[i] > arr[i + 1])

{

done = false;

temp = arr[i];

arr[i] = arr[i + 1];

arr[i + 1] = temp;

}

}

j++;

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

EbullitionSorter selSor = new EbullitionSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

高速排序

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
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class QuickSorter

{

private void swap(ref int l, ref int r)

{

int temp;

temp = l;

l = r;

r = temp;

}

public void Sort(int[] list, int low, int high)

{

int pivot;

int l, r;

int mid;

if (high <= low)

{

return;

}

else if (high == low + 1)

{

if (list[low] > list[high])

{

swap(ref list[low], ref list[high]);

}

return;

}

mid = (low + high) >> 1;

pivot = list[mid];

swap(ref list[low], ref list[mid]);

l = low + 1;

r = high;

do

{

while (l <= r && list[l] < pivot)

{

l++;

}

while (list[r] >= pivot)

{

r--;

}

if (l < r)

{

swap(ref list[l], ref list[r]);

}

} while (l < r);

list[low] = list[r];

list[r] = pivot;

if (low + 1 < r)

{

Sort(list, low, r - 1);

}

if (r + 1 < high)

{

Sort(list, r + 1, high);

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

QuickSorter selSor = new QuickSorter();

selSor.Sort(arrInt, 0, arrInt.Length - 1);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

插入排序

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
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class InsertionSorter

{

public void Sort(int[] arr)

{

for (int i = 1; i < arr.Length; i++)

{

int t = arr[i];

int j = i;

while ((j > 0) && (arr[j - 1] > t))

{

arr[j] = arr[j - 1];

--j;

}

arr[j] = t;

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

InsertionSorter selSor = new InsertionSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

希尔排序

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
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace sorter

{

public class ShellSorter

{

public void Sort(int[] arr)

{

int inc;

for (inc = 1; inc <= arr.Length / 9; inc = 3 * inc + 1) ;

for (; inc > 0; inc /= 3)

{

for (int i = inc + 1; i <= arr.Length; i += inc)

{

int t = arr[i - 1];

int j = i;

while ((j > inc) && (arr[j - inc - 1] > t))

{

arr[j - 1] = arr[j - inc - 1];

j -= inc;

}

arr[j - 1] = t;

}

}

}

}

class Program

{

static void Main(string[] args)

{

int[] arrInt = new int[] { 4, 2, 7, 1, 8, 3, 9, 0, 5, 6 };

ShellSorter selSor = new ShellSorter();

selSor.Sort(arrInt);

foreach (int i in arrInt)

{

Console.WriteLine(i);

}

Console.ReadKey();

}

}

}

归并排序

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

public class Function

{

private int Groups;

private int CopyGroups;

private int mergerows;

private int[] Array27;

private static Random ran = new Random();

public Function(int length)

{

Array27 = new int[length];

for (int i = 0; i < length; i++)

Array27[i] = ran.Next(1, 100);

}

public void ToMergeSort()

{

MergeSort(Array27);

}

public void ToRecursiveMergeSort()

{

RecursiveMergeSort(Array27, 0, Array27.Length - 1);

}

public void ToNaturalMergeSort()

{

NaturalMergeSort(Array27);

}

public void RecursiveMergeSort(int[] Array, int left, int right)

{

int middle = (left + right) / 2;

if (left < right)

{

RecursiveMergeSort(Array, left, middle);

RecursiveMergeSort(Array, middle + 1, right);

MergeOne(Array, left, middle, right);

}

}

public void MergeOne(int[] Array, int left, int middle, int right)

{

int leftindex = left;

int rightindex = middle + 1;

int[] merge = new int[right + 1];

int index = 0;

while (leftindex <= middle && rightindex <= right)

merge[index++] = (Array[leftindex] - Array[rightindex]) >= 0 ? Array[rightindex++] : Array[leftindex++];

if (leftindex <= middle)

{

for (int i = leftindex; i <= middle; i++)

merge[index++] = Array[i];

}

if (rightindex <= right)

{

for (int i = rightindex; i <= right; i++)

merge[index++] = Array[i];

}

index = 0;

for (int i = left; i <= right; i++)

Array[i] = merge[index++];

}

public void MergeSort(int[] Array)

{

int[] merge = new int[Array.Length];

int P = 0;

while (true)

{

int index = 0;

int ENumb = (int)Math.Pow(2, P);

if (ENumb < Array.Length)

{

while (true)

{

int TorFAndrightindex = index;

if (TorFAndrightindex <= Array.Length - 1)

MergeTwo(Array, merge, index, ENumb);

else

break;

index += 2 * ENumb;

}

}

else

break;

P++;

}

}

public void MergeTwo(int[] Array, int[] merge, int index, int ENumb)

{

int left = index;

int middle = left + ENumb - 1;

if (middle >= Array.Length)

{

middle = index;

}

int mergeindex = index;

int right;

int middleTwo = (index + ENumb - 1) + 1;

right = index + ENumb + ENumb - 1;

if (right >= Array.Length - 1)

{

right = Array.Length - 1;

}

while (left <= middle && middleTwo <= right)

{

merge[mergeindex++] = Array[left] >= Array[middleTwo] ? Array[middleTwo++] : Array[left++];

}

if (left <= middle)

{

while (left <= middle && mergeindex < merge.Length)

merge[mergeindex++] = Array[left++];

}

if (middleTwo <= right)

{

while (middleTwo <= right)

merge[mergeindex++] = Array[middleTwo++];

}

if (right + 1 >= Array.Length)

Copy(Array, merge);

}

public void NaturalMergeSort(int[] Array)

{

int[,] PointsSymbol = LinearPoints(Array);

if (PointsSymbol[0, 1] == Array.Length - 1)

return;

else

NaturalMerge(Array, PointsSymbol);

}

public void NaturalMerge(int[] Array, int[,] PointsSymbol)

{

int left;

int right;

int leftend;

int rightend;

mergerows = GNumberTwo(Groups);

CopyGroups = Groups;

int[] TempArray = new int[Array.Length];

while (true)

{

int[,] TempPointsSymbol = new int[mergerows, 2];

int row = 0;

do

{

if (row != CopyGroups - 1)

{

left = PointsSymbol[row, 0];

leftend = PointsSymbol[row, 1];

right = PointsSymbol[row + 1, 0];

rightend = PointsSymbol[row + 1, 1];

MergeThree(Array, TempArray, left, leftend, right, rightend);

MergePointSymbol(PointsSymbol, TempPointsSymbol, row);

}

else

{

默认剩下的单独一个子数组已经虚拟合并。然后Copy进TempArray。

int TempRow = PointsSymbol[row, 0];

int TempCol = PointsSymbol[row, 1];

while (TempRow <= TempCol)

TempArray[TempRow] = Array[TempRow++];

TempPointsSymbol[row / 2, 0] = PointsSymbol[row, 0];

TempPointsSymbol[row / 2, 1] = PointsSymbol[row, 1];

break;

}

row += 2;

if (TempPointsSymbol[0, 1] == Array.Length - 1)

break;

}

while (row <= CopyGroups - 1);

Copy(Array, TempArray);

UpdatePointSymbol(PointsSymbol, TempPointsSymbol, row);

mergerows = GNumber(mergerows);

CopyGroups = GNumberTwo(CopyGroups);

if (PointsSymbol[0, 1] == Array.Length - 1)

break;

}

}

public int GNumber(int Value)

{

if (Value % 2 == 0)

Value /= 2;

else

Value -= 1;

return Value;

}

public int GNumberTwo(int Value)

{

if (Value % 2 == 0)

mergerows = Value / 2;

else

mergerows = Value / 2 + 1;

return mergerows;

}

public void MergeThree(int[] Array, int[] Temp, int left, int leftend, int right, int rightend)

{

int index = left;

while (left <= leftend && right <= rightend)

Temp[index++] = Array[left] >= Array[right] ? Array[right++] : Array[left++];

while (left <= leftend)

Temp[index++] = Array[left++];

while (right <= rightend)

Temp[index++] = Array[right++];

}

public void MergePointSymbol(int[,] PointsSymbol, int[,] TempPointsSymbol, int row)

{

int rowindex = row / 2;

TempPointsSymbol[rowindex, 0] = PointsSymbol[row, 0];

TempPointsSymbol[rowindex, 1] = PointsSymbol[row + 1, 1];

}

public void UpdatePointSymbol(int[,] PointsSymbol, int[,] TempPointsSymbol, int rows)

{

int row = 0;

for (; row < TempPointsSymbol.GetLength(0); row++)

{

for (int col = 0; col < 2; col++)

PointsSymbol[row, col] = TempPointsSymbol[row, col];

}

for (; row < PointsSymbol.GetLength(0); row++)

{

for (int col2 = 0; col2 < 2; col2++)

PointsSymbol[row, col2] = 0;

}

补剩下的index组，

// int row3 = TempPointsSymbol.GetLength(0); // PointsSymbol[row3, 0] = PointsSymbol[rows, 0]; // PointsSymbol[row3, 1] = PointsSymbol[rows, 1]; // //后面的清零 // for (int row4 = row3 + 1; row4 < PointsSymbol.GetLength(0); row4++) // { // for (int col4 = 0; col4 < 2; col4++) // PointsSymbol[row4, col4] = 0; // } //} } public int[,] LinearPoints(int[] Array) { Groups = 1; int StartPoint = 0; int row = 0; int col = 0; //最糟糕的情况就是有Array.Length行。 int[,] PointsSet = new int[Array.Length, 2]; //线性扫描Array，划分数组 //初始前index=0 PointsSet[row, col] = 0; do { //推断升序子数组终于的index开关 bool Judge = false; //从Array第二个数推断是否要结束或者是否是升序子数组. while (++StartPoint < Array.Length && Array[StartPoint] < Array[StartPoint - 1]) { //打开第一个升序子数组结束的index开关 Judge = true; //又一次開始第二个升序子数组的前index PointsSet[row, col + 1] = StartPoint - 1; //计算子数组个数 Groups++; //换行记录自然子数组的index row++; break; //–StartPoint; } //升序子数组结束index if (Judge) PointsSet[row, col] = StartPoint; //else // –StartPoint; } while (StartPoint < Array.Length); //终于index=StartPoint - 1，可是糟糕情况下还有剩余若干行为： 0,0 … PointsSet[row, col + 1] = StartPoint - 1; //调用展示方法 DisplaySubarray(Array, PointsSet, Groups); return PointsSet; } public void DisplaySubarray(int[] Array, int[,] PointsSet, int Groups) { Console.WriteLine(“Subarray is {0}:”, Groups); //展示子数组的前后index for (int r = 0; r < Groups; r++) { for (int c = 0; c < PointsSet.GetLength(1); c++) { Console.Write(PointsSet[r, c]); if (c < PointsSet.GetLength(1) - 1) Console.Write(“,”); } Console.Write(“\t\t”); } Console.WriteLine(); //展示分出的子数组 for (int v = 0; v < Groups; v++) { int i = 1; for (int r = PointsSet[v, 0]; r <= PointsSet[v, 1]; r++) { Console.Write(Array[r] + “ “); i++; } if (i <= 3) Console.Write(“\t\t”); else Console.Write(“\t”); if (PointsSet[v, 1] == Array.Length) break; } } public void Copy(int[] Array, int[] merge) { //一部分排好序的元素替换掉原来Array中的元素 for (int i = 0; i < Array.Length; i++) { Array[i] = merge[i]; } } //输出 public override string ToString() { string temporary = string.Empty; foreach (var element in Array27) temporary += element + “ “; temporary += “\n”; return temporary; } } class Program { static void Main(string[] args) { while (true) { Console.WriteLine(“请选择：”); Console.WriteLine(“1.归并排序（非递归）”); Console.WriteLine(“2.归并排序（递归）”); Console.WriteLine(“3.归并排序（自然合并）”); Console.WriteLine(“4.退出”); int Arraynum = Convert.ToInt32(Console.ReadLine()); switch (Arraynum) { case 4: Environment.Exit(0); break; case 1: Console.WriteLine(“Please Input Array Length”); int Leng271 = Convert.ToInt32(Console.ReadLine()); Function obj1 = new Function(Leng271); Console.WriteLine(“The original sequence:”); Console.WriteLine(obj1); Console.WriteLine(“‘MergeSort’ Finaly Sorting Result:”); obj1.ToMergeSort(); Console.WriteLine(obj1); break; case 2: Console.WriteLine(“Please Input Array Length”); int Leng272 = Convert.ToInt32(Console.ReadLine()); Function obj2 = new Function(Leng272); Console.WriteLine(“The original sequence:”); Console.WriteLine(obj2); Console.WriteLine(“‘RecursiveMergeSort’ Finaly Sorting Result:”); obj2.ToRecursiveMergeSort(); Console.WriteLine(obj2); break; case 3: Console.WriteLine(“Please Input Array Length”); int Leng273 = Convert.ToInt32(Console.ReadLine()); Function obj3 = new Function(Leng273); Console.WriteLine(“The original sequence:”); Console.WriteLine(obj3); obj3.ToNaturalMergeSort(); Console.WriteLine(); Console.WriteLine(); Console.WriteLine(“‘NaturalMergeSort’ Finaly Sorting Result:”); Console.WriteLine(obj3); break; } } } } }

基数排序

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
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

public class RadixSorter

{

public int[] RadixSort(int[] ArrayToSort, int digit)

{

for (int k = 1; k <= digit; k++)

{

int[] tmpArray = new int[ArrayToSort.Length];

int[] tmpCountingSortArray = new int[10] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

for (int i = 0; i < ArrayToSort.Length; i++)

{

int tmpSplitDigit = ArrayToSort[i] / (int)Math.Pow(10, k - 1) - (ArrayToSort[i] / (int)Math.Pow(10, k)) * 10;

tmpCountingSortArray[tmpSplitDigit] += 1;

}

for (int m = 1; m < 10; m++)

{

tmpCountingSortArray[m] += tmpCountingSortArray[m -

1];

}

for (int n = ArrayToSort.Length - 1; n >= 0; n--)

{

int tmpSplitDigit = ArrayToSort[n] / (int)Math.Pow(10, k - 1) -

(ArrayToSort[n] / (int)Math.Pow(10, k)) * 10;

tmpArray[tmpCountingSortArray[tmpSplitDigit] - 1] = ArrayToSort

[n];

tmpCountingSortArray[tmpSplitDigit] -= 1;

}

for (int p = 0; p < ArrayToSort.Length; p++)

{

ArrayToSort[p] = tmpArray[p];

}

}

return ArrayToSort;

}

}

class Program

{

static void Main(string[] args)

{

int[] intArray = new int[] { 5, 3, 7, 4, 8, 2, 9, 1, 0, 6 };

int[] newIntArray = intArray;

RadixSorter rS=new RadixSorter();

newIntArray = rS.RadixSort(intArray, intArray.Length);

foreach (int i in intArray)

{

Console.Write(i + " ");

}

Console.ReadKey();

}

}

}

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

class Program

{

/// 要求: /// arrayToSort的元素必须大于等于0。或者经过一定的转换使其元素在 /// 大于等于0范围内。比如有例如以下序列(-1,-8,10,11),那么依据最小值8, /// 将各个数字加8转化为(7,0,18,19),然后进行计数排序。结果为(0,7,18,19), /// 然后再将结果个数字减8即为(-8,-1,10,11) /// /// 要排序的数组 /// 数组的最大值加一 /// 计数排序后的结果 public static int[] CountingSort(int[] arrayToSort, int k) { // 排序后的结果存储 int[] sortedArray = new int[arrayToSort.Length]; // 计数数组 int[] countingArray = new int[k]; // 计数数组初始化 for (int i = 0; i < countingArray.Length; i++) { countingArray[i] = 0; } // 单个元素计数(经过该步骤countingArray[i]的含义为数字i的个数为countingArray[i]) for (int i = 0; i < arrayToSort.Length; i++) { countingArray[arrayToSort[i]] = countingArray[arrayToSort[i]] + 1; } // 计算小于等于某数的个数(经过该步骤countingArray[i]的含义为小于等于数字i的元素个数为countingArray[i]) for (int i = 1; i < countingArray.Length; i++) { countingArray[i] += countingArray[i - 1]; } // 得到排序后的结果 for (int i = 0; i < sortedArray.Length; i++) { int numIndex = countingArray[arrayToSort[i]] - 1; sortedArray[numIndex] = arrayToSort[i]; countingArray[arrayToSort[i]] = countingArray[arrayToSort[i]] - 1; } return sortedArray; } static void Main(string[] args) { int[] intArray = new int[] { 5, 3, 7, 4, 8, 2, 9, 1, 0, 6 }; int[] intNewArray = intArray; intNewArray = CountingSort(intArray, intArray.Length); foreach (int i in intNewArray) { Console.Write(i + “ “); } Console.ReadKey(); } } }

堆排序

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
160
161
162
163
164
165
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Merge

{

class Program

{

private static void HeapSortFunction(int[] array)

{

try

{

BuildMaxHeap(array);

for (int i = array.Length - 1; i > 0; i--)

{

Swap(ref array[0], ref array[i]);

MaxHeapify(array, 0, i);

}

}

catch (Exception ex)

{

Console.Write(ex.Message);

}

}

private static void BuildMaxHeap(int[] array)

{

try

{

for (int i = array.Length / 2 - 1; i >= 0; i--)

{

MaxHeapify(array, i, array.Length);

}

}

catch (Exception ex)

{

Console.Write(ex.Message);

}

}

private static void MaxHeapify(int[] array, int currentIndex, int heapSize)

{

try

{

int left = 2 * currentIndex + 1;

int right = 2 * currentIndex + 2;

int large = currentIndex;

if (left < heapSize && array[left] > array[large])

{

large = left;

}

if (right < heapSize && array[right] > array[large])

{

large = right;

}

if (currentIndex != large)

{

Swap(ref array[currentIndex], ref array[large]);

MaxHeapify(array, large, heapSize);

}

}

catch (Exception ex)

{

Console.Write(ex.Message);

}

}

private static void Swap(ref int a, ref int b)

{

int temp = 0;

temp = a;

a = b;

b = temp;

}

static void Main(string[] args)

{

int[] intArray = new int[] { 5, 3, 7, 4, 8, 2, 9, 1, 0, 6 };

HeapSortFunction(intArray);

foreach (int i in intArray)

{

Console.Write(i + " ");

}

Console.ReadKey();

}

}

}

排序的分类/稳定性/时间复杂度和空间复杂度总结

版权声明：本文博客原创文章。博客，未经同意，不得转载。

发表于 更新于 分类于 ，

归并排序算法（C#实现）

Excerpt

自顶向下的归并排序：是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：1）划分子表 2）合并半子表

     归并排序(Merge Sort)是利用”归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。归并排序有两种方式：1): 自底向上的方法 2):自顶向下的方法

 1、 自底向上的方法
（1） 自底向上的基本思想
     自底向上的基本思想是：第1趟归并排序时，将待排序的文件R[1..n]看作是n个长度为1的有序子文件，将这些子文件两两归并，若n为偶数，则得到n/2个长度为2的有序子文件；若n为奇数，则最后一个子文件轮空(不参与归并)。故本趟归并完成后，前n/2 - 1个有序子文件长度为2，但最后一个子文件长度仍为1；第2趟归并则是将第1趟归并所得到的n/2个有序的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止。
     上述的每次归并操作，均是将两个有序的子文件合并成一个有序的子文件，故称其为”二路归并排序”。类似地有k(k>2)路归并排序。   

2、自顶向下的方法(本文主要介绍此种方法，下面的文字都是对此种方法的解读)

（1） 自顶向下的基本思想
     采用分治法进行自顶向下的算法设计，形式更为简洁。
     自顶向下的归并排序：是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：

      1）划分子表

      2）合并半子表

（1）分治法的三个步骤
     设归并排序的当前区间是R[low..high]，分治法的三个步骤是：
①分解：将当前区间一分为二，即求分裂点
②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
  递归的终结条件：子区间长度为1（一个记录自然有序）。

如下演示递归的整个过程：

递归便是深度遍历（如下由左至右进行遍历）：假设有这样的一列数组{9,8,7,6,5,4,3,2,1}进行划分的顺序如下：

{9,8,7,6,5,4,3,2,1} –> {9,8,7,6,5}，{4,3,2,1}

{9,8,7,6,5} –> {9,8,7}，{6,5}

                        {9,8,7} –> {9,8}，{7}

                                          {9,8} –> {9}，{8}

                        {6,5} –>{6}，{5}

{4,3,2,1} –> {4,3}，{2,1}

                      {4,3} –>{4}，{3}

                      {2,1} –>{2}，{1}

当深度划分到左右数组都只剩1个元素的时候，进行上述逆序的合并：

{9}，{8} –> {8,9} 然后和 {7} –> {7,8,9}

                                {6}，{5} –> {5,6}    然后 {7,8,9}和{5,6} –> {5,6,7,8,9}

                                     {2}，{1} –> {1,2}

                                     {4}，{3} –> {3,4}   然后 {1,2}和 {3,4} –> {1,2,3,4}

                                                                                                                         最终{5,6,7,8,9}和{1,2,3,4} –> {1,2,3,4,5,6,7,8,9}

具体实现代码如下所示：

复制代码

1
<span>//</span><span>归并排序（目标数组，子表的起始位置，子表的终止位置）</span><span><br></span>        <span>private</span> <span>static</span> <span>void</span> MergeSortFunction(<span>int</span>[] array, <span>int</span> first, <span>int</span> last)<br>        {<br>            <span>try</span><br>            {<br>                <span>if</span> (first &lt; last)   <span>//</span><span>子表的长度大于1，则进入下面的递归处理</span><span><br></span>                {<br>                    <span>int</span> mid = (first + last) / <span>2</span>;   <span>//</span><span>子表划分的位置</span><span><br></span>                    MergeSortFunction(array, first, mid);   <span>//</span><span>对划分出来的左侧子表进行递归划分</span><span><br></span>                    MergeSortFunction(array, mid + <span>1</span>, last);    <span>//</span><span>对划分出来的右侧子表进行递归划分</span><span><br></span>                    MergeSortCore(array, first, mid, last); <span>//</span><span>对左右子表进行有序的整合（归并排序的核心部分）</span><span><br></span>                }<br>            }<br>            <span>catch</span> (Exception ex)<br>            { }<br>        }<br><br>        <span>//</span><span>归并排序的核心部分：将两个有序的左右子表（以mid区分），合并成一个有序的表</span><span><br></span>        <span>private</span> <span>static</span> <span>void</span> MergeSortCore(<span>int</span>[] array, <span>int</span> first, <span>int</span> mid, <span>int</span> last)<br>        {<br>            <span>try</span><br>            {<br>                <span>int</span> indexA = first; <span>//</span><span>左侧子表的起始位置</span><span><br></span>                <span>int</span> indexB = mid + <span>1</span>;   <span>//</span><span>右侧子表的起始位置</span><span><br></span>                <span>int</span>[] temp = <span>new</span> <span>int</span>[last + <span>1</span>]; <span>//</span><span>声明数组（暂存左右子表的所有有序数列）：长度等于左右子表的长度之和。</span><span><br></span>                <span>int</span> tempIndex = <span>0</span>;<br>                <span>while</span> (indexA &lt;= mid &amp;&amp; indexB &lt;= last) <span>//</span><span>进行左右子表的遍历，如果其中有一个子表遍历完，则跳出循环</span><span><br></span>                {<br>                    <span>if</span> (array[indexA] &lt;= array[indexB]) <span>//</span><span>此时左子表的数 &lt;= 右子表的数</span><span><br></span>                    {<br>                        temp[tempIndex++] = array[indexA++];    <span>//</span><span>将左子表的数放入暂存数组中，遍历左子表下标++</span><span><br></span>                    }<br>                    <span>else</span><span>//</span><span>此时左子表的数 &gt; 右子表的数</span><span><br></span>                    {<br>                        temp[tempIndex++] = array[indexB++];    <span>//</span><span>将右子表的数放入暂存数组中，遍历右子表下标++</span><span><br></span>                    }<br>                }<br>                <span>//</span><span>有一侧子表遍历完后，跳出循环，将另外一侧子表剩下的数一次放入暂存数组中（有序）</span><span><br></span>                <span>while</span> (indexA &lt;= mid)<br>                {<br>                    temp[tempIndex++] = array[indexA++];<br>                }<br>                <span>while</span> (indexB &lt;= last)<br>                {<br>                    temp[tempIndex++] = array[indexB++];<br>                }<br><br>                <span>//</span><span>将暂存数组中有序的数列写入目标数组的制定位置，使进行归并的数组段有序</span><span><br></span>                tempIndex = <span>0</span>;<br>                <span>for</span> (<span>int</span> i = first; i &lt;= last; i++)<br>                {<br>                    array[i] = temp[tempIndex++];<br>                }<br>            }<br>            <span>catch</span> (Exception ex)<br>            { }<br>        }

复制代码

       对于N个元素的数组来说, 如此划分需要的层数是以2为底N的对数, 每一层中, 每一个元素都要复制到结果数组中, 并复制回来, 所以复制2N次, 那么对于归并排序,它的时间复杂度为O(N*logN), 而比较次数会少得多, 最少需要N/2次,最多为N-1次, 所以平均比较次数在两者之间. 它的主要问题还是在于在内存中需要双倍的空间.

发表于 更新于 分类于 ，

插入排序算法C#实现

Excerpt

插入排序算法主要分为：直接插入算法，折半排序算法（二分插入算法），希尔排序算法，后两种是直接插入算法的改良。因此直接插入算法是基础，这里先进行直接插入算法的分析与编码。直接插入算法的排序思想：假设有序数组从小到大为array[0],array[1],array[2],….,array[n-2],

插入排序算法主要分为：直接插入算法，折半排序算法（二分插入算法），希尔排序算法，后两种是直接插入算法的改良。因此直接插入算法是基础，这里先进行直接插入算法的分析与编码。

直接插入算法的排序思想：假设有序数组从小到大为array[0],array[1],array[2],….,array[n-2],array[n-1]，那么将待排数值array[n]与前面的有序数组从后向前依次比较，直到在有序数组中找到小于待排数值array[n]的位置，将array[n]插入到此位置，并入组合成新的有序数组。

直接插入算法--代码如下所示：

复制代码

1
<span>　　　　　//</span><span>直接插入排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）</span><span><br></span><span>　　　　　private </span><span>static </span><span>void</span><span> InsertSortionFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;   </span><span>//</span><span>临时变量，存储待排的数值</span><span><br></span><span>　　　　　　　　　for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>1</span><span>; i </span><span>&lt;</span><span> array.Length; i</span><span>++</span><span>)  </span><span>//</span><span>将无序的所有数值依次插入到有序数组中，注：下标从1开始，因为操作的是同一个数组</span><span><br></span><span>                {<br>                    temp </span><span>=</span><span> array[i];    </span><span>//</span><span>记录待插入前面有序数组的数值</span><span><br></span><span>　　　　　　　　　　　 int</span><span> index </span><span>=</span><span> i </span><span>-</span><span>1</span><span>;  </span><span>//</span><span>记录前方有序数组的末尾位置</span><span><br></span><span>　　　　　　　　　　　 while</span><span> (index </span><span>&gt;=</span><span>0</span><span>&amp;&amp;</span><span> array[index] </span><span>&gt;</span><span> temp)   </span><span>//</span><span>循环遍历前面的有序数组，并且从大到小依次与待排数值进行比较</span><span><br></span><span>                    {<br>                        array[index </span><span>+</span><span>1</span><span>] </span><span>=</span><span> array[index];    </span><span>//</span><span>如果index&gt;=0并且此时的值大于待排数值，将此处的值向后移动一位</span><span><br></span><span>                        index</span><span>--</span><span>;    </span><span>//</span><span>index--向前遍历有序数组</span><span><br></span><span>                    }<br>                    array[index </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp;    </span><span>//</span><span>由于前面的index--，所以temp插入的位置是index+1</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

复制代码

折半排序算法是对直接插入算法的一种优化，优化的核心是：通过折半查看有序数组中间位置的数值（a）与待插入的数值（temp）的大小，如果a>=temp，则转向折半的左区间继续折半查找； 如果a<temp，则转向折半后的右区间继续折半查找。直到左右下标相同时，此时折半的下标也指向相同的位置，再做最后一次循环，最终的结果是：左右下标相差1，并且原来左侧的下标指向大于temp的位置，原来右侧的下标指向了小于temp的位置，即：array[biggerIndex] < temp < array[smallerIndex]。

折半排序算法--代码如下：

复制代码

1
<span>  &nbsp;　　　</span><span>//</span><span>折半排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）</span>
1
<span>        private </span><span>static </span><span>void</span><span> BinaryInsertionSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> smallerIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录有序数组的起始位置</span><span><br></span><span>　　　　　　　　　 int</span><span> biggerIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录有序数组的终止位置</span><span><br></span><span>　　　　　　　　　 int</span><span> midIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录获取有序数组的中间位置（折半法的关键：折半的位置）</span><span><br></span><span>　　　　　　　　　 int</span><span> temp;  </span><span>//</span><span>记录带排的数值</span><span><br></span><span>　　　　　　　　　 for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>1</span><span>; i </span><span>&lt;</span><span> array.Length; i</span><span>++</span><span>)  </span><span>//</span><span>循环向有序数组中插入数值（i从1开始，因为操作的是同一个数组）</span><span><br></span><span>                {<br>                    temp </span><span>=</span><span> array[i];   </span><span>//</span><span>记录待插入有序数组的数值</span><span><br></span><span>                    biggerIndex </span><span>=</span><span> i </span><span>-</span><span>1</span><span>;<br>                    </span><span>//</span><span>当smallerIndex==biggerIndex时，进入最后一次循环：smallerIndex指向大于temp的数组位置，biggerIndex指向小于temp的数组位置</span><span><br></span><span>　　　　　　　　　　　 while</span><span> (smallerIndex </span><span>&lt;=</span><span> biggerIndex)   <br>                    {<br>                        midIndex </span><span>=</span><span> (smallerIndex </span><span>+</span><span> biggerIndex) </span><span>/</span><span>2</span><span>; </span><span>//</span><span>确定折半的位置</span><span><br></span><span>　　　　　　　　　　　　　　if</span><span>(array[midIndex] </span><span>&gt;=</span><span> temp)  </span><span>//</span><span>折半位置的数值 &gt;= temp</span><span><br></span><span>                        {<br>                            biggerIndex </span><span>=</span><span> midIndex </span><span>-</span><span>1</span><span>;    </span><span>//</span><span>biggerIndex以midIndex为基础向前移动一位</span><span><br></span><span>                        }<br>                        </span><span>else</span><span><br>                        {<br>                            smallerIndex </span><span>=</span><span> midIndex </span><span>+</span><span>1</span><span>;  </span><span>//</span><span>smallerIndex以midIndex为基础向后移动一位</span><span><br></span><span>                        }<br>                    }<br>                    </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span> i </span><span>-</span><span>1</span><span>; j </span><span>&gt;</span><span>biggerIndex; j</span><span>--</span><span>) </span><span>//</span><span>将有序数组中大于temp的数值分别向后移动一位</span><span><br></span><span>                    {<br>                        array[j </span><span>+</span><span>1</span><span>] </span><span>=</span><span> array[j];  </span><span>//<br></span><span>                    }<br>                    array[biggerIndex </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp;   </span><span>//</span><span>将temp插入biggerIndex + 1，因为此时array[biggerIndex]&lt;temp&lt;array[smallerIndex]</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

复制代码

希尔排序同样是直接插入排序算法的一种改进，基本思想是：将无序的数列划分为若干小的子序列，然后对子序列进行直接插入排序。
时间性能优于直接插入排序算法，但是一种不稳定的排序，时间复杂度为O(nlogn)。
希尔排序算法主要分为3重循环：
第一重循环–>按照gap的大小进行分组，初始化从array.Length/2开始，依次递减到1
第二重循环–>对所有分组进行排序
第三重循环–>组内进行直接插入排序

希尔排序算法--代码如下：

复制代码

1
<span>　　　　  private </span><span>static </span><span>void</span><span> ShellSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> length </span><span>=</span><span> array.Length;<br>                </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;<br>                </span><span>for</span><span> (</span><span>int</span><span> gap </span><span>=</span><span> length </span><span>/</span><span>2</span><span>; gap </span><span>&gt;</span><span>0</span><span>; gap</span><span>--</span><span>)  </span><span>//</span><span>第一重循环，按照gap的大小进行分组</span><span><br></span><span>                {<br>                    </span><span>for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>0</span><span>; i </span><span>&lt;</span><span> gap; i</span><span>++</span><span>)   </span><span>//</span><span>第二重循环，对所有分组进行排序</span><span><br></span><span>                    {<br>                        </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span> i; j </span><span>&lt;</span><span> length; j </span><span>=</span><span> j </span><span>+</span><span> gap)    </span><span>//</span><span>第三重循环，组内进行直接插入排序</span><span><br></span><span>                        {<br>                            temp </span><span>=</span><span> array[j];<br>                            </span><span>int</span><span> index </span><span>=</span><span> j </span><span>-</span><span> gap;<br>                            </span><span>while</span><span> (index </span><span>&gt;=</span><span>0</span><span>&amp;&amp;</span><span> array[index] </span><span>&gt;</span><span> temp)<br>                            {<br>                                array[index </span><span>+</span><span> gap] </span><span>=</span><span> array[index];<br>                                index </span><span>=</span><span> index </span><span>-</span><span> gap;<br>                            }<br>                            array[index </span><span>+</span><span> gap] </span><span>=</span><span> temp;<br>                        }<br>                    }<br>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }</span>

复制代码

。。。。

发表于 更新于 分类于

安装

1
2
3
4
5
6
7
8
9

sudo apt install lm-sensors curl hddtemp  # 安装工具

sensors-detect # 检测传感器

sudo apt install conky # 安装

conky & # 运行conky

传感器数据样例

1
2
3
4
5
6
7
8
9
acpitz-virtual-0-
Adapter: Virtual device
temp1: +49.5°C (crit = +99.0°C)

coretemp-isa-0000
Adapter: ISA adapter
Physical id 0: +49.0°C (high = +100.0°C, crit = +100.0°C)
Core 0: +49.0°C (high = +100.0°C, crit = +100.0°C)
Core 1: +49.0°C (high = +100.0°C, crit = +100.0°C)

:TODO conky 默认运行效果截图

conky默认以一个弹窗的形式运行，并使用位于/etc/conky/conky.conf的基础配置文件

集成到桌面

1
2
cp /etc/conky/conky.conf /home/$USER/.conkyrc # 复制默认配置文件

发表于 更新于 分类于

添加删除

1
2
3
4
5
6
7
8
9
10
11
12
13
# 查看虚拟机
virsh list --all

# 创建虚拟机
virt-install -virt-type=kvm --name={虚拟机名} --vcpus=4 \
    --memory=1024 --location={iso文件} \
    --disk path={虚拟机硬盘存放路径}.qcow2,size=30,format=qcow2 \
    --network bridge=virbr0 --graphics none --extra-args='console=ttyS0'
    --force

# 删除虚拟机
virsh undefine {虚拟机名}

开关机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 开启虚拟机
virsh start {虚拟机名}

# 关闭虚拟机
virsh shutdown {虚拟机名}

# 强制关机
virsh destroy {虚拟机名}

# 挂起虚拟机
virsh suspend {虚拟机名}

# 恢复挂起的
virsh resume {虚拟机名}

# 设置虚拟机和物理机开机一起启动
virsh autostart {虚拟机名}

# 取消虚拟机开机启动
virsh autostart {虚拟机名}

备份克隆

1
2
3
4
5
6
7
8
9
10
11
12
13

# 通过配置文件启动
virsh create /etc/libvirt/qemu/{虚拟机名}.xml

# 备份虚拟机配置文件
virsh dumpxml {虚拟机名} > {存储路径}

# 恢复备份虚拟机
virsh create {虚拟机名}

# 虚拟机克隆
virt-clone -o {虚拟机名} -n localhost -f /virtual/KVM/{虚拟机名}.qcow2

快照

1
2
3
4
5
6
7
8
9
10
11
# 创建快照
virsh snapshot-create {虚拟机名}

# 查看快照
virsh snapshot-list {虚拟机名}

# 恢复快照
virsh snapshot-revert {虚拟机名} {快照名称}

# 删除快照
virsh snapshot-delete {虚拟机名} {快照名称}

发表于 更新于

使用markdown的链接语法

使用markdown的语法指定url创建站内链接，有绝对地址和相对地址两种方式，绝对地址与相对地址的区别在于是否以/开头：

使用绝对地址

代码如下：

1
2
# 格式 [标题](文章地址)
[Hexo 增加站内文章链接](/Hexo博客/Hexo-增加站内文章链接)

示例中，Hexo-增加站内文章链接使用的是文章对应的md文件名，使用hexo n创建post时，空格会转换为中划线-。/Hexo是为了文章管理方便在_posts目录下增加的子目录，Hexo-增加站内文章链接.md位于_posts/Hexo/目录下。

结果如下：

Hexo 增加站内文章链接

Hexo对绝对地址和相对地址的处理方式是不一样的。对于绝对地址/Hexo/Hexo-博客配置，生成的目标url不会变化。

使用相对地址

代码如下：

1
[Hexo 增加站内文章链接](Hexo/Hexo-增加站内文章链接)

对于相对地址Hexo/Hexo-增加站内文章链接，生成的目标URL会叠加文章的的URL，结果是/Hexo/Hexo/Hexo-增加站内文章链接，这显然不是期望的结果。但是如果是文章内的锚点链接，使用这种方式非常合适。

代码如下：

1
2
# 格式 [标题](#文章内要跳转的标题)
[测试文章内跳转锚点](#测试文章内跳转锚点)

结果如下：
跳转文章内测试锚点

生成的URL可以正确的跳转到文章内的锚点。注意，标题中的空格用-代替。

使用post_link标签

由于Hexo文章的URL规则是可以配置的，在_config.yml中可以配置URL自动添加日期、目录等信息。如果使用markdown语法的链接规则多有不便，一方面需要知道目标URL，一方面如果规则修改或者站点迁移，对应的内容需要修改。

好在Hexo提供了post_link标签解决这个问题。

代码如下：

1
2
# 格式 {% post_link 以_post下文件路径 '显示链接名'%}
{% post_link Hexo博客/Hexo-博客配置 'Hexo 博客配置' %}

示例中，Hexo-博客配置使用的是文章对应的md文件名，使用hexo n创建post时，空格会转换为中划线-。Hexo是为了文章管理方便在_posts目录下增加的子目录，Hexo-博客配置.md位于_posts/Hexo目录下。

结果如下：

Hexo 博客配置

这样的链接会自动适配_config.yml中的文章URL规则。

小结

对比markdown语法和post_link标签，推荐在文章链接到站内文章时优先使用post_link，链接到文章内锚点时优先使用markdown语法。

测试文章内跳转锚点

文章内锚点跳转示例

发表于 更新于 分类于 ，

使用 Visual Studio 2022 创建 ASP.NET Core Web API

可以从 Visual Studio 2022 中选择 ASP.NET Core Web API 或 ASP.NET Core gRPC模板

安装依赖库,可以使用NuGet安装或使用DotNet CLI

1
2
3
4
dotnet add package Microsoft.EntityFrameworkCore.SqlServer --version 6.0.33
dotnet add package Microsoft.EntityFrameworkCore.Tools --version 6.0.33
dotnet add package Microsoft.AspNetCore.Identity.EntityFrameworkCore --version 6.0.33
dotnet add package Microsoft.AspNetCore.Authentication.JwtBearer --version 6.0.33

在appsettings.json中添加配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
{
    "Logging": {
        "LogLevel": {
            "Default": "Information",
            "Microsoft.AspNetCore": "Warning"
        }
    },
    "AllowedHosts": "*",
    "Database": {
        "Driver": "SqlServer",
        "Host": "127.0.0.1",
        "Port": 6543,
        "DbName": "SAMPLE",
        "User": "postgres",
        "Password": "postgres"
    },
    "Jwt": {
        "Audience": "",
        "Issuer": "",
        "Secret": ""
    }
}

准备Model

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
using Microsoft.AspNetCore.Identity;

namespace Samples.Identity.Model

public class Role : IdentityRole<int>
{

}

public class RoleClaim : IdentityRoleClaim<int>
{

}

public class User : IdentityUser<int>
{

}

public class UserClaim : IdentityUserClaim<int>
{

}

public class UserLogin : IdentityUserLogin<int>
{

}

public class UserRole : IdentityUserRole<int>
{

}

public class UserToken : IdentityUserToken<int>
{

}

Fluent API重定义数据库表名，字段

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
using Sample.Identity.Model;
using Microsoft.EntityFrameworkCore;
using Microsoft.EntityFrameworkCore.Metadata.Builders;

namespace Samples.Identity.Configurations;

public class RoleClaimConfiguration : IEntityTypeConfiguration<RoleClaim>
{
    public void Configure(EntityTypeBuilder<RoleClaim> builder)
    {
        builder.ToTable("SYS_ROLE_CLAIM").HasKey(x => x.Id);
        builder.Property(x => x.Id).HasColumnName("ID").ValueGeneratedOnAdd();
        builder.Property(x => x.RoleId).HasColumnName("ROLE_ID");
        builder.Property(x => x.ClaimType).HasColumnName("CLAIM_TYPE").HasMaxLength(50);
        builder.Property(x => x.ClaimType).HasColumnName("CLAIM_VALUE").HasMaxLength(50);
    }
}

public class RoleConfiguration : IEntityTypeConfiguration<Role>
{
    public void Configure(EntityTypeBuilder<Role> builder)
    {
        builder.ToTable("SYS_ROLE").HasKey(x => x.Id);
        builder.Property(x => x.Id).HasColumnName("ID").ValueGeneratedOnAdd();
        builder.Property(x => x.Name).HasColumnName("NAME").HasMaxLength(50);
        builder.Property(x => x.NormalizedName).HasColumnName("NORMALIZED_NAME").HasMaxLength(50);
        builder.Property(x => x.ConcurrencyStamp).HasColumnName("CONCURRENCY_STAMP").HasMaxLength(50);

        builder.HasData(new Role { Id = 1, Name = "SuperAdmin", NormalizedName = "超级管理员" });
        builder.HasData(new Role { Id = 2, Name = "Admin", NormalizedName = "管理员" });
        builder.HasData(new Role { Id = 3, Name = "Operator", NormalizedName = "操作员" });
    }
}

public class UserClaimConfiguration : IEntityTypeConfiguration<UserClaim>
{
    public void Configure(EntityTypeBuilder<UserClaim> builder)
    {
        builder.ToTable("SYS_USER_CLAIM").HasKey(x => x.Id);
        builder.Property(x => x.Id).HasColumnName("ID").ValueGeneratedOnAdd();
        builder.Property(x => x.UserId).HasColumnName("USER_ID");
        builder.Property(x => x.ClaimType).HasColumnName("CLAIM_TYPE").HasMaxLength(50);
        builder.Property(x => x.ClaimValue).HasColumnName("CLAIM_VALUE").HasMaxLength(50);
    }
}

public class UserConfiguration : IEntityTypeConfiguration<User>
{
    public void Configure(EntityTypeBuilder<User> builder)
    {
        builder.ToTable("SYS_USER").HasKey(x => x.Id);
        builder.Property(x => x.Id).HasColumnName("ID").ValueGeneratedOnAdd();
        builder.Property(x => x.UserName).HasColumnName("USERNAME").HasMaxLength(20);
        builder.Property(x => x.NormalizedUserName).HasColumnName("NORMALIZED_USERNAME").HasMaxLength(20);
        builder.Property(x => x.Email).HasColumnName("EMAIL").HasMaxLength(50);
        builder.Property(x => x.NormalizedEmail).HasColumnName("NORMALIZED_EMAIL").HasMaxLength(50);
        builder.Property(x => x.EmailConfirmed).HasColumnName("EMAIL_CONFIRMED");
        builder.Property(x => x.PasswordHash).HasColumnName("PASSWORD_HASH").HasMaxLength(256);
        builder.Property(x => x.SecurityStamp).HasColumnName("SECURITY_STAMP").HasMaxLength(256);
        builder.Property(x => x.ConcurrencyStamp).HasColumnName("CONCURRENCY_STAMP").HasMaxLength(256);
        builder.Property(x => x.PhoneNumber).HasColumnName("PHONE_NUMBER").HasMaxLength(15);
        builder.Property(x => x.PhoneNumberConfirmed).HasColumnName("PHONE_NUMBER_CONFIRMED");
        builder.Property(x => x.TwoFactorEnabled).HasColumnName("TWO_FACTOR_ENABLED");
        builder.Property(x => x.LockoutEnd).HasColumnName("LOCKOUT_END");
        builder.Property(x => x.LockoutEnabled).HasColumnName("LOCKOUT_ENABLED");
        builder.Property(x => x.AccessFailedCount).HasColumnName("ACCESS_FAILED_COUNT");

        builder.HasData(new User
        {
            Id = 1,
            UserName = "admin",
            NormalizedUserName = "ADMIN",
            PasswordHash = "AQAAAAEAACcQAAAAELR93lThWhjLUaJtEMPGJXUR88rGK9RjjZytUhr0Jfy3J7JaObJCZAcu5MhPl39erg==",
            SecurityStamp = "LA4OVIYIUDB7CB44WR4CTS6FCY4VRWSO",
        });
    }
}

public class UserLoginConfiguration : IEntityTypeConfiguration<UserLogin>
{
    public void Configure(EntityTypeBuilder<UserLogin> builder)
    {
        builder.ToTable("SYS_USER_LOGIN");
        builder.Property(x => x.LoginProvider).HasColumnName("LOGIN_PROVIDER").HasMaxLength(20);
        builder.Property(x => x.ProviderKey).HasColumnName("PROVIDER_KEY").HasMaxLength(20);
        builder.Property(x => x.ProviderDisplayName).HasColumnName("PROVIDER_DISPLAY_NAME").HasMaxLength(20);
        builder.Property(x => x.UserId).HasColumnName("USER_ID");
    }
}

public class UserRoleConfiguration : IEntityTypeConfiguration<UserRole>
{
    public void Configure(EntityTypeBuilder<UserRole> builder)
    {
        builder.ToTable("SYS_USER_ROLE");
        builder.Property(x => x.UserId).HasColumnName("USER_ID");
        builder.Property(x => x.RoleId).HasColumnName("ROLE_ID");
    }
}

public class UserTokenConfiguration : IEntityTypeConfiguration<UserToken>
{
    public void Configure(EntityTypeBuilder<UserToken> builder)
    {
        builder.ToTable("SYS_USER_TOKEN");
        builder.Property(x => x.UserId).HasColumnName("USER_ID");
        builder.Property(x => x.LoginProvider).HasColumnName("LOGIN_PROVIDER").HasMaxLength(20);
        builder.Property(x => x.Name).HasColumnName("NAME").HasMaxLength(50);
        builder.Property(x => x.Value).HasColumnName("VALUE").HasMaxLength(256);
    }
}

新建DataContext

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
using Microsoft.AspNetCore.Identity.EntityFrameworkCore;
using Microsoft.AspNetCore.Identity;
using Microsoft.EntityFrameworkCore;

namespace Samples.Identity;

public class DataContext: IdentityDbContext<User>
{
    public DataContext(DbContextOptions<DataContext> options)
        : base(options)
    {
            
    }
    
    protected override void OnModelCreating(ModelBuilder builder)
    {
        base.OnModelCreating(builder);
        builder.ApplyConfiguration(new UserConfiguration());
        builder.ApplyConfiguration(new RoleConfiguration());
        builder.ApplyConfiguration(new UserClaimConfiguration());
        builder.ApplyConfiguration(new UserRoleConfiguration());
        builder.ApplyConfiguration(new UserLoginConfiguration());
        builder.ApplyConfiguration(new RoleClaimConfiguration());
        builder.ApplyConfiguration(new UserTokenConfiguration());
    }
}

添加ViewModel

1
2
3
4
5
6
7
8
9
10
11
12
using System.ComponentModel.DataAnnotations;

namespace Sample.Identity.ViewModels;

public class LoginViewModel
{
    [Required(ErrorMessage = "用户名不能为空")]
    public string? Username { get; set; }
    
    [Required(ErrorMessage = "密码不能为空")]
    public string? Password { get; set; }
}

添加Controller

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
using Sample.Identity.ViewModels;
using Microsoft.AspNetCore.Identity;
using Microsoft.AspNetCore.Mvc;
using Microsoft.AspNetCore.Tokens;
using System.IdentityModel.Tokens.Jwt;
using System.Security.Claims;
using System.Text;

namespace Sample.Identity.Controllers;

[Route("api/[controller]")]
[ApiController]
public class AuthenticateController : ControllerBase
{
    private readonly UserManager<User> m_userManager;
    private readonly RoleManager<Role> m_roleManager;
    private readonly IConfiguration m_configuration;
    
    private readonly JwtOption m_jwtOptions;
    
    public AuthenticateController(UserManager<User> userManager,
                                 RoleManager<Role> roleManager,
                                 IConfiguration configuration)
    {
    	m_userManager = userManager;
        m_roleManager = roleManager;
        m_configuration = configuration;
        
        m_jwtOptions = m_configuration.GetSection("").Get<JwtOption>();
    }
    
    [HttpPost]
    [Route("login")]
    public async Task<IActionResult> Login([FromBody] LoginViewModel model)
    {
        var user = await m_userManager.FindByNameAsync(model.Username);
        if(user!=null && await m_userManager.CheckPasswordAsync(user, model.Password))
        {
            var roles = await m_userManager.GetRolesAsync(user);
            
            var claims = new List<Claim>
            {
                new Claim(ClaimTypes.Name, user.Username);
                new Claim(JwtRegisteredClaimNames.Jti, Guid.NewGuid().ToString())
            }
            
            foreach (var role in roles)
            {
                claims.Add(new Claim(ClaimTypes.Role, role));
            }
            
            var token = GenerateToken(claims);
            
            return Ok(new {
               token = new JwtSecurityTokenHandler().WriteToken(token),
                expiration = token.ValidTo
            });
        }
        
        return Unauthorized();
    }
    
    private JwtSecurityToken GetToken(List<Claim> authClaims)
    {
        var authSigningKey = new SymmetricSecurityKey(Encoding.UTF8.GetBytes(m_jwtOptions.Secret));
        var token = new JwtSecurityToken(
                issuer: _configuration["JWT:ValidIssuer"],
                audience: _configuration["JWT:ValidAudience"],
                expires: DateTime.Now.AddHours(3),
                claims: authClaims,
                signingCredentials: new SigningCredentials(authSigningKey, SecurityAlgorithms.HmacSha256)
            );
 
            return token;
    }
}

修改Program中添加

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
using Sample.Identity;
using Microsoft.AspNetCore.Authentication.JwtBearer;
using Microsoft.AspNetCore.Identity;
using Microsoft.EntityFrameworkCore;
using Microsoft.IdentityModel.Tokens;
using System.Text;
 
var builder = WebApplication.CreateBuilder(args);
ConfigurationManager configuration = builder.Configuration;
 
// Add services to the container.
 
// For Entity Framework
builder.Services.AddDbContext<ApplicationDbContext>(options => options.UseSqlServer(configuration.GetConnectionString("ConnStr")));
 
// For Identity
builder.Services.AddIdentity<User, Role>() 
//optinos => {
//options.Password.RequireDigit = false;
//options.Password.RequireLowercase = false;
//options.Password.RequireUppercase = false;
//options.Password.RequireNonAlphanumeric = false;
//options.Password.RequiredLength = 8;
//options.Password.RequiredUniqueChars = 1;

//options.Lockout.DefaultLockoutTimeSpan = TimeSpan.FromMinutes(10);
//options.Lockout.MaxFailedAccessAttempts = 5;
//options.Lockout.AllowedForNewUsers = true;
//}
    .AddEntityFrameworkStores<DataContext>()
    .AddDefaultTokenProviders();
 
 var jwtOptions = builder.Configuration.GetSection("JWT").Get<JwtOption>();
 
// Adding Authentication
builder.Services.AddAuthentication(options =>
{
    options.DefaultAuthenticateScheme = JwtBearerDefaults.AuthenticationScheme;
    options.DefaultChallengeScheme = JwtBearerDefaults.AuthenticationScheme;
    options.DefaultScheme = JwtBearerDefaults.AuthenticationScheme;
})
 
// Adding Jwt Bearer
.AddJwtBearer(options =>
{
    options.SaveToken = true;
    options.RequireHttpsMetadata = false;
    options.TokenValidationParameters = new TokenValidationParameters()
    {
        ValidateIssuer = true,
        ValidateAudience = true,
        ValidAudience = jwtOptions.Audience,
        ValidIssuer = jwtOptions.Issuer,
        IssuerSigningKey = new SymmetricSecurityKey(Encoding.UTF8.GetBytes(jwtOptions.Secret))
    };
});
 
builder.Services.AddControllers();
// Learn more about configuring Swagger/OpenAPI at https://aka.ms/aspnetcore/swashbuckle
builder.Services.AddEndpointsApiExplorer();
builder.Services.AddSwaggerGen();
 
var app = builder.Build();
 
// Configure the HTTP request pipeline.
if (app.Environment.IsDevelopment())
{
    app.UseSwagger();
    app.UseSwaggerUI();
}
 
app.UseHttpsRedirection();
 
// Authentication & Authorization
app.UseAuthentication();
app.UseAuthorization();
 
app.MapControllers();
 
app.Run();

执行数据迁移

1
2
add-migration L0
update-database
0%