快速排序

1. pub fn quick_sort<T: PartialOrd>(arr: &mut [T]) {
2. if arr.len() > 1 {
3. quick_sort_range(arr, 0, arr.len() - 1);
4. }
5. }

7. fn quick_sort_range<T: PartialOrd>(arr: &mut [T], lo: usize, hi: usize) {
8. // 只有当元素个数大于一时才进行排序
9. if lo < hi {
10. let pos = partition(arr, lo, hi);
11. // let pos = partition_random(arr, lo, hi);
12. if pos != 0 {
13. // 如果 pos == 0, pos - 1 会发生溢出错误
14. quick_sort_range(arr, lo, pos - 1);
15. }
16. quick_sort_range(arr, pos + 1, hi);
17. }
18. }

20. fn partition<T: PartialOrd>(arr: &mut [T], lo: usize, hi: usize) -> usize {
21. // 默认选取 lo 作为 pivot
22. let pivot = lo;

24. let (mut left, mut right) = (lo, hi);
25. while left < right {
26. // 找到右边第一个不大于等于 arr[pivot] 的元素
27. while left < right && arr[right] >= arr[pivot] {
28. right -= 1;
29. }

31. // 找到左边第一个不小于等于 arr[pivot] 的元素
32. while left < right && arr[left] <= arr[pivot] {
33. left += 1;
34. }

36. // 交换前面找到的两个元素
37. if left != right {
38. arr.swap(left, right);
39. }
40. }

42. arr.swap(pivot, left);

44. // 返回正确的分割位置
45. left
46. }

48. // 随机选取 pivot 的位置
49. fn partition_random<T: PartialOrd>(arr: &mut [T], lo: usize, hi: usize) -> usize {
50. // 在 Cargo.toml 的依赖中添加 rand 库
51. use rand::Rng;
52. let mut rng = rand::thread_rng();
53. let pivot = rng.gen_range(lo..=hi);

55. // 交换 lo 和 pivot 位置上的元素，从而间接使得 pivot = lo
56. // 因此后序操作和 partition() 函数一致
57. arr.swap(lo, pivot);

59. let pivot = lo;
60. let (mut left, mut right) = (lo, hi);
61. while left < right {
62. // 找到右边第一个不大于等于 arr[pivot] 的元素
63. while left < right && arr[right] >= arr[pivot] {
64. right -= 1;
65. }

67. // 找到左边第一个不小于等于 arr[pivot] 的元素
68. while left < right && arr[left] <= arr[pivot] {
69. left += 1;
70. }

72. // 交换前面找到的两个元素
73. if left != right {
74. arr.swap(left, right);
75. }
76. }

78. arr.swap(pivot, left);

80. // 返回正确的分割位置
81. left
82. }

84. #[cfg(test)]
85. mod tests {
86. use super::*;

88. #[test]
89. fn test_empty_vec() {
90. let mut empty_vec: Vec<String> = vec![];
91. quick_sort(&mut empty_vec);
92. assert_eq!(empty_vec, Vec::<String>::new());
93. }

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

102. #[test]
103. fn test_string_vec() {
104. let mut vec = vec![
105. String::from("Bob"),
106. String::from("David"),
107. String::from("Carol"),
108. String::from("Alice"),
109. ];
110. quick_sort(&mut vec);
111. assert_eq!(
112. vec,
113. vec![
114. String::from("Alice"),
115. String::from("Bob"),
116. String::from("Carol"),
117. String::from("David"),
118. ]
119. );
120. }
121. }