双向冒泡排序 c#

Question

我有一个编写双向冒泡排序的作业任务。请问我的逻辑是否正确？我不想要代码，因为我想自己解决它。我只需要检查一下我理解的逻辑是否正确。

根据我的理解，双向冒泡排序需要实现两个循环。第一个循环从列表中的位置1开始，执行正常的冒泡排序。当第一个循环到达末尾时，实现第二个循环并反向工作。我只是不完全理解每个循环的终止条件应该是什么。

每个循环的条件是否如下所示？

循环1 - for(i = 0; i < Count -i; i++) 循环2 - for(j = Count - i; j > i; j--) 在每个循环中，都需要指定交换条件。

谢谢

- user2046257

---

精彩的排序视频：http://www.youtube.com/watch?v=SJwEwA5gOkM - Davin Tryon

这可能更适合在 http://programmers.stackexchange.com/ 或 http://codereview.stackexchange.com/ 上提问。 - Tieson T.

@TiesonT。虽然“程序员”可能是一个合适的词，但“codereview”需要由OP编写的完整、可工作的代码片段。 - Sergey Kalinichenko

我对这个网站还很新，所以任何关于标签使用和发布此类问题的帮助都将不胜感激。 - user2046257

@user2046257，http://stackoverflow.com/faq 可以回答大部分问题。通常会有人告诉你何时“违反规则”。 - Tieson T.

Answer 1

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

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

并且

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

两个循环都跳过了一个索引：第一个循环跳过了最后一个索引，而第二个循环跳过了初始索引。这样，您的代码就可以安全地比较data [i]和data [i + 1]，以及data [j]和data [j-1]。

编辑 "优化的"冒泡排序在第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>);

- Sergey Kalinichenko

---

那么反向迭代不依赖于第一个循环的位置吗？即使第一个循环已经检查过它们，它也总是到达位置1吗？ - user2046257

@user2046257 正确，因为第一次循环可能已经移动了它检查过的数组部分的元素。这是冒泡排序效率低的原因之一。 - Sergey Kalinichenko

技术上说，在第一次遍历后（即上下两次），您不再需要检查第一个或最后一个元素，因为它们已知是最小和最大的元素。因此，i不总是需要从0开始，j也不总是需要在0结束。 - Xantix

@Xantix 那是“优化”冒泡排序。从问题描述来看，这似乎是 OP 正在尝试做的事情，所以我编辑了答案。 - Sergey Kalinichenko

非常感谢大家的帮助。真的非常感激。它对我的编码帮助很大。 - user2046257

Answer 2

双向冒泡排序的工作原理如下：

不同于每次从底部到顶部遍历列表（冒泡排序），你需要从底部开始一次，每隔一次从列表顶部开始。请参考维基百科文章中更好的解释： http://en.wikipedia.org/wiki/Cocktail_sort - Rich

- rich