冒泡排序

1. pub fn bubble_sort<T: PartialOrd>(arr: &mut [T]) {
2. if arr.len() <= 1 {
3. return;
4. }

6. let size = arr.len();
7. for i in 0..(size - 1) {
8. // 标记当前循环是否发生元素交换
9. let mut swapped = false;

11. // 最后i个元素已经排好了顺序
12. for j in 1..(size - i) {
13. if arr[j - 1] > arr[j] {
14. arr.swap(j - 1, j);
15. swapped = true;
16. }
17. }

19. // 如果当前循环没有发生元素交换，说明数组已经有序
20. if !swapped {
21. break;
22. }
23. }
24. }

26. #[cfg(test)]
27. mod tests {
28. use super::*;

30. #[test]
31. fn test_empty_vec() {
32. let mut empty_vec: Vec<String> = vec![];
33. bubble_sort(&mut empty_vec);
34. assert_eq!(empty_vec, Vec::<String>::new());
35. }

37. #[test]
38. fn test_number_vec() {
39. let mut vec = vec![7, 49, 73, 58, 30, 72, 44, 78, 23, 9];
40. bubble_sort(&mut vec);
41. assert_eq!(vec, vec![7, 9, 23, 30, 44, 49, 58, 72, 73, 78]);
42. }

44. #[test]
45. fn test_string_vec() {
46. let mut vec = vec![
47. String::from("Bob"),
48. String::from("David"),
49. String::from("Carol"),
50. String::from("Alice"),
51. ];
52. bubble_sort(&mut vec);
53. assert_eq!(
54. vec,
55. vec![
56. String::from("Alice"),
57. String::from("Bob"),
58. String::from("Carol"),
59. String::from("David"),
60. ]
61. );
62. }
63. }