为什么冒泡排序算法通常这样计算长度？

Question

所以我只是想了解 bubblesort（当我也看到这种东西时它可能对我的其他算法有帮助）如何与嵌套的 for 循环一起工作。

我注意到大多数人会这样循环：

public static void BubbleSort(int[] arr, int arr_size)
{
    int i, j, temp;
    bool swapped;
    for (i = 0; i < arr_size - 1; i++)
    {
        swapped = false;
        for (j = 0; j < arr_size - i -1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (swapped == false)
        {
            break;
        }
    }            
}

我是这样做的（只是略有不同；注意嵌套循环大小检查：

public static void BubbleSort(int[] arr, int arr_size)
{
    int i, j, temp;
    bool swapped;
    for (i = 0; i < arr_size - 1; i++)
    {
        swapped = false;
        for (j = 0; j < arr_size - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (swapped == false)
        {
            break;
        }
    }            
}

它似乎适用于我目前所做的每项检查。

我想总结一下，我想知道为什么第一个循环的大小为 - 1（我知道这是因为末尾有空格）而嵌套循环的大小为 - i - 1 （至少我见过很多）。感谢您的任何反馈！

Answer 1

内循环的效果：

for (j = 0; j < arr_size - i - 1; j++)
{
    if (arr[j] > arr[j + 1])
    {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
    }
}

正在寻找数组中的最大元素并将其放置到最后一个位置。因此，对于 i == 0（来自外循环的索引），它将它移动到最后一个数组位置。对于i == 1，数组的总最大元素已经在最后一个数组位置，不需要再处理。对于 i == 2 等，情况是一样的。换句话说，数组从 'backward' 开始按 'bubbling'（因此算法的名称）排序，每次迭代的最大元素。

Wikipedia 上有一个很好的分步示例。

在您的第二个示例中，通过省略 for 循环子句中的 - i，您只是不必要地检查先前（外循环）迭代中已经存在的数组元素，因此不能改了。

为什么冒泡排序算法通常这样计算长度？

Why is the length usually calculated this way for BubbleSort algorithm?

c#

bubble-sort