c# 排序之堆排序

夜炙至尊

代码：

1. /// <summary>  
2.         /// 堆排序办法。  
3.         /// </summary>  
4.         /// <param name="a">  
5.         /// 待排序数组。  
6.         /// </param>  
7.         private void Heapsort(int[] a)
8.         {
9.             HeapSort_BuildMaxHeap(a); // 成立年夜根堆。  
10.             Console.WriteLine("Build max heap:");
11.             foreach (int i in a)
12.             {
13.                 Console.Write(i + " "); // 挨印年夜根堆。  
14.             }
16.             Console.WriteLine("\r\nMax heap in each iteration:");
17.             for (int i = a.Length - 1; i > 0; i--)
18.             {
19.                 HeapSort_Swap(ref a[0], ref a[i]); // 将堆顶元素战无序区的最初一个元故旧换。  
20.                 HeapSort_MaxHeaping(a, 0, i); // 将新的无序区调解为年夜根堆。  
22.                 // 挨印每次堆排序迭代后的年夜根堆。  
23.                 for (int j = 0; j < i; j++)
24.                 {
25.                     Console.Write(a[j] + " ");
26.                 }
28.                 Console.WriteLine(string.Empty);
29.             }
30.         }
32.         /// <summary>  
33.         /// 由底背上建堆。由完整两叉树的性子可知，叶子结面是从index=a.Length/2开端，以是从index=(a.Length/2)-1结面开端由底背长进止年夜根堆的调解。  
34.         /// </summary>  
35.         /// <param name="a">  
36.         /// 待排序数组。  
37.         /// </param>  
38.         private static void HeapSort_BuildMaxHeap(int[] a)
39.         {
40.             for (int i = (a.Length / 2) - 1; i >= 0; i--)
41.             {
42.                 HeapSort_MaxHeaping(a, i, a.Length);
43.             }
44.         }
46.         /// <summary>  
47.         /// 将指定的结面调解为堆。  
48.         /// </summary>  
49.         /// <param name="a">  
50.         /// 待排序数组。  
51.         /// </param>  
52.         /// <param name="i">  
53.         /// 需求调解的结面。  
54.         /// </param>  
55.         /// <param name="heapSize">  
56.         /// 堆的巨细，也指数组中无序区的少度。  
57.         /// </param>  
58.         private static void HeapSort_MaxHeaping(int[] a, int i, int heapSize)
59.         {
60.             int left = (2 * i) + 1; // 左子结面。  
61.             int right = 2 * (i + 1); // 左子结面。  
62.             int large = i; // 暂时变量，寄存年夜的结面值。  
64.             // 比力左子结面。  
65.             if (left < heapSize && a[left] > a[large])
66.             {
67.                 large = left;
68.             }
70.             // 比力左子结面。  
71.             if (right < heapSize && a[right] > a[large])
72.             {
73.                 large = right;
74.             }
76.             // 若有子结面年夜于本身便交流，使年夜的元素上移；而且把该年夜的元素调解为堆以包管堆的性子。  
77.             if (i != large)
78.             {
79.                 HeapSort_Swap(ref a[i], ref a[large]);
80.                 HeapSort_MaxHeaping(a, large, heapSize);
81.             }
82.         }
84.         /// <summary>  
85.         /// 交流两个整数的值。  
86.         /// </summary>  
87.         /// <param name="a">整数a。</param>  
88.         /// <param name="b">整数b。</param>  
89.         private static void HeapSort_Swap(ref int a, ref int b)
90.         {
91.             int tmp = a;
92.             a = b;
93.             b = tmp;
94.         }

复造代码

 

免责声明：假如进犯了您的权益，请联络站少，我们会实时删除侵权内乱容，感谢协作！