c++ - C++中的冒泡排序实现

Question

下面的代码用于实现冒泡排序。为什么在这种情况下使用模板？ swapped 变量的目的是什么。即使我从循环代码中删除 swapped 变量和 swapped condition 仍然可以正常工作

#include <algorithm>
#include <iostream>
#include <iterator>

template <typename RandomAccessIterator>
void bubble_sort(RandomAccessIterator begin, RandomAccessIterator end) {
  bool swapped = true;
  while (begin != end-- && swapped) {
    swapped = false;
    for (auto i = begin; i != end; ++i) {
      if (*(i + 1) < *i) {
        std::iter_swap(i, i + 1);
        swapped = true;
      }
    }
  }
}

int main() {
  int a[] = {100, 2, 56, 200, -52, 3, 99, 33, 177, -199};
  bubble_sort(std::begin(a), std::end(a));
  copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
  std::cout << "\n";
}

另一个实现:

template<typename Iterator>
 void bubbleSort(Iterator first, Iterator last)
 {
     Iterator i, j;
     for (i = first; i != last; i++)
         for (j = first; j < i; j++)
             if (*i < *j)
                 std::iter_swap(i, j); // or std::swap(*i, *j);
 }

Answer 1

模板只是为了方便使用不同类型的函数。实现使用迭代器而不是简单数组的函数可以为您省去很多指针和大小方面的麻烦。

swapped 变量向算法表明从 begin 到 end 的最后一次运行没有导致任何交换。这意味着数组已经在这个范围内排序(并且在 end 之后它也被排序，因为这是在之前的传递中处理的)并且不需要循环直到 begin 和 end 迭代器是一样的。如果您删除此检查，该算法将起作用，但在部分排序的数组的情况下可能会导致时间浪费。

让我们看这个例子:

0: {1   2   5   3   4} (begin = 0, end = 4)
1: {1   2   3   4   5} (begin = 0, end = 3)
2: {1   2   3   4   5} (begin = 0, end = 2)
3: {1   2   3   4   5} (begin = 0, end = 1)
4: {1   2   3   4   5} (begin = 0, end = 0)

您可以看到在 0: 之后数组已经排序，但是如果没有 swapped 标志，算法将不会中断并继续检查。如果标志在 1: 之后存在，则 swapped 标志为 false 并且算法退出。