为什么冒泡排序需要嵌套循环？

Question

我将开始新的问题.我昨天提出了这个问题,想知道我的程序中有什么问题.下面给出了该程序,你们人们指出,以下程序只进行一次排序,并且还需要一个外部循环.那时我很好,好.但是当我查看程序时,我感到困惑,需要问为什么我们需要外部循环以及排序,因为只有一个循环可以进行排序(在我看来).首先看下面的程序然后我在程序结束时提出我的逻辑.

#include <iostream.h>
#include <conio.h>

using namespace std;

main()
{

    int number[10];
    int temp = 0;
    int i = 0;

    cout << "Please enter any ten numbers to sort one by one: "
         << "\n";

    for (i = 0; i < 10; i++)
    {
        cin >> number[i];
    }

    i = 0;

    for (i = 0; i < 9; i++)
    {

        if (number[i] > number[i + 1])
        {
            temp = number[i + 1];
            number[i + 1] = number[i];
            number[i] = temp;
        }
    }
    i = 0;
    cout << "The sorted numbers are given below:"
         << "\n";

    for (i = 0; i < 10; i++)
    {
        cout << number[i] << "\n";
    }

    getch();
}

我认为具有气泡条件的ONLY循环应该进行排序.查看以下程序循环:

for (i=0;i<9;i++)
if(number[i]>number[i+1])
{
    temp=number[i+1];
    number[i+1]=number[i];
    number[i]=temp;

}

现在我解释一下我在想什么这个循环"应该"做什么.它首先将数字[0]与数字[1]进行比较.如果条件满足,它将执行IF语句的正文.然后我将增加1(i ++).然后在下一次迭代中,比较的值将是数字[1]和数字[2].那么为什么它不会发生并且循环仅在通过后退出？换句话说,可能是我试图要求IF语句不会在for循环中重复？在我看来它确实如此.我非常感谢你的帮助和观点,我的问题可能很小,但这就是我的进步方式.

Answer 1

让我举个例子,让我们只拿3个数字.所以你输入

13, 3 ,1 

现在你开始排序你是如何做到的.所以它比较了13和3, 13 > 3所以切换它们.现在我们有.

3, 13, 1

现在它会比较,因为你说下一对= 13和1 13 > 1所以新订单将是

3, 1, 13

现在你的循环结束了,你错过了比较3和1实际上第一个循环只排序最大的数字!

Answer 2

因为只有一个循环可以进行排序(在我看来)

这是不正确的.在没有详细说明的情况下,由于排序存在问题,因此常量循环不足以进行排序Omega(nlogn).O(1)对于任何算法^1,2而言,一个(常数,包括1)个循环数量是不够的.

考虑输入

5, 4, 3, 2, 1 

单个循环的冒泡排序将:

4, 5, 3, 2, 1
4, 3, 5, 2, 1 
4, 3, 2, 5, 1
4, 3, 2, 1, 5

所以算法最终会得到数组:[ 4, 3, 2, 1, 5],它没有排序.

在一个冒泡排序循环之后,您只能保证最后一个元素到位(在示例中确实会发生).第二次迭代将确保最后两个元素就位,第二n次迭代将确保数组确实已排序,从而产生n循环,这是通过嵌套循环实现的.

(1)外部循环有时被隐藏为递归调用(快速排序是它发生的一个例子) - 但仍然存在循环.
(2)确切地说,基于比较的算法.