我正在学习冒泡排序,但每次都容易忘记排序的类型。因此,我试图找到每种排序方法的逻辑含义,以便在回忆排序逻辑时有所帮助:
我无法理解冒泡排序为什么被称为冒泡排序的确切含义?
我正在学习冒泡排序,但每次都容易忘记排序的类型。因此,我试图找到每种排序方法的逻辑含义,以便在回忆排序逻辑时有所帮助:
我无法理解冒泡排序为什么被称为冒泡排序的确切含义?
冒泡排序之所以被称为冒泡,是因为在算法的一个迭代中,最小(或最大)元素将会在数组的末尾(或开头)找到它的最终位置。
因此,在冒泡排序算法的一次迭代中,数组中元素的移动类似于气泡在水中上升的运动方式。
引用自维基百科:
冒泡排序,有时也称为下沉排序,是一种简单的排序算法,它重复地遍历要排序的列表,比较每对相邻项并交换它们如果它们的顺序错误。通过列表的传递重复进行,直到不需要交换,这表明列表已经排序。该算法是一种比较排序,以较小的元素“冒泡”到列表的顶部而得名。
正如其他答案所述,“冒泡排序”之所以被称为这个名字,是因为元素会慢慢地移动到列表的目标末端,类似于气泡向表面移动的方式。
auto bubble_sort(vector<int>& vs)
{
int n = vs.size();
bool swapped = false;
for(int i = 0; i < n-1; ++i) // total # of iterations
{
for(int j = 0; j < n-i-1; ++j) // each iterations bubbles up 1 element
{
if(vs[j] > vs[j+1])
{
swap(vs[j], vs[j+1]);
swapped = true;
}
}
if(!swapped) break;
}
return vs;
}