堆排序

1. pub fn heap_sort<T: PartialOrd>(arr: &mut [T]) {
2. let size = arr.len();
3. // 构建大根堆
4. for i in (0..size / 2).rev() {
5. heapify(arr, i, size);
6. }

8. // 每轮循环将堆顶元素（也就是最大元素）放到最后
9. for i in (1..size).rev() {
10. arr.swap(0, i);
11. // 恢复大根堆
12. heapify(arr, 0, i);
13. }
14. }

16. fn heapify<T: PartialOrd>(arr: &mut [T], root: usize, end: usize) {
17. // 记录父节点和左右节点中最大元素的索引位置
18. let mut largest = root;

20. let left_child = 2 * root + 1;
21. if left_child < end && arr[left_child] > arr[largest] {
22. largest = left_child;
23. }

25. let right_child = left_child + 1;
26. if right_child < end && arr[right_child] > arr[largest] {
27. largest = right_child;
28. }

30. if largest != root {
31. arr.swap(root, largest);
32. heapify(arr, largest, end);
33. }
34. }

36. #[cfg(test)]
37. mod tests {
38. use super::*;

40. #[test]
41. fn test_empty_vec() {
42. let mut empty_vec: Vec<String> = vec![];
43. heap_sort(&mut empty_vec);
44. assert_eq!(empty_vec, Vec::<String>::new());
45. }

47. #[test]
48. fn test_number_vec() {
49. let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
50. heap_sort(&mut vec);
51. assert_eq!(vec, vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78]);
52. }

54. #[test]
55. fn test_string_vec() {
56. let mut vec = vec![
57. String::from("Bob"),
58. String::from("David"),
59. String::from("Carol"),
60. String::from("Alice"),
61. ];
62. heap_sort(&mut vec);
63. assert_eq!(
64. vec,
65. vec![
66. String::from("Alice"),
67. String::from("Bob"),
68. String::from("Carol"),
69. String::from("David"),
70. ]
71. );
72. }
73. }