哪一种是真正的冒泡排序，哪一种更好？

发布于 2024-10-06 02:04:33 字数 707 浏览 11 评论 0原文

我和一个朋友争论了以下两种算法的真正的冒泡排序，以及哪种更好，不提哪个是我的，我只是想听听你对这两种算法的这两个问题的回答（写在c++)

1-哪一个才是真正的冒泡排序？
2-哪一个更好？

这是两种算法：

// Number one :
void BubbleSort(int Arr[], int size)
{   for (int i=0;i<size-1;i++)
        for (int j=i+1;j<size;j++)
            if (Arr[i]>Arr[j])
            {   int temp = Arr[i];
                Arr[i] = Arr[j];
                Arr[j] = temp;
}           }

// Number two : 
void BubbleSort(int Arr[], int size)
{   for (int i=0;i<size-1;i++)
        for (int j=0;j<size-1;j++)
            if (Arr[j]>Arr[j+1])
            {   int temp = Arr[j];
                Arr[j] = Arr[j+1];
                Arr[j+1] = temp;
}           }

原文

I had an argument with a friend about the real bubble sort of the following two algorithms, and about which one is better, no mention which one is mine, I just want to hear your answers on these two questions about those two algorithms (written in c++)

1-which one is the real bubble sort?
2-which one is better?

here are the two algorithms :

// Number one :
void BubbleSort(int Arr[], int size)
{   for (int i=0;i<size-1;i++)
        for (int j=i+1;j<size;j++)
            if (Arr[i]>Arr[j])
            {   int temp = Arr[i];
                Arr[i] = Arr[j];
                Arr[j] = temp;
}           }

// Number two : 
void BubbleSort(int Arr[], int size)
{   for (int i=0;i<size-1;i++)
        for (int j=0;j<size-1;j++)
            if (Arr[j]>Arr[j+1])
            {   int temp = Arr[j];
                Arr[j] = Arr[j+1];
                Arr[j+1] = temp;
}           }

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

撑一把青伞 2024-10-13 02:04:33

第二号更接近真实的。所有比较都应该在相邻元素之间进行。

但真正的冒泡排序将采用 while 循环而不是外部 for 循环，并且仅当元素必须时，while 循环才会再次执行在最后一次传递时交换，如下所示：

void BubbleSort(int Arr[], int size) 
{   
    bool swapped;
    do {
        swapped = false;
        for (int j=0;j<size-1;j++)
            if (Arr[j]>Arr[j+1]) {
                int temp = Arr[j];
                Arr[j] = Arr[j+1];
                Arr[j+1] = temp;
                swapped = true;
            }
    } while (swapped);
}

Number Two is closer to the real one. All comparisons should be between adjacent elements.

But the real bubble sort would take a while loop instead of an outer for loop, and the while loop would execute again only if elements had to be swapped on the last pass, like this:

void BubbleSort(int Arr[], int size) 
{   
    bool swapped;
    do {
        swapped = false;
        for (int j=0;j<size-1;j++)
            if (Arr[j]>Arr[j+1]) {
                int temp = Arr[j];
                Arr[j] = Arr[j+1];
                Arr[j+1] = temp;
                swapped = true;
            }
    } while (swapped);
}

回复收藏 0 原文

柏林苍穹下 2024-10-13 02:04:33

嵌套循环冒泡排序的伪代码是：

procedure bubbleSort( A : list of sortable items ) 
  n := length(A)-1
  for(i=0; i<= n; i++) 
     for(j=n; j>i; j--) 
        if A[j-1] > A[j] then
           swap (A[j-1], A[j])
        end if
     end for
  end for
end procedure

这意味着第一个是最接近的，因为内部循环仅迭代 i 之后的元素。您展示的第二种方法有一个内部循环，它会迭代所有元素，即使 i 之前的元素已经排序，因此无需在它们上浪费时间。

这意味着第一种方法也更好。

The pseudocode for the nested loop bubble sort is:

procedure bubbleSort( A : list of sortable items ) 
  n := length(A)-1
  for(i=0; i<= n; i++) 
     for(j=n; j>i; j--) 
        if A[j-1] > A[j] then
           swap (A[j-1], A[j])
        end if
     end for
  end for
end procedure

This means that the first is closest because the inner loop only iterates over elements after i. The second method you showed has an inner loop which iterates over all elements, even though elements before i have already been sorted, so there's no need to waste time on them.

That means the first method is also better.

回复收藏 0 原文