为什么冒泡排序需要更多时间然后选择排序-Java 学习之路

我正在尝试使用冒泡排序和选择排序的各种方案 . 我知道如果我们使用break语句，冒泡排序的最佳情况是O（n） . 但是我们可以说，即使我没有使用任何break语句，也不会有任何交换（因为我们有条件），并且选择排序应该花费相同或更少的时间 .

但奇怪的是它花了更多时间给我 .

Note ：我已经采用了已经排序的相同数据集（1到900000） . 而且由于我使用已排序的数据集，因此没有任何算法可以进行任何交换 .

请找到以下程序：

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

4 回答

0
好吧，正如我在您的代码中看到的，两种算法中的迭代次数都是相同的
```
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（东西） .

在选择排序：
```
if(target>(Integer)list.get(j))
{
    pos=j;
    target=(Integer)list.get(j);
}
```
但你不会进入if，所以你只得到一个list.get（某事） .

简而言之，通过选择排序，您在每次迭代中执行的操作都会减少，这可能会使您的程序运行得更快 .
回复于 2024-04-29T23:22:42+08:00
4

你混淆 complexity 和 running time .

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

回复于 2024-04-29T23:22:42+08:00

举一个简单的例子，这是冒泡排序中的两种情况

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}

如在冒泡排序中看到的那样，有三个过程发生，而在选择排序中只有一个过程

回复于 2024-04-29T23:22:42+08:00

0

你说：

“但是我们可以说，即使我没有使用任何中断声明，也不会有任何掉期（因为我们有条件），并且选择排序应该花费相同或更少的时间 . ”

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

//如果（状态== 0）断裂;

没有break语句，算法/代码是O（n ^ 2），并且您没有从它被排序中获得任何好处 .

回复于 2024-04-29T23:22:42+08:00

为什么冒泡排序需要更多时间然后选择排序

4 回答

相关问题