归并排序

 1         /// <summary>
 2         /// 归并排序_合并
 3         /// </summary>
 4         /// <param name="v"></param>
 5         /// <param name="first"></param>
 6         /// <param name="mid"></param>
 7         /// <param name="last"></param>
 8         public static int[] Merger(int[] v, int first, int mid, int last)
 9         {
10             Queue<int> tempV = new Queue<int>();
11             int indexA, indexB;
12             //设置indexA，并扫描subArray1 [first,mid]
13             //设置indexB, 并扫描subArray2 [mid,last]
14             indexA = first;
15             indexB = mid;
16             //在没有比较完两个子标的情况下，比较 v[indexA]和v[indexB]
17             //将其中小的放到临时变量tempV中
18             while (indexA < mid && indexB < last)
19             {
20                 if (v[indexA] < v[indexB])
21                 {
22                     tempV.Enqueue(v[indexA]);
23                     indexA++;
24                 }
25                 else
26                 {
27                     tempV.Enqueue(v[indexB]);
28                     indexB++;
29                 }
30             }
31             //复制没有比较完子表中的元素
32             while (indexA < mid)
33             {
34                 tempV.Enqueue(v[indexA]);
35                 indexA++;
36             }
37             while (indexB < last)
38             {
39                 tempV.Enqueue(v[indexB]);
40                 indexB++;
41             }
42             int index = 0;
43             while (tempV.Count > 0)
44             {
45                 v[first + index] = tempV.Dequeue();
46                 index++;
47             }
48             return v;
49         }
50 
51         /// <summary>
52         /// 归并算法
53         /// 原理：把原始数组分成若干子数组,对每一个子数组进行排序,
54         ///       继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组
55         /// </summary>
56         /// <param name="v"></param>
57         /// <param name="first"></param>
58         /// <param name="last"></param>
59         public static int[] MergerSort(int[] v, int first, int last)
60         {
61             if (first + 1 < last)
62             {
63                 int mid = (first + last) / 2;
64                 MergerSort(v, first, mid);  //数组前一半
65                 MergerSort(v, mid, last);   //数组后一半
66                 v = Merger(v, first, mid, last);  //合并子序列
67             }
68             return v;
69         }
工欲善其事，必先利其器。