梳排序

1. pub fn comb_sort<T: Ord>(arr: &mut [T]) {
2. let mut gap = arr.len();
3. let shrink = 1.3;
4. let mut sorted = false;

6. while !sorted {
7. gap = (gap as f32 / shrink).floor() as usize;
8. if gap <= 1 {
9. gap = 1;
10. sorted = true;
11. }
12. for i in 0..arr.len() - gap {
13. let j = i + gap;
14. if arr[i] > arr[j] {
15. arr.swap(i, j);
16. sorted = false;
17. }
18. }
19. }
20. }

22. #[cfg(test)]
23. mod tests {
24. use super::*;

26. #[test]
27. fn descending() {
28. //descending
29. let mut ve1 = vec![6, 5, 4, 3, 2, 1];
30. comb_sort(&mut ve1);
31. for i in 0..ve1.len() - 1 {
32. assert!(ve1[i] <= ve1[i + 1]);
33. }
34. }

36. #[test]
37. fn ascending() {
38. //pre-sorted
39. let mut ve2 = vec![1, 2, 3, 4, 5, 6];
40. comb_sort(&mut ve2);
41. for i in 0..ve2.len() - 1 {
42. assert!(ve2[i] <= ve2[i + 1]);
43. }
44. }
45. }