C#算法基础之递归排序

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace ConsolePractice
  8 {
  9     class CArray
 10     {
 11         private int[] arr;
 12         //数组大小
 13         private int upper;
 14         //下标
 15         private int numElements;
 16 
 17         /// <summary>
 18         /// 初始化数组参数
 19         /// </summary>
 20         /// <param name="size"></param>
 21         public CArray(int size)
 22         {
 23             arr = new int[size];
 24             upper = size - 1;
 25             numElements = 0;
 26         }
 27 
 28         /// <summary>
 29         /// 插入方法
 30         /// </summary>
 31         /// <param name="item">存储的数</param>
 32         public void Insert(int item)
 33         {
 34             arr[numElements] = item;
 35             numElements++;
 36         }
 37 
 38         /// <summary>
 39         /// 输出方法
 40         /// </summary>
 41         public void DisplayElements()
 42         {
 43             for (int i = 0; i <= upper; i++)
 44             {
 45                 Console.Write(arr[i] + " ");
 46             }
 47             Console.WriteLine();
 48         }
 49 
 50         /// <summary>
 51         /// 清除数组
 52         /// </summary>
 53         public void Clear()
 54         {
 55             for (int i = 0; i <= upper; i++)
 56             {
 57                 arr[i] = 0;
 58             }
 59             numElements = 0;
 60         }
 61 
 62         #region 递归排序算法
 63         /// <summary>
 64         /// 递归排序合并两个子集的方法
 65         /// </summary>
 66         /// <param name="tempArray">临时数组</param>
 67         /// <param name="lowp">子集1的下标</param>
 68         /// <param name="highp">子集2的下标，同时可以计算出子集1的长度</param>
 69         /// <param name="ubound">子集2的长度</param>
 70         public void Merge(int[] tempArray, int lowp, int highp, int ubound)
 71         {
 72             //主数组arr的初始下标位置
 73             int lbound = lowp;
 74             //子集1的长度
 75             int mid = highp - 1;
 76             //主数组arr的长度
 77             int n = (ubound - lbound) + 1;
 78 
 79             int j = 0;
 80             //3个while的作用是合并子集1和子集2到临时的数组中
 81             while ((lowp <= mid) && (highp <= ubound))
 82             {
 83                 if (arr[lowp] < arr[highp])
 84                 {
 85                     tempArray[j] = arr[lowp];
 86                     lowp++;
 87                     j++;
 88                 }
 89                 else
 90                 {
 91                     tempArray[j] = arr[highp];
 92                     highp++;
 93                     j++;
 94                 }
 95             }
 96             //子集1还留有数值时
 97             while (lowp <= mid)
 98             {
 99                 tempArray[j] = arr[lowp];
100                 j++;
101                 lowp++;
102             }
103             //子集2还留有数值时
104             while (highp <= ubound)
105             {
106                 tempArray[j] = arr[highp];
107                 j++;
108                 highp++;
109             }
110 
111             //将临时数组存储的数值替换主数组的数值。
112             for (j = 0; j <= n - 1; j++)
113             {
114                 arr[lbound + j] = tempArray[j];
115             }
116 
117             this.DisplayElements();
118         }
119 
120         /// <summary>
121         /// 递归方法
122         /// </summary>
123         /// <param name="tempArray">临时数组</param>
124         /// <param name="lbound">数组的最小下标</param>
125         /// <param name="ubound">数组的最大下标</param>
126         public void RecMergeSort(int[] tempArray, int lbound, int ubound)
127         {
128             if (lbound == ubound)
129                 return;
130             else
131             {
132                 //求出中间的下标
133                 int mid = (int)(lbound + ubound) / 2;
134                 //子集1的递归
135                 RecMergeSort(tempArray, lbound, mid);
136                 //子集2的递归
137                 RecMergeSort(tempArray, mid + 1, ubound);
138                 //合并子集1和子集2
139                 Merge(tempArray, lbound, mid + 1, ubound);
140             }
141         }
142 
143         /// <summary>
144         /// 调用递归排序算法
145         /// </summary>
146         public void MergeSort()
147         {
148             int[] tempArray = new int[numElements];
149             RecMergeSort(tempArray,0,numElements-1);
150         }
151         #endregion
152     }
153 
154     class C_shape
155     {
156         static void Main()
157         {
158             CArray nums = new CArray(10);
159             Random rnd = new Random(100);
160             for (int i = 0; i < 10; i++)
161             {
162                 nums.Insert(rnd.Next(0, 100));
163             }
164             Console.WriteLine("Before sorting:");
165             nums.DisplayElements();
166             Console.WriteLine("During sorting:");
167             nums.MergeSort();
168             Console.WriteLine("After sorting:");
169             nums.DisplayElements();
170             Console.ReadKey();
171         }
172     }
173 }
运行结果：