2

我正在寻找实现冒泡排序。我有以下我编写的代码，它在for循环内使用do循环。我怎样才能使它成为使用两个for循环的冒泡排序？

这是我的代码：

do {
    switched = false;
    for (int i = 1; i < size; i++) {
        if (a[i] < a[i-1]) {
            int temp = a[i];
            a[i] = a[i-1];
            a[i-1] = temp;
            switched = true;
        }
    }
} while (switched);

（这是标记为作业，但这是为期末考试而学习，而不是实际作业。）

4

8 回答 8

6

因为您知道列表中的最后一个元素将始终被排序（因为它冒泡到顶部），所以您可以停在那里。

for(int x = size; x >= 0; x--) {
    bool switched = false;
    for(int i = 1; i < x; i++) {
        if(blah) {
            // swap code here
            switched = true;
        }

    }
    if(!switched) break; // not the biggest fan of this but it gets the job done
}
于 2011-12-19T23:14:40.807 回答
5

有点义务，但是，嘿，你要求它：

for(bool switched=true; switched;)
{
    switched = false;
    for (int i = 1; i < size; i++) {
        if (a[i] < a[i-1]) {
            int temp = a[i];
            a[i] = a[i-1];
            a[i-1] = temp;
            switched = true;
        }
    }
}

两个for循环...

于 2011-12-19T23:09:00.730 回答
3

由于您的内循环将运行的最大次数是size次，因此您知道外循环只能由size.

for (int x = 0; x < size; x++ )
{
    switched = false;
    for (int i = 1; i < size; i++)
    {
        if (a[i] < a[i - 1])
        {
            int temp = a[i];
            a[i] = a[i - 1];
            a[i - 1] = temp;
            switched = true;
        }
    }

    if(switched)
    {
        break;
    }
}
于 2011-12-19T23:19:35.823 回答
1

冒泡排序的一个简单改进是记住上次发生交换的位置。每次通过后，超过该点的元素都会被排序。下一次循环只迭代到前一个高水位线。

void bubble_sort(int *arr, int size)
{
    for (int hwm; size > 1; size = hwm)
    {
        hwm = 0;
        for (int i = 1; i < size; ++i)
        {
            if (arr[i] < arr[i-1])
            {
                std::swap(arr[i], arr[i-1]);
                hwm = i;
            }
        }
    }
}
于 2011-12-20T01:02:37.783 回答
0

您可以通过外部循环运行内部循环size时间而不是检查。为了使其效率稍低一些，您可以每次将内部循环缩短 1 步。switchedfor(int j=0; j<size; ++j)

于 2011-12-19T23:13:23.497 回答
0

保证第一次完整通过循环（即外do循环的第一次迭代）将最大元素放在 position 中a[size - 1]。（你明白为什么吗？）保证下一个完整的传递不会改变它，此外，将第二大元素放在位置a[size - 2]。（再次，你明白为什么吗？）等等。所以第一遍需要i从1to size - 1，但第二遍只需i要从1to ，size - 2第三遍只需i要从1to size - 3，依此类推。总体而言，您最多需要size - 1通过（最后一次通过只是覆盖位置1并比较a[1]以a[0]确保最小的元素就位）。

所以，你的外for循环需要改变max_i，最初设置为size - 1并结束1，你的内for循环需要i从1to改变max_i。

于 2011-12-19T23:14:08.347 回答
0

do考虑循环可以执行的最大次数。

于 2011-12-19T23:18:16.607 回答
0

使用两个 for 循环的一个非常愚蠢的方法如下：

for(bool switched=true;switched;)
{
    switched=false;
    for(int i=1; i<size; ++i)
    {
        if (a[i] < a[i-1]) 
        {
            int temp = a[i];
            a[i] = a[i-1];
            a[i-1] = temp;
            switched = true;
        }
    }
}

一个更严肃的答案可能如下......但现在我想这可能不是冒泡排序：

for(int i=0; i<(size-1); ++i)
{
    for(int j=(i+1); j<(size-1); ++j)
    {
        if(a[i]>a[j])
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
}
于 2011-12-19T23:19:50.040 回答