Timsort

算法由 xieyu567 提交

1. use std::cmp::min;

3. pub fn find_min_run(mut n: usize) -> usize {
4. let mut r = 0;
5. let minimum = 64;
6. while n >= minimum {
7. r |= n & 1;
8. n >>= 1;
9. }
10. n + r
11. }

13. pub fn insert_sort<T>(arr: &mut [T], left: usize, right: usize)
14. where T: PartialOrd + Copy, {
15. for i in left + 1..right + 1 {
16. let element = arr[i];
17. let mut j = i - 1;
18. while element < arr[j] && j >= left {
19. arr[j + 1] = arr[j];
20. j -= 1;
21. }
22. arr[j + 1] = element;
23. }
24. }

26. pub fn merge<T>(arr: &mut [T], left: usize, mid: usize, right: usize)
27. where T: PartialOrd + Copy, {
28. let array_length1 = mid - left + 1;
29. let array_length2 = right - mid;
30. let left_arr = Vec::from(&arr[left..left + array_length1]);
31. let right_arr = Vec::from(&arr[mid + 1..mid + 1 + array_length2]);

33. let (mut i, mut j, mut k) = (0, 0, left);
34. while j < array_length2 && i < array_length1 {
35. if left_arr[i] <= right_arr[j] {
36. arr[k] = left_arr[i];
37. i += 1;
38. } else {
39. arr[k] = right_arr[j];
40. j += 1
41. }
42. k += 1
43. }
44. while i < array_length1 {
45. arr[k] = left_arr[i];
46. k += 1;
47. i += 1
48. }
49. while j < array_length2 {
50. arr[k] = right_arr[j];
51. k += 1;
52. j += 1
53. }
54. }

56. pub fn tim_sort<T>(arr: &mut [T])
57. where T: PartialOrd + Copy, {
58. let n = arr.len();
59. let min_run = find_min_run(n);

61. for start in (0..n).filter(|x| x % min_run == 0) {
62. let end = min(start + min_run - 1, n - 1);
63. insert_sort(arr, start, end)
64. }
65. let mut size = min_run;
66. while size < n {
67. for left in (0..n).filter(|x| x % (2 * size) == 0) {
68. let mid = min(n - 1, left + size - 1);
69. let right = min(left + 2 * size - 1, n - 1);
70. merge(arr, left, mid, right)
71. }
72. size = 2 * size
73. }
74. }

76. #[cfg(test)]
77. mod tests {
78. use super::*;

80. #[test]
81. fn cal_min() {
82. let n = 189;
83. let min_run = find_min_run(n);
84. assert_eq!(48, min_run);
85. assert_eq!(61, find_min_run(976));
86. }

88. #[test]
89. fn insert_test() {
90. let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
91. insert_sort(&mut vec, 0, 9);
92. assert_eq!(vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78], vec)
93. }

95. #[test]
96. fn tim_test() {
97. let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
98. tim_sort(&mut vec);
99. assert_eq!(vec, vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78]);
100. }
101. }