网站设计公司建设网站,凡客建站网,网站建设手机端页面模板,网易企业邮箱客户端设置算法定义 合并排序是一种递归算法#xff0c;思路如下#xff1a; 如果源数组长度为 1#xff0c;立即返回。将源数组平分为两个新数组#xff1a;Left 和 Right。对 Left 执行递归排序。对 Right 执行递归排序。将排序后的 Left 和 Right 执行合并到原数组。可以看出来思路如下 如果源数组长度为 1立即返回。将源数组平分为两个新数组Left 和 Right。对 Left 执行递归排序。对 Right 执行递归排序。将排序后的 Left 和 Right 执行合并到原数组。可以看出来改算法的重点是已排序数组的合并过程。 算法举例 【54321】 【543】【21】 【54】【3】【21】 【5】【4】【3】【21】 【45】【3】【21】 【345】【21】 【345】【2】【1】 【345】【12】 【12345】 算法实现 1 using System;2 using System.Collections.Generic;3 using System.Linq;4 using System.Text;5 using System.Threading.Tasks;6 7 namespace DataStuctureStudy.Sorts8 {9 class MergeSortT
10 where T : IComparableT
11 {
12 private static void Swap(T[] items, int left, int right)
13 {
14 if (left ! right)
15 {
16 var temp items[left];
17 items[left] items[right];
18 items[right] temp;
19 }
20 }
21
22 public static void Sort(T[] items)
23 {
24 if (items.Length 2)
25 {
26 return;
27 }
28
29 int leftSize items.Length / 2;
30 int rightSize items.Length - leftSize;
31
32 T[] left new T[leftSize];
33 T[] right new T[rightSize];
34
35 Array.Copy(items, 0, left, 0, leftSize);
36 Array.Copy(items, leftSize, right, 0, rightSize);
37
38 Sort(left);
39 Sort(right);
40 Merge(items, left, right);
41 }
42
43 private static void Merge(T[] items, T[] left, T[] right)
44 {
45 var leftIndex 0;
46 var rightIndex 0;
47
48 for (var i 0; i items.Length; i)
49 {
50 if (leftIndex left.Length)
51 {
52 items[i] right[rightIndex];
53 rightIndex;
54 }
55 else if (rightIndex right.Length)
56 {
57 items[i] left[leftIndex];
58 leftIndex;
59 }
60 else if (left[leftIndex].CompareTo(right[rightIndex]) 0)
61 {
62 items[i] left[leftIndex];
63 leftIndex;
64 }
65 else
66 {
67 items[i] right[rightIndex];
68 rightIndex;
69 }
70 }
71 }
72 }
73 } 合并过程 已排序数组的合并过程比较有意思分别对 Left 和 Right 维护一个从左到右的指针分别是leftIndex 和 RightIndex当填充目标数组的第 i 个元素时需要从 Left 和 Right 中找到剩余元素指针到末尾部分的元素的最小值因为是已排序数组只需比较 Left[LeftIndex] 和 Right[RightIndex] 的大小将最小的元素填充到目标数组的第 i 个位置即可然后相应的指针加 1。 转载于:https://www.cnblogs.com/happyframework/p/3464645.html
