下面的代码用于实现冒泡排序。为什么在这种情况下使用模板？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);
}
不同的容器具有自己的迭代器类型。例如，对于一维数组，使用指针作为迭代器，而对于std :: vector类型的对象，则使用在此模板类中定义的迭代器。
该变量swapped用作是否已对元素进行排序的标准。如果遍历该序列时没有交换元素，则表示该序列已被排序。
考虑到由于该语句，您显示的实现具有未定义的行为
while (begin != end-- && swapped) {
^^^^
因为在范围可以为空时尝试减少最后一个迭代器。因此实现是不正确的。
此外，该算法效率不高。例如，在内部循环的某些迭代之后，数组的尾部可能已经被排序。但是，在外部循环中，最后一个迭代器仅向左移动一个位置。
使用正向迭代器进行冒泡排序就足够了。在这种情况下，即使std::forward_list没有其他容器具有随机访问迭代器，您也可以使用该算法。
这是一个演示程序，显示了如何使用正向迭代器实现该算法。
#include <iostream>
#include <algorithm>
#include <iterator>
#include <forward_list>
template <typename ForwardIterator>
void bubble_sort( ForwardIterator first, ForwardIterator last )
{
for ( ForwardIterator sorted = first; first != last; last = sorted )
{
sorted = first;
for ( ForwardIterator current = first, prev = first; ++current != last; ++prev )
{
if ( *current < *prev )
{
std::iter_swap( current, prev );
sorted = current;
}
}
}
}
int main()
{
int a[] = { 100, 2, 56, 200, -52, 3, 99, 33, 177, -199 };
bubble_sort( std::begin( a ), std::end( a ) );
std::copy( std::begin( a ), std::end( a ),
std::ostream_iterator<int>( std::cout, " " ) );
std::cout << "\n";
std::forward_list<int> lst = { 100, 2, 56, 200, -52, 3, 99, 33, 177, -199 };
bubble_sort( std::begin( lst ), std::end( lst ) );
std::copy( std::begin(lst ), std::end( lst ),
std::ostream_iterator<int>( std::cout, " " ) );
std::cout << "\n";
}
程序输出为
-199 -52 2 3 33 56 99 100 177 200
-199 -52 2 3 33 56 99 100 177 200
在程序中，这里使用了一个数组和一个类型的对象，std::forward_list并且该算法可以应用于两个容器。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句