题目
内部排序算法比较
对7种常用的内部排序算法进行比较：直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、二路归并排序。
待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为关键字参加的比较次数和数据元素的移动次数（关键字交换计为3次移动）。
对不同的输入表长做试验，观察两个指标相对于表长的变化关系，也可以对稳定性做验证。
统计成绩
给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。
①按总分由高到低的顺序，打印出名次表，分数相同的为同一名次；
②按名次打印出每个学生的学号、姓名、总分以及各科成绩。
一
一些经验，rust对于类型要求很严格，所以用作索引的一律用usize，因为for循环里的i默认是，统计数据用u64，如果u32溢出程序会直接panic
use std::mem::swap;
use tracing::info;
use tracing_subscriber::filter::LevelFilter;
pub struct Benchmark{
compare_time : u64,
move_time : u64,
}
struct Sort{
bench : Benchmark,
}
impl Sort{
pub fn new() -> Sort{
Sort{
bench : Benchmark{
compare_time : 0,
move_time : 0,
}
}
}
pub fn compare(&mut self, num1 : i32, num2 : i32) -> bool{
self.bench.compare_time += 1;
num1 > num2
}
pub fn insert_sort(&mut self, nums : &mut Vec<i32>){
let mut temp = 0;
for i in 1..nums.len(){
if self.compare(nums[i-1], nums[i]) { //如果小于，直接跳过
temp = nums[i];
let mut j = i;
while j > 0 && !self.compare(temp, nums[j-1]){ // 与第j-1个元素相比较
nums[j] = nums[j-1];
self.bench.move_time += 1;
j -= 1;
}
nums[j] = temp;
self.bench.move_time +=1;
}
}
}
pub fn shell_sort(&mut self, nums : &mut Vec<i32>) {
let dlta = vec![8,4,2,1];
for k in 0..dlta.len(){
self.shell_insert(nums, dlta[k]);
}
}
fn shell_insert(&mut self, nums : &mut Vec<i32>, d : u32){
// d为步长
let dd = d as usize;
// 分成d次插入排序
for i in dd..nums.len(){
if self.compare(nums[i - dd],nums[i]){
let temp = nums[i];
let mut j = i;
while j >= dd && self.compare(nums[j - dd], temp) {
nums[j] = nums[j - dd];
self.bench.move_time += 1;
j -= dd;
}
nums[j] = temp;
self.bench.move_time += 1;
}
}
}
pub fn bubble_sort(&mut self, nums : &mut Vec<i32>){
let mut change = true;
let n = nums.len();
for i in 0..n{
if change == false{
return;
}
change = false;
for j in 1..n - i{
if self.compare(nums[j-1], nums[j]){
// 交换，记录
nums.swap(j-1, j);
self.bench.move_time += 3;
change = true;
}
}
}
}
pub fn quick_sort(&mut self, nums : &mut Vec<i32>, low: usize, high: usize){
if high > low {
let pi = self.partition(nums, low, high);
if pi > low { // 避免pi = 0发生溢出的情况
self.quick_sort(nums, low, pi - 1);
}
self.quick_sort(nums, pi + 1, high);
}
}
fn partition(&mut self, nums : &mut Vec<i32>, low: usize, high: usize) -> usize{
let pivot = nums[high as usize];
let mut index : usize = low as usize;
for j in low..high {
if self.compare(pivot, nums[j]){
index += 1;
nums.swap(index -1,j);
self.bench.move_time += 3;
}
}
nums.swap(index,high as usize);
index
}
pub fn select_sort(&mut self, nums : &mut Vec<i32>){
let t = nums.len();
for i in 0..t-1{
let target = t - 1 - i;
let k = self.find_max(nums, t-i);
if k != target{
nums.swap(k,target);
self.bench.move_time += 3;
}
}
}
fn find_max(&mut self, nums : &mut Vec<i32>, len:usize) -> usize{
let mut max = nums[0];
let mut max_index = 0;
for i in 1..len{
if self.compare(nums[i],max){
max_index = i;
max = nums[i];
}
}
max_index
}
pub fn heap_sort(&mut self, nums : &mut Vec<i32>){
let len = nums.len();
let last_parent = (len / 2) - 1;
for i in (0..=last_parent).rev(){
self.sift_down(nums, i, len - 1);
}
for i in (1..=len - 1).rev(){
nums.swap(0, i);
self.bench.move_time += 3;
self.sift_down(nums, 0, i-1);
}
}
fn sift_down(&mut self, nums : &mut Vec<i32>, start : usize, end : usize){
let mut parent = start;
let mut child = parent * 2 + 1;
while child <= end{
if child + 1 <= end && self.compare(nums[child + 1], nums[child]){
child += 1;
}
if self.compare(nums[parent],nums[child] ) {
return;
}else{
nums.swap(child, parent);
self.bench.move_time += 3;
parent = child;
child = parent * 2 + 1;
}
}
}
pub fn merge_sort(&mut self, nums : &mut Vec<i32>, left : usize, right : usize){
if left < right{
let mid = left + (right - left) / 2;
self.merge_sort(nums, left, mid);
self.merge_sort(nums, mid + 1, right);
self.merge(nums, left,mid, right);
}
}
fn merge(&mut self, nums : &mut Vec<i32>, left : usize,mid : usize, right : usize){
let l1 = mid - left + 1;
let l2 = right - mid;
let v1 = nums[left..left + l1].to_vec();
let v2 = nums[mid + 1..mid + 1 + l2].to_vec();
self.bench.move_time += (l1 + l2) as u64;
let mut i = 0;
let mut j = 0;
let mut k = left;
while i<l1 && j<l2{
if self.compare(v1[i], v2[j]){
nums[k] = v2[j];
self.bench.move_time += 1;
j += 1;
}else {
nums[k] = v1[i];
self.bench.move_time += 1;
i += 1;
}
k += 1;
}
while i < l1{
nums[k] = v1[i];
self.bench.move_time += 1;
i += 1;
k += 1;
}
while i < l2{
nums[k] = v2[j];
self.bench.move_time += 1;
j += 1;
k += 1;
}
}
}
#[cfg(test)]
mod test{
use crate::Sort;
#[test]
fn test_sort() {
use rand::Rng;
use tracing::info;
use tracing_subscriber::filter::LevelFilter;
let _ = tracing_subscriber::fmt()
.with_max_level(LevelFilter::INFO)
.with_test_writer()
.try_init();
let mut rng = rand::rng();
// 定义5组测试数据的长度
let test_sizes = [100, 500, 1000, 2000, 5000, 10000, 100000];
for (round, &len) in test_sizes.iter().enumerate() {
info!("=== 第 {} 组测试 | 数据量: {} ===", round + 1, len);
// 生成随机数据
let origin: Vec<i32> = (0..len).map(|_| rng.random_range(-10000..10000)).collect();
let sorted_std = {
let mut v = origin.clone();
v.sort();
v
};
// 定义算法列表：(名称, 执行闭包)
// 使用 Box<dyn Fn...> 来统一不同函数签名的调用
let algorithms: Vec<(&str, Box<dyn Fn(&mut Sort, &mut Vec<i32>)>)> = vec![
("插入排序", Box::new(|s, v| s.insert_sort(v))),
("希尔排序", Box::new(|s, v| s.shell_sort(v))),
("冒泡排序", Box::new(|s, v| s.bubble_sort(v))),
("选择排序", Box::new(|s, v| s.select_sort(v))),
("堆排序 ", Box::new(|s, v| s.heap_sort(v))),
("快速排序", Box::new(|s, v| {
let l = v.len();
if l > 0 { s.quick_sort(v, 0, l - 1); }
})),
("归并排序", Box::new(|s, v| {
let l = v.len();
if l > 0 { s.merge_sort(v, 0, l - 1); }
})),
];
for (name, func) in algorithms {
let mut data = origin.clone();
let mut sort_instance = Sort::new(); // 每次新建实例
// 执行排序
func(&mut sort_instance, &mut data);
// 验证结果 (使用标准库排序结果作为基准)
assert_eq!(data, sorted_std, "{} 结果不正确!", name);
// 打印结果 (格式化对齐)
info!(
"算法: {} | 比较: {:>9} | 移动: {:>9}",
name,
sort_instance.bench.compare_time,
sort_instance.bench.move_time
);
}
}
}
/*
fn verify_sort(num : Vec<i32>, sorted : Vec<i32>) -> Result<(), String>{
if num.len() != sorted.len() {
return Err("长度不相等".to_string());
}
// 检查排序后的数组是否有序
for i in 1..sorted.len() {
if sorted[i] < sorted[i - 1] {
return Err("排序后数组存在逆序".to_string());
}
}
// 检查两个数组是否包含相同的元素（顺序可以不同）
let mut num_sorted = num.clone();
num_sorted.sort();
if num_sorted == sorted {
Ok(())
}else{
Err("数组不相等".to_string())
}
}
*/
}运行结果：
running 1 test
2025-12-22T05:01:19.791577Z INFO ex7::test: === 第 1 组测试 | 数据量: 100 ===
2025-12-22T05:01:19.792588Z INFO ex7::test: 算法: 插入排序 | 比较: 2702 | 移动: 2609
2025-12-22T05:01:19.793373Z INFO ex7::test: 算法: 希尔排序 | 比较: 1145 | 移动: 781
2025-12-22T05:01:19.794736Z INFO ex7::test: 算法: 冒泡排序 | 比较: 4905 | 移动: 7536
2025-12-22T05:01:19.796295Z INFO ex7::test: 算法: 选择排序 | 比较: 4950 | 移动: 282
2025-12-22T05:01:19.797076Z INFO ex7::test: 算法: 堆排序 | 比较: 1027 | 移动: 1746
2025-12-22T05:01:19.797772Z INFO ex7::test: 算法: 快速排序 | 比较: 727 | 移动: 1095
2025-12-22T05:01:19.798186Z INFO ex7::test: 算法: 归并排序 | 比较: 549 | 移动: 1292
2025-12-22T05:01:19.798396Z INFO ex7::test: === 第 2 组测试 | 数据量: 500 ===
2025-12-22T05:01:19.803050Z INFO ex7::test: 算法: 插入排序 | 比较: 62463 | 移动: 61970
2025-12-22T05:01:19.804701Z INFO ex7::test: 算法: 希尔排序 | 比较: 13345 | 移动: 11392
2025-12-22T05:01:19.818697Z INFO ex7::test: 算法: 冒泡排序 | 比较: 124372 | 移动: 184407
2025-12-22T05:01:19.821945Z INFO ex7::test: 算法: 选择排序 | 比较: 124750 | 移动: 1485
2025-12-22T05:01:19.822856Z INFO ex7::test: 算法: 堆排序 | 比较: 7440 | 移动: 12117
2025-12-22T05:01:19.823920Z INFO ex7::test: 算法: 快速排序 | 比较: 5113 | 移动: 9120
2025-12-22T05:01:19.824957Z INFO ex7::test: 算法: 归并排序 | 比较: 3856 | 移动: 8694
2025-12-22T05:01:19.825448Z INFO ex7::test: === 第 3 组测试 | 数据量: 1000 ===
2025-12-22T05:01:19.839718Z INFO ex7::test: 算法: 插入排序 | 比较: 256070 | 移动: 255078
2025-12-22T05:01:19.843516Z INFO ex7::test: 算法: 希尔排序 | 比较: 54399 | 移动: 50467
2025-12-22T05:01:19.879929Z INFO ex7::test: 算法: 冒泡排序 | 比较: 498905 | 移动: 762174
2025-12-22T05:01:19.891824Z INFO ex7::test: 算法: 选择排序 | 比较: 499500 | 移动: 2982
2025-12-22T05:01:19.894710Z INFO ex7::test: 算法: 堆排序 | 比较: 16804 | 移动: 27147
2025-12-22T05:01:19.895870Z INFO ex7::test: 算法: 快速排序 | 比较: 10949 | 移动: 14496
2025-12-22T05:01:19.897454Z INFO ex7::test: 算法: 归并排序 | 比较: 8709 | 移动: 19296
2025-12-22T05:01:19.898132Z INFO ex7::test: === 第 4 组测试 | 数据量: 2000 ===
2025-12-22T05:01:19.943426Z INFO ex7::test: 算法: 插入排序 | 比较: 970591 | 移动: 968597
2025-12-22T05:01:19.949645Z INFO ex7::test: 算法: 希尔排序 | 比较: 156710 | 移动: 148767
2025-12-22T05:01:20.075452Z INFO ex7::test: 算法: 冒泡排序 | 比较: 1998790 | 移动: 2899533
2025-12-22T05:01:20.126713Z INFO ex7::test: 算法: 选择排序 | 比较: 1999000 | 移动: 5973
2025-12-22T05:01:20.129949Z INFO ex7::test: 算法: 堆排序 | 比较: 37755 | 移动: 60588
2025-12-22T05:01:20.132023Z INFO ex7::test: 算法: 快速排序 | 比较: 25649 | 移动: 38115
2025-12-22T05:01:20.134511Z INFO ex7::test: 算法: 归并排序 | 比较: 19412 | 移动: 42698
2025-12-22T05:01:20.134763Z INFO ex7::test: === 第 5 组测试 | 数据量: 5000 ===
2025-12-22T05:01:20.396978Z INFO ex7::test: 算法: 插入排序 | 比较: 6203283 | 移动: 6198287
2025-12-22T05:01:20.444421Z INFO ex7::test: 算法: 希尔排序 | 比较: 918591 | 移动: 898657
2025-12-22T05:01:21.271658Z INFO ex7::test: 算法: 冒泡排序 | 比较: 12496639 | 移动: 18577998
2025-12-22T05:01:21.593931Z INFO ex7::test: 算法: 选择排序 | 比较: 12497500 | 移动: 14982
2025-12-22T05:01:21.600998Z INFO ex7::test: 算法: 堆排序 | 比较: 107656 | 移动: 171342
2025-12-22T05:01:21.605011Z INFO ex7::test: 算法: 快速排序 | 比较: 68277 | 移动: 100923
2025-12-22T05:01:21.610876Z INFO ex7::test: 算法: 归并排序 | 比较: 55199 | 移动: 120893
2025-12-22T05:01:21.611331Z INFO ex7::test: === 第 6 组测试 | 数据量: 10000 ===
2025-12-22T05:01:22.675283Z INFO ex7::test: 算法: 插入排序 | 比较: 24842700 | 移动: 24832712
2025-12-22T05:01:22.817031Z INFO ex7::test: 算法: 希尔排序 | 比较: 3423814 | 移动: 3383885
2025-12-22T05:01:26.095848Z INFO ex7::test: 算法: 冒泡排序 | 比较: 49978529 | 移动: 74460552
2025-12-22T05:01:27.326666Z INFO ex7::test: 算法: 选择排序 | 比较: 49995000 | 移动: 29973
2025-12-22T05:01:27.342937Z INFO ex7::test: 算法: 堆排序 | 比较: 235350 | 移动: 372729
2025-12-22T05:01:27.352162Z INFO ex7::test: 算法: 快速排序 | 比较: 146882 | 移动: 225297
2025-12-22T05:01:27.364114Z INFO ex7::test: 算法: 归并排序 | 比较: 120507 | 移动: 261739
2025-12-22T05:01:27.364474Z INFO ex7::test: === 第 7 组测试 | 数据量: 100000 ===
test test::test_sort has been running for over 60 seconds
2025-12-22T05:03:33.557852Z INFO ex7::test: 算法: 插入排序 | 比较: 2489615146 | 移动: 2489515158
2025-12-22T05:03:47.811176Z INFO ex7::test: 算法: 希尔排序 | 比较: 323937261 | 移动: 323537347
2025-12-22T05:11:05.291893Z INFO ex7::test: 算法: 冒泡排序 | 比较: 4999918875 | 移动: 7467497442
2025-12-22T05:13:36.252963Z INFO ex7::test: 算法: 选择排序 | 比较: 4999950000 | 移动: 299970
2025-12-22T05:13:36.433015Z INFO ex7::test: 算法: 堆排序 | 比较: 3019688 | 移动: 4725597
2025-12-22T05:13:36.563771Z INFO ex7::test: 算法: 快速排序 | 比较: 1994351 | 移动: 2669799
2025-12-22T05:13:36.738450Z INFO ex7::test: 算法: 归并排序 | 比较: 1536095 | 移动: 3282766
test test::test_sort ... ok
test test::test_sort ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 736.95s
Running unittests src\main.rs (target\debug\deps\ex7-c62cfa010482da9d.exe)
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
Doc-tests ex7
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s对于最后一组，十万数据的排序测试，冒泡排序跑了7分多钟，居然这么慢，插入排序和选择排序跑了两分多钟
shell排序因为步长很短，效果并不好，但是可以优化
二
实现
一道排序算法模板题，但是没有标准库可用，同时要求输出时附带名次且同分同名
既然测试的结果快排最好，那接下来就在快排的基础上改，首先把它变成一个泛型函数：
pub fn quick_sort <T>(&mut self, nums : &mut [T], low: usize, high: usize)
where
T : PartialOrd + Clone,
{
if high > low {
let pi = self.partition(nums, low, high);
if pi > low { // 避免pi = 0发生溢出的情况
self.quick_sort(nums, low, pi - 1);
}
self.quick_sort(nums, pi + 1, high);
}
}
fn partition <T>(&mut self, nums : &mut [T], low: usize, high: usize) -> usize
where
T : PartialOrd + Clone,
{
let pivot = nums[high].clone();
let mut index = low ;
for j in low..high {
if self.compare(pivot.clone(), nums[j].clone()){
index += 1;
nums.swap(index -1,j);
self.bench.move_time += 3;
}
}
nums.swap(index,high);
index
}
pub fn compare<T: PartialOrd>(&mut self, num1 : T, num2 : T) -> bool{
self.bench.compare_time += 1;
num1 > num2
}compare函数的比较对象并没有写成引用，这导致每次调用compare会移交所有权，而循环在继续，所以不得不.clone()，但这又会造成不必要的开销。i32类型时没有所有权问题是因为i32具有copy特征，其表示按位复制，当实现了copy特征后传参就会变成按位复制而非移动所有权。如果我传入一个指针，它会在函数结束被free掉，在自己的生命周期结束再被free，显然rust不会允许这种事情发生。涉及堆的、文件句柄、连接等的数据都无法实现copy特征
按理说compare的参数应当是引用，这是最标准的写法，这里为避免大面积修改clone了事了
接下来是Student结构体的实现，单独划分出一个字段记录名次，同时实现必要的特征
#[derive(Debug, Clone)]
pub struct Student{
id : u64,
name : String,
math : i32,
chinese : i32,
english : i32,
order : usize,
}
impl Student{
pub fn new(id : u64, name : String, math : i32, chinese : i32, english : i32) -> Self{
Self{
id,
name,
math,
chinese,
english,
order : 0,
}
}
}
impl fmt::Display for Student{
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let total = self.math + self.chinese + self.english;
write!(f,"学号：{}, 姓名：{} 总分:{}, 语文：{} 数学：{}英语：{}",self.id,self.name,total,self.chinese,self.math,self.english)
}
}
impl PartialEq for Student{
fn eq(&self, other: &Self) -> bool{
let t1 = self.math + self.chinese + self.english;
let t2 = other.math + other.chinese + other.english;
t1 == t2
}
}
impl PartialOrd for Student{
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
let t1 = self.math + self.chinese + self.english;
let t2 = other.math + other.chinese + other.english;
t1.partial_cmp(&t2)
}
}然后是核心的排序输出：
pub fn sort(mut s : Vec<Student>){
let mut sort_instance = Sort::new();
let len = s.len();
sort_instance.quick_sort(&mut s, 0, len - 1);
let mut current_score = 0;
let mut current_order = 0;
for i in (0..len).rev(){
let order = len - 1 - i;
let score = s[i].chinese + s[i].math + s[i].english;
let mut index = order;
if current_score == score {
index = current_order;
}else{
current_order = index;
current_score = score;
}
info!("第{}名，{}",index + 1,s[i]);
}
}这个名次处理感觉实现得笨笨的;总分应该单独维护一个字段的。倒序遍历列表输出，测试：
#[test]
fn test_2(){
let _ = tracing_subscriber::fmt()
.with_max_level(LevelFilter::INFO)
.with_test_writer()
.try_init();
let mut data = generate_test_data(100_00);
Student::sort(data.clone());
}
pub fn generate_test_data(count: usize) -> Vec<Student> {
// 预分配内存，避免 vector 扩容带来的性能损耗
let mut rng = rand::rng();
let mut students = Vec::with_capacity(count);
for i in 0..count {
students.push(Student::new(
i as u64,
format!("Student_{}", i),
rng.random_range(0..=100), // 数学
rng.random_range(0..=100), // 语文
rng.random_range(0..=100), // 英语
));
}
students
}输出belike:
2025-12-23T07:29:15.759951Z INFO ex7: 第99989名，学号：42516, 姓名：Student_42516 总分:7, 语文：2 数学：1英语：4
2025-12-23T07:29:15.760054Z INFO ex7: 第99989名，学号：65695, 姓名：Student_65695 总分:7, 语文：1 数学：1英语：5
2025-12-23T07:29:15.760159Z INFO ex7: 第99992名，学号：41828, 姓名：Student_41828 总分:6, 语文：6 数学：0英语：0
2025-12-23T07:29:15.760265Z INFO ex7: 第99992名，学号：93845, 姓名：Student_93845 总分:6, 语文：4 数学：2英语：0
2025-12-23T07:29:15.760370Z INFO ex7: 第99992名，学号：99254, 姓名：Student_99254 总分:6, 语文：3 数学：2英语：1
2025-12-23T07:29:15.760447Z INFO ex7: 第99995名，学号：88285, 姓名：Student_88285 总分:5, 语文：1 数学：3英语：1
2025-12-23T07:29:15.760566Z INFO ex7: 第99996名，学号：78260, 姓名：Student_78260 总分:4, 语文：1 数学：3英语：0
2025-12-23T07:29:15.760702Z INFO ex7: 第99996名，学号：69322, 姓名：Student_69322 总分:4, 语文：2 数学：0英语：2
2025-12-23T07:29:15.760823Z INFO ex7: 第99998名，学号：38750, 姓名：Student_38750 总分:3, 语文：2 数学：0英语：1
2025-12-23T07:29:15.760930Z INFO ex7: 第99999名，学号：14388, 姓名：Student_14388 总分:2, 语文：0 数学：1英语：1
2025-12-23T07:29:15.761039Z INFO ex7: 第99999名，学号：96388, 姓名：Student_96388 总分:2, 语文：0 数学：2英语：0
test test::test_2 ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 21.45s简单优化一下
十万条学生数据的测试结果是21秒，然而实验1里只用了不到2毫秒，着实奇怪
首先去掉了日志输出：
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 4.80s提升明显，但还差着数量级
然后加大编译优化
cargo test --release -- --nocapture
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 3.06s没有解决问题，首先的怀疑对象肯定是每次比较clone（心虚），那就把compare的参数改成引用吧
pub fn compare<T: PartialOrd>(&mut self, num1: &T, num2: &T) -> bool {
self.bench.compare_time += 1;
num1 > num2
}结果:
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.06s居然只剩6ms了，快了500倍，可怕，这还包括了生成随机数的时间
比较有意思的是--release ，如果正常打印日志速度变慢了两三倍（18 -> 49s），而去掉日志又变快了一个数量级（67 -> 6 ms）
快排奇怪的变差
接下来测试了5千万、两亿的数据长度，发现堆排序和归并只需要2分钟左右，而快排奇怪地慢到了6min
测试多次结果不变。会是分区策略的影响吗？
fn partition_hoare <T>(&mut self, nums: &mut [T], low: usize, high: usize) -> usize
where
T: PartialOrd,
{
let pivot_index = low;
let mut l = low + 1;
let mut h = high;
loop{
while l <= h && self.compare(&nums[h],&nums[pivot_index] ){
h -= 1;
}
while l <= h && !self.compare(&nums[l],&nums[pivot_index] ){
l += 1;
}
if l > h {
break;
}
nums.swap(h,l);
self.bench.move_time += 3;
l += 1;
h -= 1;
}
nums.swap(pivot_index,h);
self.bench.move_time += 3;
h
}测试结果是几乎没有变化
快排擅长排序散乱的数据，回看测试数据，是在正负10000区间内的随机数，是否是因为对于亿级的数据，这个区间太小碰撞太多？改成了正负一百万，发现快排的速度优势又回来了