sorting - 为什么这种部分快速排序实现比标准库排序慢这么多？

Question

显然，std 库的实现总是比我的要快得多，但是在快速的计算机上完成 773 x 1031 图像需要 3 分钟左右的时间。使用相同的比较器，标准库需要 4 秒来对整个图像进行排序。任何想法为什么我的代码这么慢？

fn partial_quick_sort(img: &mut Bitmap, cmp: &BoxedPixelComparator) {
    // buffer is a Vec of Pixel structs - Pixel { r: u8, g: u8, b: u8, a: u8 }
    let max_depth = img.buffer.len()/200;
    println!("{}", max_depth); // For the input image I'm testing with, this prints 3984

    let mut queue = VecDeque::new();
    queue.push_back(img.buffer.as_mut_slice());

    let mut depth = 0;
    loop {
        let buffer_opt = queue.pop_front();
        if buffer_opt.is_none() {
            break;
        }
        let buffer = buffer_opt.unwrap();
        if depth >= max_depth || buffer.len() <= 1 {
            continue;
        }
        let pivot_idx = buffer.len() - 1;

        // cmp is a comparator function, which just compares the sums of two pixels
        let (left, _pivot, right) = buffer.partition_at_index_by(pivot_idx, cmp);
        queue.push_back(left);
        queue.push_back(right);
        depth +=1;
    }

}

Answer 1

该算法最大的问题是这一行:

let pivot_idx = buffer.len() - 1;

快速排序需要一个精心挑选的主元才能高效:理想情况下，主元应该将要排序的数组分成两半。因为你选择了一个支点 索引的 n - 1 ，您将每个切片划分为长度为 n - 1 的未排序前缀和切片末尾的单个“已排序”元素(和空后缀)。 The implementation of partition_at_index* actually special cases the n - 1 case ，所以这个算法基本上是一个选择排序，它是 O(n²)(例如，参见 quicksort worst case condition)。

partition_at_index_by 的文档有点模棱两可，这可能导致您出现此错误:

Reorder the slice with a comparator function such that the element at index is at its final sorted position.

“在 index 处的元素”表示以 index 结尾的元素，而不是从那里开始的那个。

要解决此问题，请将上面的行更改为 buffer.len() / 2 .