5

我要开始新的问题了。我昨天提出了这个问题，想知道我的程序有什么问题。该程序在下面给出，你们指出，下面的程序只进行一次排序，并且还需要一个外循环。那个时候我就好喜欢OK。但是当我再次查看程序时，我感到困惑，需要问为什么我们还需要外循环进行排序，因为只有一个循环可以进行排序（在我看来）。首先看下面的程序，然后我在程序结束时展示我的逻辑。

#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();
}

我认为具有气泡条件的唯一循环应该进行排序。查看程序的以下循环：

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

}

现在我解释一下我在想这个循环“应该”做什么。它将首先将 number[0] 与 number[1] 进行比较。如果满足条件，它将执行 IF 语句主体中的操作。然后 i 将增加 1(i++)。然后在下一次迭代中，比较的值将是 number[1] 和 number[2]。那为什么它没有发生并且循环仅在通过后退出？换句话说，可能是我想问 IF 语句不会在 for 循环中重复吗？在我看来确实如此。我非常感谢您的帮助和意见，我的问题可能很小，但这就是我的进步。

4

4 回答 4

14

让我举个例子，让我们只取3个数字。所以你输入

13, 3 ,1

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

3, 13, 1

现在它会像你说的那样比较下一对 = 13 和 1 13 > 1所以新的订单是

3, 1, 13

现在你的循环已经完成，你错过了比较 3 和 1 实际上第一个循环只对最大的数字进行排序！

于 2012-09-04T08:40:55.340 回答
11

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

这是不正确的。不深入细节，恒定数量的循环不足以排序，因为排序是个Omega(nlogn)问题。意思是，O(1)（常数，包括 1）循环数是不够的 - 对于任何算法1,2。

考虑输入

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]，它没有排序。

经过一个冒泡排序循环后，您只能保证将最后一个元素放在适当的位置（在示例中确实发生了这种情况）。第二次迭代将确保最后 2 个元素就位，n第 th 次迭代将确保数组确实已排序，从而产生n循环，这是通过嵌套循环实现的。

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

于 2012-09-04T08:39:22.453 回答
2

对于冒泡排序，只需将最大元素移动到数组的末尾。所以你需要 n-1 次传递来获得一个排序的数组，这就是你需要其他循环的原因。现在对于您的代码 1 pass 意味着

if(number[0]>number[0+1])
{
    temp=number[0+1];
    number[0+1]=number[0];
    number[0]=temp;

}
if(number[1]>number[1+1])
{
    temp=number[1+1];
    number[1+1]=number[1];
    number[1]=temp;

}
.....6 more times
if(number[8]>number[8+1])
{
    temp=number[8+1];
    number[8+1]=number[8];
    number[8]=temp;

}

所以你可以看到 IF 语句重复自己，只是在所有 9 个 IF 之后，largets 元素移动到数组的末尾

于 2012-09-04T08:40:53.170 回答
1

这是不正确的，因为

该算法得名于较小元素“冒泡”到列表顶部的方式。（冒泡排序）

所以，在第一个循环结束时，我们得到了最小的元素。所以，为了完成排序，我们必须保持总共 n 个循环。（其中 n = 数字的总大小）

于 2012-09-04T09:00:11.637 回答