c# 排序之堆排序

以你之姓@ 2023-01-02 06:23 116阅读 0赞

代码：

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. `}`
15. 
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); // 将新的无序区调整为大根堆。`
21. 
22. `// 打印每一次堆排序迭代后的大根堆。`
23. `for (int j = 0; j < i; j++)`
24. `{`
25. `Console.Write(a[j] + " ");`
26. `}`
27. 
28. `Console.WriteLine(string.Empty);`
29. `}`
30. `}`
31. 
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. `}`
45. 
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; // 临时变量，存放大的结点值。`
63. 
64. `// 比较左子结点。`
65. `if (left < heapSize && a[left] > a[large])`
66. `{`
67. `large = left;`
68. `}`
69. 
70. `// 比较右子结点。`
71. `if (right < heapSize && a[right] > a[large])`
72. `{`
73. `large = right;`
74. `}`
75. 
76. `// 如有子结点大于自身就交换，使大的元素上移；并且把该大的元素调整为堆以保证堆的性质。`
77. `if (i != large)`
78. `{`
79. `HeapSort_Swap(ref a[i], ref a[large]);`
80. `HeapSort_MaxHeaping(a, large, heapSize);`
81. `}`
82. `}`
83. 
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. `}`