c# - 双向冒泡排序 C#

Question

我有一项编写双向冒泡排序程序的家庭作业。有人可以看看我的逻辑是否正确。我不想要代码，因为我想自己弄清楚。我只想对我的理解进行逻辑检查。

据我了解，双向冒泡排序实现了 2 个 for 循环，其中一个从列表中的位置 1 开始，并执行正常的冒泡排序。当第一个 for 循环结束时，第二个 for 循环以相反的方式执行。我只是不完全理解每个循环的终止条件是什么。

for 循环条件会不会是这样的？

循环 1 - for(i = 0; i < Count -i; i++)

循环 2 - for(j = Count - i; j > i; j--)

在每个循环中，将指定交换条件。

谢谢

Answer 1

“经典的”冒泡排序在每次迭代时都会遍历整个数组，因此循环应该是

for(i = 0; i < Count - 1; i++)

和

for(j = Count - 1; j > 0; j--)

两个循环都跳过一个索引:第一个循环跳过最后一个索引，而第二个循环跳过初始索引。这样您的代码就可以安全地将 data[i] 与 data[i+1] 以及 data[j] 与 数据[j-1].

编辑 "optimized"冒泡排序在第 k 次迭代中跳过初始的 k 元素。由于您的冒泡排序是双向的，您将能够跳过初始 k 和尾部 k 元素，如下所示:

 int k = 0;
 do { // The outer loop
     ...
     for(int i = k; i < Count - k - 1; i++)
         ...
     for(int j = Count - k - 1; j > k ; j--)
         ...
     k++;
} while (<there were swaps>);