为什么通常使用BubbleSort算法以这种方式计算长度？

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等，情况相同。换句话说，该数组是通过“冒泡”（因此算法的名称）从“向后”排序的，因此每次迭代中的最大元素都将排序。

Wikipedia上有一个不错的分步示例。

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