rust 双轴快排非递归

你的名字 2022-10-07 00:51 180阅读 0赞

# rust 双轴快排迭代法 #

思路是用一个Vec当作栈来模拟保存快排的左右边界，思路来自这篇[文章][Link 1]，文章只有普通快排，我改成双轴的实现

partion 函数还是我上篇写的rust双轴快排的函数，只是调用partion的quick\_sort\_iter函数变了，用栈的方式模拟函数而已

fn partion(v: &mut Vec<i32>, l: usize, r: usize) -> (usize, usize) { 
        if v[l] > v[r] { 
            v.swap(l, r);
        }
        let mut left = l + 1;
        let mut right = r - 1;
        let mut i = left;
        while i < right { 
            if v[i] < v[l] { 
                v.swap(i, left);
                left += 1;
            } else if v[i] > v[r] { 
                while v[right] > v[r] { 
                    right -= 1;
                }
                v.swap(i, right);
                right -= 1;
            }
            i += 1;
        }
        left -= 1;
        right += 1;
        v.swap(l, left);
        v.swap(r, right);
        (left, right)
    }
    
    fn quick_sort_iter(v: &mut Vec<i32>) { 
        let mut l;
        let mut r;
        let mut stack = Vec::new();
        stack.push(0);
        stack.push(v.len()-1);
        while !stack.is_empty() { 
            r = stack.pop().unwrap();
            l = stack.pop().unwrap();
            if l < r { 
                let (tmp1, tmp2) = partion(v, l, r);
                if tmp1 > l { 
                    stack.push(l);
                    stack.push(tmp1 - 1);
                }
                if tmp2 > tmp1 { 
                    stack.push(tmp1 + 1);
                    stack.push(tmp2 - 1);
                }
                if r > tmp2 { 
                    stack.push(tmp2 + 1);
                    stack.push(r);
                }
            }
        }
    }
    
    fn main() { 
        let mut v = vec![12, 34, 7, 1, 48, 32, 9, 7, 432, 69, 343, 1, 4, 0];
        quick_sort_iter(&mut v);
        println!("{:?}", v);
    }

[Link 1]: https://www.cnblogs.com/ljy2013/p/4003412.html