1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 6 namespace HeapSort 7 { 8 public static class Heap 9 { 10 /// <summary> 11 /// 堆排序 12 /// </summary> 13 /// <param name="arr">数组</param> 14 public static void Sort(int[] arr) 15 { 16 //初始化堆 17 InitialHeap(arr); 18 //无序区递减 19 for (int i = arr.Length - 1; i > 0; --i) 20 { 21 //交换堆顶元素与无序区末端元素 22 Program.Swap(ref arr[0], ref arr[i]); 23 //堆化新无序区 24 Heapify(arr, 0, i); 25 } 26 } 27 28 /// <summary> 29 /// 初始化堆 30 /// </summary> 31 /// <param name="arr">数组</param> 32 private static void InitialHeap(int[] arr) 33 { 34 //堆化所有以非叶子节点为堆顶的数据 35 for (int i = arr.Length / 2 - 1; i >= 0; --i) 36 { 37 Heapify(arr, i, arr.Length); 38 } 39 } 40 41 /// <summary> 42 /// 以指定节点为堆顶，由上至下递归堆化其所有子节点 43 /// </summary> 44 /// <param name="arr">数组</param> 45 /// <param name="nodeIndex">堆顶节点索引</param> 46 /// <param name="heapSize">堆大小(这里指数组无序区大小)</param> 47 private static void Heapify(int[] arr, int nodeIndex, int heapSize) 48 { 49 //左右子节点索引 50 int leftIndex = nodeIndex * 2 + 1; 51 int rightIndex = nodeIndex * 2 + 2; 52 //最大值节点索引 53 int maxIndex = nodeIndex; 54 55 //左子节点存在，并且值大于最大值节点 56 if (leftIndex < heapSize && arr[leftIndex] > arr[maxIndex]) 57 maxIndex = leftIndex;//调整最大值节点索引 58 59 //右节点存在，并且值大于最大值 60 if (rightIndex < heapSize && arr[rightIndex] > arr[maxIndex]) 61 maxIndex = rightIndex;//调整最大值节点索引 62 63 //两次比较之后，堆顶节点值不是最大 64 if (maxIndex != nodeIndex) 65 { 66 //将最大值交换至堆顶 67 Program.Swap(ref arr[nodeIndex], ref arr[maxIndex]); 68 //堆结构发生变化，递归调整堆 69 Heapify(arr, maxIndex, heapSize); 70 } 71 }//end Method Heapify() 72 }//end class Heap 73 74 class Program 75 { 76 private static Random Seed = new Random();//Random Seed 77 78 //交换 79 public static void Swap(ref int a, ref int b) 80 { 81 int t = a; 82 a = b; 83 b = t; 84 } 85 86 /// <summary> 87 /// 快速排序 88 /// </summary> 89 /// <param name="arr">数组</param> 90 /// <param name="begin">起始索引</param> 91 /// <param name="end">结束索引</param> 92 /// <param name="isRandomKey">是否随机取Key</param> 93 private static void QuickSort(int[] arr, int begin, int end, bool isRandomKey) 94 { 95 //起始索引小于结束索引，排序未完成 96 if (begin < end) 97 { 98 int i = begin - 1, j = end + 1, key; 99 if (!isRandomKey) 100 key = arr[(begin + end) / 2]; 101 else//随机取Key 102 key = arr[Seed.Next(begin, end)]; 103 104 while (true) 105 { 106 //第一个大于Key值的元素索引 107 while (i < end && arr[++i] < key) ; 108 //最后一个小于Key值的元素索引 109 while (j > 0 && arr[--j] > key) ; 110 111 //索引已无需交换 112 if (i >= j) 113 break; 114 //交换元素 115 Swap(ref arr[i], ref arr[j]); 116 } 117 118 QuickSort(arr, begin, i - 1, isRandomKey);//左部分子递归 119 QuickSort(arr, j + 1, end, isRandomKey);//右部分子递归 120 }//end if(begin < end) 121 }//end QuickSort() 122 123 /// <summary> 124 /// 计算经过毫秒数 125 /// </summary> 126 /// <param name="dtStart">起始时间</param> 127 /// <param name="dtEnd">结束时间</param> 128 /// <returns>返回毫秒数</returns> 129 private static double GetMilliSecond(DateTime dtStart, DateTime dtEnd) 130 { 131 TimeSpan ts1 = new TimeSpan(dtStart.Ticks); 132 TimeSpan ts2 = new TimeSpan(dtEnd.Ticks); 133 TimeSpan ts = ts1.Subtract(ts2).Duration(); 134 return ts.TotalMilliseconds; 135 } 136 137 //输出 138 static void Output(int[] arr) 139 { 140 foreach (var item in arr) 141 Console.Write(item + " "); 142 143 Console.WriteLine(); 144 } 145 146 static void Main(string[] args) 147 { 148 int ArrLen = 0;//数组长度 149 150 ReInput://重新输入 151 152 Console.Write("请输入待测试数组长度:"); 153 if (!int.TryParse(Console.ReadLine(), out ArrLen)) 154 { 155 Console.WriteLine("输入错误!"); 156 goto ReInput; 157 } 158 159 //数组1，测试快速排序 160 int[] NumArr = new int[ArrLen]; 161 //数组2，测试堆排序 162 int[] NumArr_2 = new int[NumArr.Length]; 163 164 Console.WriteLine("正在随机初始化数组元素……"); 165 for (int i = 0; i < NumArr.Length; i++)//随机(-1000 ~ 1000)初始化数组元素 166 NumArr[i] = Seed.Next(-1000, 1000); 167 168 Console.WriteLine("初始化完成"); 169 170 Console.WriteLine("\n复制元素值到数组2……"); 171 for (int i = 0; i < NumArr.Length; i++)//复制元素值 172 NumArr_2[i] = NumArr[i]; 173 174 Console.WriteLine("复制完成"); 175 176 /*//取消该段注释，输出排序前数组 177 Console.Write("排序前："); 178 Output(NumArr); 179 */ 180 181 182 Console.Write("\n开始快速排序，请稍后……"); 183 DateTime dtStart = DateTime.Now; 184 QuickSort(NumArr, 0, NumArr.Length - 1, false); 185 // 186 DateTime dtEnd = DateTime.Now; 187 Console.WriteLine("\n快速排序完成，用时：{0} 毫秒", GetMilliSecond(dtStart, dtEnd)); 188 189 /*//取消该段注释，输出排序后数组 190 Console.Write("\n\n\n排序后："); 191 Output(NumArr); 192 */ 193 194 //............................................................................................. 195 196 Console.Write("\n开始堆排序，请稍后……"); 197 dtStart = DateTime.Now; 198 Heap.Sort(NumArr_2); 199 // 200 dtEnd = DateTime.Now; 201 Console.WriteLine("\n堆排序完成，用时：{0} 毫秒", GetMilliSecond(dtStart, dtEnd)); 202 203 /*//取消该段注释，输出排序后数组 204 Console.Write("\n\n\n排序后："); 205 Output(NumArr_2); 206 */ 207 208 Console.Write("按任意键退出……"); 209 Console.ReadKey(true); 210 }//end Main() 211 }//end class Program 212 }//end namespace
//欢迎转载，请注明原创，感谢