2024-01-13 15:51:24 +08:00
|
|
|
use rand::Rng; // 0.7.2
|
|
|
|
|
use std::io;
|
|
|
|
|
|
|
|
|
|
fn quick_sort(nums: &mut Vec<i32>, left: usize, right: usize) {
|
|
|
|
|
if left >= right {
|
|
|
|
|
return;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
let random_index = rand::thread_rng().gen_range(left, right + 1);
|
|
|
|
|
let temp = nums[random_index];
|
|
|
|
|
nums[random_index] = nums[left];
|
|
|
|
|
nums[left] = temp;
|
|
|
|
|
|
|
|
|
|
let pivot = nums[left];
|
|
|
|
|
let mut i = left;
|
|
|
|
|
let mut j = right;
|
|
|
|
|
while i < j {
|
|
|
|
|
while i < j && nums[j] >= pivot {
|
|
|
|
|
j -= 1;
|
|
|
|
|
}
|
|
|
|
|
nums[i] = nums[j];
|
|
|
|
|
while i < j && nums[i] < pivot {
|
|
|
|
|
i += 1;
|
|
|
|
|
}
|
|
|
|
|
nums[j] = nums[i];
|
|
|
|
|
}
|
|
|
|
|
nums[i] = pivot;
|
|
|
|
|
|
|
|
|
|
quick_sort(nums, left, i);
|
|
|
|
|
quick_sort(nums, i + 1, right);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
fn main() -> io::Result<()> {
|
|
|
|
|
let mut n = String::new();
|
|
|
|
|
io::stdin().read_line(&mut n)?;
|
|
|
|
|
let n = n.trim().parse::<usize>().unwrap();
|
|
|
|
|
|
|
|
|
|
let mut nums = String::new();
|
|
|
|
|
io::stdin().read_line(&mut nums)?;
|
2024-06-21 10:06:50 +08:00
|
|
|
let mut nums: Vec<i32> = nums.split(' ').map(|s| s.trim().parse().unwrap()).collect();
|
2024-01-13 15:51:24 +08:00
|
|
|
|
|
|
|
|
quick_sort(&mut nums, 0, n - 1);
|
|
|
|
|
for num in nums.iter() {
|
|
|
|
|
print!("{} ", num);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
Ok(())
|
|
|
|
|
}
|
