这类案子有拐角吗？

Question

我正试图回到c++，我做了一些包括排序在内的练习。我必须按降序排序一个简单的数组。据我所知，最简单的类型是这样的：

for ( int i = 0; i < array_size; i++ ) {

    for ( int k = 0; k < i; k++ ) {

        if ( array[i] > array[k] ) {

            int temp = array[i];
            array[i] = array[k];
            array[k] = temp;
        }
    }
}

而且效果很好..。但我想知道是否有任何角落的情况下这是行不通的。我问是因为据我所见，我找不到人用这个。我可以找到的大多数示例都类似于以下内容：https://www.geeksforgeeks.org/bubble-sort/

Answer 1

基本案例

让我们检查一下这些琐碎的情况：

• array_size = 0。外部循环立即退出，没有任何变化，因此这是可行的。
• array_size = 1。内部循环立即退出，没有任何变化，因此这是可行的。

归纳步骤

现在假设在外部循环的某个迭代i中，对元素0, 1, ..., i-1进行排序。例如，让i = 3考虑以下示例：

array = 4, 2, 1, 3

现在让我们通过内部循环。每当kth较大时，就用ith元素交换ith元素。

k = 0:  array = 4, 2, 1, 3
k = 1:  array = 4, 3, 1, 2
k = 2:  array = 4, 3, 2, 1

内部循环似乎正确地对数组元素0, 1, ..., i进行排序。

因此，在迭代i结束时，数组元素0, 1, ..., i都被排序。

结论

最后一次迭代是在i = array_size-1。执行此操作后，必须对数组元素0, 1, ..., array_size-1进行排序。但这正是整个array！

Answer 2

С++使用size_t作为足够大的类型来保存大小值，而int变量可能不够。例如，在具有32位int的典型64位平台上，它的最大值为2,147,483,647，因此尝试排序较大的数组将无法工作，并可能导致签名溢出，这是未定义的行为。