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 ("请选择算法(从小到大排序)：\n0.退出 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+1140                 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 }