冒泡排序算法中的这一行是什么意思？

Question

Introduction to programming with C++ 6th edition book，它用C++解释了冒泡排序算法，我理解它，但是有两行代码我不明白为什么它们在代码中，当我试图理解代码我擦除它们，没有任何改变，算法仍然有效。所以我仍然对他们感到困惑。有代码；

int main()
 {
     int numbers[4] = {23, 46, 12, 35};
     int sub = 0; //keeps track of subscripts
     int temp = 0; //variable used for swapping
     int maxSub = 3; //maximum subscript
     int lastSwap = 0; //position of last swap
     char swap = 'Y'; //indicates if a swap was made

     //repeat loop instructions as long as a swap was made
     while (swap == 'Y')
     {
     swap = 'N'; //assume no swaps are necessary

     sub = 0; //begin comparing with first
     //array element

     //compare adjacent array elements to determine
     //compare adjacent array elements to determine
     //whether a swap is necessary
     while (sub < maxSub)
     {
         if (numbers[sub] > numbers[sub + 1])
         {
             //a swap is necessary
             temp = numbers[sub];
             numbers[sub] = numbers[sub + 1];
             numbers[sub + 1] = temp;
             swap = 'Y';
             lastSwap = sub;
         } //end if
         sub += 1; //increment subscript
         } //end while

         maxSub = lastSwap; //reset maximum subscript
     } //end while

     //display sorted array
     for (int x = 0; x < 4; x += 1)
        cout << numbers[x] << endl;
     //end for

     system("pause");
     return 0;
 } //end of main function

所以我不明白 lastSwap = sub 和 maxSub = lastSwap。它们很重要还是我从代码中删除它们是正确的？谁能给我解释一下。

Answer 1

这些行是为了性能（使其运行更快），而不是为了正确性。因此，删除这些行会使它运行变慢，但不会使其无法正确排序。

函数进行交换后，它冒泡了迄今为止看到的最高值 [sub + 1]。如果在那之后，它没有找到更多要交换的东西，这意味着数组的其余部分已经具有排序顺序中的最高值，因此该函数不需要再次查看它们——所有这些数字已经在它们在数组中的正确最终排序位置。因此，对于每次交换，该函数都会将数组位置保存在 lastSwap 中，因此在内部 while 循环结束时，lastSwap 包含最后一次进行交换的位置，并且该函数会将此值存储在 maxSub 中。

然后外层 while 循环从 sub 设置为零的数组开头开始另一次扫描。但是现在maxSub变了，所以内循环

while (sub < maxSub)

只上升到 maxSub 并且不会不必要地扫描数组的其余部分，这些部分必须已经具有排序顺序中的最高值。

这种速度差异在四个数字的数组上不会很明显，但是有足够的数字来排序，节省无用的工作会有回报。

Answer 2

为简单起见，

第一轮冒泡排序 => 数组中的最大元素获得新的适当位置。

第二遍 => 数组中的第二大元素获得新的适当位置。

.

第 N 遍 => 数组中的第 N 个元素获得新的适当位置。

变量lastSwap存储最后一次交换发生的数组的最大索引。

现在，如果对于第一遍，新的合适位置不是数组的最后一个索引，即lastSwap < last index of array，则意味着索引lastSwap已经排序，我们不需要处理它。

每次通过都遵循此规则，并且通过总数的上限（maxSub）设置为lastSwap，从而减少了通过。

使用这两行的优点：

我们优化了在所有遍完成之前对数组进行排序时的遍数。
它还可以在第一遍中检测给定/输入数组是否已排序。

Answer 3

它对算法的正确性没有贡献，而是用来提高冒泡排序算法的速度。该语句存储到目前为止读取的最大气泡的值，因此不会超出该循环。为了更好地理解冒泡排序的实际工作原理。

冒泡排序算法中的这一行是什么意思？

What this lines in bubble sort algorithm means?

c++

bubble-sort