algorithm - 为什么我的递归归并排序算法会导致堆栈溢出？

Question

实现归并排序时的递归调用会引发错误。我尝试使用调试宏来查看它是否有一些内存限制而没有运气。

fn merge<T: PartialOrd>(mut v: Vec<T>) -> Vec<T> {
    if v.len() < 1 {
        return v;
    }
    let mut res = Vec::with_capacity(v.len());
    let b = v.split_off(v.len() / 2);
    let a = merge(v);
    let b = merge(b);
    let mut a_it = a.into_iter();
    let mut b_it = b.into_iter();
    let mut a_curr = a_it.next();
    let mut b_curr = b_it.next();
    loop {
        match a_curr {
            Some(ref a_val) => match b_curr {
                Some(ref b_val) => {
                    if a_val < b_val {
                        res.push(a_curr.take().unwrap());
                        a_curr = a_it.next()
                    } else {
                        res.push(b_curr.take().unwrap());
                        b_curr = b_it.next();
                    }
                }
                None => {
                    res.push(a_curr.take().unwrap());
                    res.extend(a_it);
                    return res;
                }
            },
            None => {
                if let Some(b_val) = b_curr {
                    res.push(b_val)
                }
                res.extend(b_it);
                return res;
            }
        }
    }
}

fn main() {
    let v = vec![9, 7, 4, 6, 5, 2, 1, 11];
    let x = merge(v);
    println!("{:?}", x);
}

thread 'main' has overflowed its stack
error: process didn't exit successfully: `target\debug\tescode.exe` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)

标签： algorithmsortingrust

Answer 1

您有堆栈溢出，因为您执行了无限数量的递归调用。这是由于您的退出标准不正确造成的；改用小于或等于：

if v.len() <= 1 {
    return v;
}