为什么冒泡排序比选择排序花费更多时间

Question

我正在尝试使用冒泡排序和选择排序的各种场景。我知道如果我们使用 break 语句，冒泡排序的最佳情况是 O(n)。但是假设即使我没有使用任何 break 语句，也不会有任何交换（因为我们有 if 条件），并且它应该花费与选择排序相同或更少的时间。

但奇怪的是，我花了更多时间。

注意：我采用了已经排序的相同数据集（1 到 900000）。由于我使用的是已经排序的数据集，none 算法将进行任何交换。

请在下面找到程序：

 package sorting;

import java.util.ArrayList;
import java.util.Calendar;
import java.util.Date;
import java.util.List;

public class Sorting<Item extends Comparable>//this Item is a var/field which can only be find while creatng a object and hence it is non static
{

    List<Item> list=new ArrayList<Item>();

    public static void main(String args[])
    {

        Sorting<Integer> ss=new Sorting<Integer>();

        System.out.println("adding item logic started : "+Calendar.getInstance().getTime());
        for(int i=0;i<90000;i++)
        {
            ss.list.add(i);

        }
        System.out.println("adding item logic ended : "+Calendar.getInstance().getTime());
        //selection sort started
        Calendar c1=Calendar.getInstance();
        System.out.println(c1.getTime());
        ss.selectionSort(ss.list);

        Calendar c2=Calendar.getInstance();
        System.out.println(c2.getTime());
        System.out.println("selection sort time taken in seconds : "+(c2.getTimeInMillis()-c1.getTimeInMillis())/1000);
    //  System.out.println(ss.list);


        //bubble sort started
        ss.list=new ArrayList<Integer>();
        for(int i=0;i<90000;i++)
        {
            ss.list.add(i);

        }
        Calendar c3=Calendar.getInstance();
        System.out.println(c3.getTime());
        ss.bubbleSort(ss.list);

        Calendar c4=Calendar.getInstance();
        System.out.println(c4.getTime());
        System.out.println("bubble sort time taken in seconds : "+(c4.getTimeInMillis()-c3.getTimeInMillis())/1000);
    //  System.out.println(ss.list);
    }

    void selectionSort(List<Integer> list)
    {
        for(int i=0;i<list.size();i++)
        {
            int target=(Integer)list.get(i);
            int pos=0;

            for(int j=i+1;j<list.size();j++)
            {//System.out.println(i+"  "+j);
                if(target>(Integer)list.get(j))
                {
                    pos=j;
                    target=(Integer)list.get(j);
                }
            }
            if(pos!=0)
            {
                Integer temp=(Integer)list.get(i);
                list.set(i, (Integer)list.get(pos));
                list.set(pos, temp);


            }



        }
    }

    void bubbleSort(List<Integer> list)
    {

        for(int i=list.size()-1;i>0;i--)
        {
            int status=0;
            for(int j=0;j<=i-1;j++)
            {
                //System.out.println(i+"  "+j);
                if((Integer)list.get(j)>(Integer)list.get(j+1))
                {
                    int temp=(Integer)list.get(j+1);
                    list.set(j+1, (Integer)list.get(j));
                    list.set(j, temp);
                    status++;
                }
            }
            //if(status==0)break;
        }
    }
}

这个程序有 85% 的时间用于冒泡排序，有时它是插入排序所用时间的两倍。

adding item logic started : Fri Jun 26 02:47:13 PDT 2015
adding item logic ended : Fri Jun 26 02:47:13 PDT 2015
Fri Jun 26 02:47:13 PDT 2015
Fri Jun 26 02:47:58 PDT 2015
selection sort time taken in seconds : 44
Fri Jun 26 02:47:58 PDT 2015
Fri Jun 26 02:48:46 PDT 2015
bubble sort time taken in seconds : 56

Answer 1

你混淆了复杂性和运行时间。

例如，如果您有一种算法，总是需要一个小时，则该算法的复杂度为 O(1)。第二种算法 1 个元素需要 1 分钟，2 个元素需要 2 分钟，3 个元素需要 3 分钟，... 该算法的复杂度为 O(n)。复杂性方面，第一种算法更好，但对于 1 到 59 个元素，第二种算法更快。

Answer 2

举个简单的例子有两种情况在冒泡排序中

First Pass:
( 5 1 4 2 8 ) \to ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) \to ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) \to ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Now, the array is already sorted, but the algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )

与选择排序一样

64 25 12 22 11 // this is the initial, starting state of the array

11 25 12 22 64 // sorted sublist = {11}

11 12 25 22 64 // sorted sublist = {11, 12}

11 12 22 25 64 // sorted sublist = {11, 12, 22}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

如在冒泡排序中看到的那样，发生了三遍，而在选择排序中只有一次遍

Answer 3

嗯，正如我在您的代码中看到的，两种算法的迭代次数将相同

for(int i=0;i<list.size();i++)
    for(int j=i+1;j<list.size();j++)

与

相同

for(int i=list.size()-1;i>0;i--)
    for(int j=0;j<=i-1;j++)

所以差异应该取决于每次迭代中发生的事情（我将只采用循环的内部部分，其他我们将省略）。

在冒泡排序中：

if((Integer)list.get(j)>(Integer)list.get(j+1))
{
    int temp=(Integer)list.get(j+1);
    list.set(j+1, (Integer)list.get(j));
    list.set(j, temp);
    status++;
}

由于列表已排序，您不会进入 if，因此您有两个 list.get(something)。

在选择排序中：

if(target>(Integer)list.get(j))
{
    pos=j;
    target=(Integer)list.get(j);
}

但是你不会进入 if，所以你只能得到一个 list.get(something)。

简而言之，通过选择排序，您在每次迭代中执行的操作更少，这可能是使您的程序运行更快的原因。

Answer 4

你说：

"But lets say even if I am not using any break statement, there will not be any swaps (as we have if condition for it), and it should take same or less time as selection sort."

在您的代码中，您注释掉了外循环中的 break 语句：

//如果（状态==0）中断；

如果没有 break 语句，algorithm/code 的复杂度为 O(n^2)，您不会从排序中获得任何好处。

为什么冒泡排序比选择排序花费更多时间

Why bubble sort is taking more time then selection sort

java

algorithm

bubble-sort

selection-sort