希尔排序

1. pub fn shell_sort<T: Ord + Copy>(values: &mut Vec<T>) {
2. // shell sort works by swiping the value at a given gap and decreasing the gap to 1
3. fn insertion<T: Ord + Copy>(values: &mut Vec<T>, start: usize, gap: usize) {
4. for i in ((start + gap)..values.len()).step_by(gap) {
5. let val_current = values[i];
6. let mut pos = i;
7. // make swaps
8. while pos >= gap && values[pos - gap] > val_current {
9. values[pos] = values[pos - gap];
10. pos -= gap;
11. }
12. values[pos] = val_current;
13. }
14. }

16. let mut count_sublist = values.len() / 2; // makes gap as long as half of the array
17. while count_sublist > 0 {
18. for pos_start in 0..count_sublist {
19. insertion(values, pos_start, count_sublist);
20. }
21. count_sublist /= 2; // makes gap as half of previous
22. }
23. }

25. #[cfg(test)]
26. mod test {
27. use super::shell_sort;

29. #[test]
30. fn basic() {
31. let mut vec = vec![3, 5, 6, 3, 1, 4];
32. shell_sort(&mut vec);
33. for i in 0..vec.len() - 1 {
34. assert!(vec[i] <= vec[i + 1]);
35. }
36. }

38. #[test]
39. fn empty() {
40. let mut vec: Vec<i32> = vec![];
41. shell_sort(&mut vec);
42. assert_eq!(vec, vec![]);
43. }

45. #[test]
46. fn reverse() {
47. let mut vec = vec![6, 5, 4, 3, 2, 1];
48. shell_sort(&mut vec);
49. for i in 0..vec.len() - 1 {
50. assert!(vec[i] <= vec[i + 1]);
51. }
52. }

54. #[test]
55. fn already_sorted() {
56. let mut vec = vec![1, 2, 3, 4, 5, 6];
57. shell_sort(&mut vec);
58. for i in 0..vec.len() - 1 {
59. assert!(vec[i] <= vec[i + 1]);
60. }
61. }
62. }