计算分割点
(nums: &mut [i32], low: usize, high: usize)
| 14 | |
| 15 | // 计算分割点 |
| 16 | fn partition(nums: &mut [i32], low: usize, high: usize) -> usize { |
| 17 | let mut lm = low; // 左标记 |
| 18 | let mut rm = high; // 右标记 |
| 19 | |
| 20 | loop { |
| 21 | // 左标记不断右移 |
| 22 | while lm <= rm && nums[lm] <= nums[low] { |
| 23 | lm += 1; |
| 24 | } |
| 25 | // 右标记不断左移 |
| 26 | while lm <= rm && nums[low] <= nums[rm] { |
| 27 | rm -= 1; |
| 28 | } |
| 29 | |
| 30 | // 左标记越过右标记时退出并交换左右标记数据 |
| 31 | if lm > rm { |
| 32 | break; |
| 33 | } else { |
| 34 | nums.swap(lm, rm); |
| 35 | } |
| 36 | } |
| 37 | nums.swap(low, rm); |
| 38 | |
| 39 | rm |
| 40 | } |
| 41 | |
| 42 | // 分割点不单独计算的快速排序，lm 和 rm 作分割点 |
| 43 | fn quick_sort2(nums: &mut [i32], low: usize, high: usize) { |