rust-algorithms:15-臭皮匠排序
pub fn stooge_sort<T: Ord>(arr: &mut [T]) {
if arr.len() > 1 {
stooge_sort_range(arr, 0, arr.len() - 1);
}
}
fn stooge_sort_range<T: Ord>(arr: &mut[T], begin: usize, end: usize) {
// 避免end = start + 1
if arr[begin] > arr[end] {
arr.swap(begin, end);
}
if end - begin > 1 {
// 数值,而非间距,需要+1
let one_third = (end - begin + 1) / 3;
// 前2/3
stooge_sort_range(arr, begin, end - one_third);
// 后1/3
stooge_sort_range(arr, begin + one_third, end);
// 前2/3
stooge_sort_range(arr, begin, end - one_third)
}
}
本作品采用《CC 协议》,转载必须注明作者和本文链接