如何知道排序算法何时完成？

Question

我已经在 Rust 中开发了一个非常基本的排序算法实现，它按照我想要的方式工作，除了一件事。它能够接受一组输入（接受 [3, 6, 2, 1, 9, 4]）并对其进行排序。我让我的程序在每次交换后打印一组新的输出。我想知道的是，我怎么才能真正知道我的排序何时完成？解决后它会显示一个完整的排序并无限地挂在那里。

我能做的是将预期结果硬编码进去，然后检查排序是否匹配，但这很糟糕，原因有二：它破坏了排序的全部目的，而且效率低得可怕而且需要硬编码值，然后没有动态值可以通过算法。这是简单的算法：

loop {
    for num in 0..(nums.len() - 1) {
        if nums[num] > nums[num + 1] {
            let i = nums[num + 1];

            nums[num + 1] = nums[num];

            nums[num] = i;
        }
    }
}

我希望它做的是识别它何时完成排序，并break;脱离我的循环，但是，一旦它被解决，程序就会挂起。

感谢任何帮助！

Answer 1

每次迭代，跟踪数组是否已排序，如果是则中断。

let mut sorted = false;
while !sorted {
    sorted = true;
    for num in 0..(nums.len() - 1) {
        if nums[num] > nums[num + 1] {
            let i = nums[num + 1];
            nums[num + 1] = nums[num];
            nums[num] = i;
            sorted = false;
        }
    }
}

请记住这是一个 O(n^2) 排序，所以我实际上不会将它用于任何事情。

如何知道排序算法何时完成？

How to know when a sorting algorithm has finished?

language-agnostic

sorting

algorithm