6大排序算法，c#实现

  1 using System;
  2 using System.Text;
  3 using System.Collections.Generic;
  4 
  5 namespace ArithmeticPractice
  6 {
  7     static class ExtendsFunction 
  8     {
  9         public static string printArray(this Array p_arr) 
 10         {
 11             StringBuilder sb = new StringBuilder("[ ");
 12             for(int i = 0 ; i < p_arr.Length ; i++) 
 13             {
 14                 if(i != 0) 
 15                 {
 16                     sb.Append(", ");
 17                 }
 18                 sb.Append(p_arr.GetValue(i));
 19             }
 20             sb.Append (" ]");
 21             return sb.ToString ();
 22         }
 23     }
 24     class MainClass
 25     {
 26         public static void Main (string[] args)
 27         {
 28             int[] arr = new int[]{49, 38, 65, 97, 76, 13, 27, 49};
 29             int[] sortedArr = null;
 30             while(true) 
 31             {
 32                 Console.WriteLine ("请选择算法(从小到大排序)：
0.退出 1.冒泡排序 2.选择排序 3.插入排序 4.希尔排序 5.快速排序 6.堆排序");
 33                 string choose = Console.ReadLine ();
 34 
 35                 Console.WriteLine("排序前：" + arr.printArray());
 36                 switch(choose) {
 37                 case "1":
 38                     sortedArr = bubbleSort(arr);
 39                     break;
 40                 case "2":
 41                     sortedArr = chooseSort(arr);
 42                     break;
 43                 case "3":
 44                     sortedArr = insertSort(arr);
 45                     break;
 46                 case "4":
 47                     sortedArr = shellSort(arr);
 48                     break;
 49                 case "5":
 50                     sortedArr = quickSort(arr);
 51                     break;
 52                 case "6":
 53                     sortedArr = heapSort(arr);
 54                     break;
 55                 default:
 56                     return;
 57                 }
 58                 Console.WriteLine("排序后：" + sortedArr.printArray());
 59             }
 60         }
 61         /// <summary>
 62         /// 冒泡排序
 63         /// </summary>
 64         /// <param name="p_arr">P_arr.</param>
 65         private static int[] bubbleSort(int[] p_arr) 
 66         {
 67             for(int i = p_arr.Length - 1; i > 0 ; i--)
 68             {
 69                 for(int j = p_arr.Length - 1; j > p_arr.Length - i - 1 ; j--) 
 70                 {
 71                     if(p_arr[j - 1] > p_arr[j] )
 72                     {
 73                         int temp = p_arr[j];
 74                         p_arr[j] = p_arr[j - 1];
 75                         p_arr[j - 1] = temp;
 76                     }
 77                 }
 78             }
 79             return p_arr;
 80         }
 81         /// <summary>
 82         /// 选择排序
 83         /// </summary>
 84         /// <param name="p_arr">P_arr.</param>
 85         private static int[] chooseSort(int[] p_arr)
 86         {
 87             for(int i = 0; i < p_arr.Length ; i++) 
 88             {
 89                 var l_min = p_arr[i];
 90                 for(int j = i + 1; j < p_arr.Length; j++)
 91                 {
 92                     if(l_min > p_arr[j]) 
 93                     {
 94                         l_min = p_arr[j];
 95                         p_arr[j] = p_arr[i];
 96                         p_arr[i] = l_min;
 97                     }
 98                 }
 99             }
100             return p_arr;
101         }
102         /// <summary>
103         /// 插入排序
104         /// </summary>
105         /// <returns>The sort.</returns>
106         /// <param name="p_arr">P_arr.</param>
107         private static int[] insertSort(int[] p_arr)
108         {
109             List<int> list = new List<int> ();
110             list.Add (p_arr [0]);
111             for (int i = 1; i < p_arr.Length; i++) 
112             {
113                 int j = 0;
114                 for(; j < list.Count ; j++) 
115                 {
116                     if(p_arr[i] < list[j]) 
117                     {
118                         list.Insert(j, p_arr[i]);
119                         break;
120                     }
121                 }
122                 if(j == list.Count) 
123                 {
124                     list.Add(p_arr[i]);
125                 }
126             }
127             return list.ToArray ();
128         }
129         /// <summary>
130         /// 希尔排序
131         /// </summary>
132         /// <returns>The sort.</returns>
133         /// <param name="p_arr">P_arr.</param>
134         private static int[] shellSort(int[] p_arr)
135         {
136             int l_cache;//用来缓存符合交换条件的那一个（这里缓存小的，因为排序是从小到大）
137             int l_space = p_arr.Length;// 交换的间隔，人称增量
138             while(l_space > 1){
139                 l_space = l_space/3 + 1;// 间隔缩小，最后一定要是1，所以不能space/2+1
140                 for(int index = l_space; index < p_arr.Length; index++) 
141                 {
142                     if(p_arr[index] < p_arr[index - l_space])//当前index和index-space的需要进行交换
143                     {
144                         l_cache = p_arr[index];//缓存最小的那个
145                         int j;
146                         //*进行一次必然为true的判断，把index的值设置为前面比较大的那个，然后在往前去看看间隔为space的位置的数(假定为temp)，有没有比cache的还要大的，（cache的值不变）如果有的话就设置当前位置（不是index而是j+space）设置为假定为temp，然后继续往前看
147                         for(j = index - l_space; j >= 0 && l_cache < p_arr[j]; j -= l_space) 
148                         {
149                             p_arr[j + l_space] = p_arr[j];
150                         }
151                         p_arr[j + l_space] = l_cache;
152                     }
153                 }
154             }
155             return p_arr;
156         }
157         /// <summary>
158         /// 快速排序
159         /// </summary>
160         /// <returns>The sort.</returns>
161         /// <param name="p_arr">P_arr.</param>
162         private static int[] quickSort(int[] p_arr, int p_left = 0, int p_right = 0) 
163         {
164             int l_left = p_left;
165             int l_right = p_right;
166             if(l_right == 0) 
167             {
168                 l_right = p_arr.Length - 1;
169                 p_right = p_arr.Length - 1;
170             }
171             if (l_right > 0) 
172             {
173                 int l_middle = p_arr[ (l_left + l_right) / 2];//中值，不一定为最中间，仅仅作为一个判断依据，是最小或者最大的都无所谓
174                 Console.WriteLine(" l_left " + l_left + " l_right " + l_right + " l_middle " + l_middle);
175                 while( l_left < l_right)
176                 {//从左边开始检索
177                     if (p_arr [l_left] >= l_middle) 
178                     {//遇到了左边比中值要大的
179                         while( l_right > l_left)
180                         {//开始检索右边的
181                             if (p_arr [l_right] < l_middle) 
182                             {//遇到右边比中值要小的,交换此时左右flag的数然后左边继续
183                                 int l_temp = p_arr [l_right];
184                                 p_arr [l_right] = p_arr [l_left];
185                                 p_arr [l_left] = l_temp;
186                                 l_right--;
187                                 break;
188                             } else 
189                             {
190                                 l_right--;
191                             }
192                         }
193                     }
194                     l_left++;
195                 }
196                 Console.WriteLine("--- l_left " + l_left + " l_right " + l_right + " l_middle " + l_middle);
197                 if(p_left < l_right)
198                 {//此处只所以从p_left~l_right，而不是p_left~l_left，是因为上面的l_left++了，l_right--了
199                     quickSort (p_arr, p_left, l_right);
200                 }
201 
202                 if(l_left < p_right)
203                 {
204                     quickSort (p_arr, l_left, p_right);
205                 }
206             }
207             return p_arr;
208         }
209         /// <summary>
210         /// 堆排序.
211         /// </summary>
212         /// <returns>The sort.</returns>
213         /// <param name="p_arr">P_arr.</param>
214         private static int[] heapSort(int[] p_arr) 
215         {// 要求最后结果是从小到大，所以堆顶要放最大的元素
216             int l_last = p_arr.Length - 1;//从堆地元素上溯初始化堆
217             int l_index = l_last;
218 
219             while(l_index > 0)
220             {
221                 int l_parent = (l_index + 1)/2 - 1;
222                 if(p_arr[l_index] > p_arr[l_parent])
223                 { //大于父节点，交换
224                     int temp = p_arr[l_index];
225                     p_arr[l_index] = p_arr[l_parent];
226                     p_arr[l_parent] = temp;
227                     checkChild(p_arr, l_index, l_last);
228                 } else {
229                     int l_borther = l_index % 2 == 0? l_index - 1 : l_index + 1;//当前如果是右节点，则兄弟为左，反之亦然
230                     if(l_borther <= l_last && p_arr[l_borther] > p_arr[l_parent])
231                     {//兄弟节点大于父节点，交换
232                         int temp = p_arr[l_borther];
233                         p_arr[l_borther] = p_arr[l_parent];
234                         p_arr[l_parent] = temp;
235                         checkChild(p_arr, l_borther, l_last);
236                     } else 
237                     {
238                         l_index = l_parent;
239                     }
240                 }
241             }
242             Console.WriteLine ("初始化堆：" + p_arr.printArray ());
243             while(l_last > 0)
244             {
245                 int temp = p_arr[l_last];
246                 p_arr[l_last] = p_arr[0];
247                 p_arr[0] = temp;
248                 l_last--;
249                 checkChild(p_arr, 0, l_last);
250             }
251             return p_arr;
252         }
253 
254         private static void checkChild(int[] p_arr, int p_index, int p_last)
255         {
256             int l_index = p_index;
257             while(l_index < p_last)
258             {
259                 int l_leftIndex = 2 * l_index + 1;//l_index的左子
260                 int l_rightIndex = 2 * l_index + 2;//l_index的柚子
261                 if(l_leftIndex > p_last && l_rightIndex > p_last)
262                 {//末节点
263                     break;
264                 }
265                 if( l_leftIndex <= p_last && p_arr[l_leftIndex]  > p_arr[l_index])
266                 {//左子大于父节点，交换
267                     int temp = p_arr[l_index];
268                     p_arr[l_index] = p_arr[l_leftIndex];
269                     p_arr[l_leftIndex] = temp;
270                     checkChild(p_arr, l_leftIndex, p_last);
271                 }
272                 if( l_rightIndex <= p_last && p_arr[l_rightIndex] > p_arr[l_index])
273                 {//右子大于父节点，交换
274                     int temp = p_arr[l_index];
275                     p_arr[l_index] = p_arr[l_rightIndex];
276                     p_arr[l_rightIndex] = temp;
277                     checkChild(p_arr, l_rightIndex, p_last);
278                 }
279                 l_index++;
280             }
281         }
282     }
283 }