java - 冒泡排序优于选择排序？

Question

根据我的阅读，即使它们的大 Oh 表示法相同，当对数组进行冒泡排序和选择排序时，随着数组大小的增长，选择排序应该优于冒泡排序。

但在我的代码中，随着数组变大，冒泡排序始终优于选择排序。

在程序中，用户指定数组中的项目数，以及应创建和排序包含这么多项目的数组的次数(以获得更准确的结果)。

这是我的代码:

import java.util.Scanner;
import java.util.Random;

public class SelectionSorting
{
  public static int[] arr;
  public static long runningSelectionTime, runningBubbleTime;

   public static void main(String[] args)
   {
     Scanner in = new Scanner(System.in);
     System.out.println("Please enter the number of the items in the array: ");
     int i = in.nextInt();
     System.out.println("Please enter the number of iterations: ");
     int iters = in.nextInt();
     arr = new int[i];
     for (int x = 0; x < iters; x++)
     {
       for (int n = 0; n < i; n++)
       {
         arr[n] = randomness();
        }
       long startSelectionTime = System.nanoTime();
       selectionSort(arr);
       long endSelectionTime = System.nanoTime();
       runningSelectionTime += endSelectionTime - startSelectionTime;
     }
     System.out.println("Selection Sort: ");
     System.out.println("Total running time: " + runningSelectionTime + " and the average is " + runningSelectionTime/iters);

    for (int x = 0; x < iters; x++)
    {
      for (int n = 0; n < i; n++)
      {
        arr[n] = randomness();
      }
      long startBubbleTime = System.nanoTime();
      bubbleSort(arr);
      long endBubbleTime = System.nanoTime();
      runningBubbleTime += endBubbleTime - startBubbleTime;
    }
    System.out.println("Bubble Sort: ");
    System.out.println("Total running time: " + runningBubbleTime + " and the average is " + runningBubbleTime/iters);
   }

   public static void selectionSort(int[] array)
   {
     for (int i = 0; i < array.length - 1; i++)
     {
       int iMin = i;
       for (int j = i + 1; j < array.length; j++)
       {
         if (array[j] < array[iMin]) 
         {
          iMin = j;
         }
       }
       if (iMin != i)
       {
         int temp = array[i];
         array[i] = array[iMin];
         array[iMin] = temp;
       }
     }
  }

   public static void bubbleSort(int[] arr)
   {
     int unsorted = arr.length;
     while (unsorted != 0) 
     {
       int lastSwap = 0;
       for (int i = 1; i < unsorted; i++)
       {
         if (arr[i - 1] > arr[i])
         {
           swap(arr, i, i - 1);
           lastSwap = i;
         }
       }
       unsorted = lastSwap;
     }
   }

   private static void swap(int[] arr, int a, int b)
   {
     int temp = arr[a];
     arr[a] = arr[b];
     arr[b] = temp;
   }

   public static int randomness()
   {
    Random rand = new Random();
    int random = rand.nextInt();
    if (random < 0)
    {
      random = random * -1;
    }
    do {
      random = random / 10;
    } while (random > 100);
    return random;
  }

}

如果尝试输入500和1000，冒泡排序的运行时间会比选择排序短。

有趣的是，如果我去掉变量“iters”，那么结果就是预期的。然而，iters 似乎应该使运行时间更准确，而不是更少。

有什么想法可以解释为什么会这样吗？我做错什么了吗？冒泡排序是否有可能(始终如一)优于选择排序？

(为了防止任何混淆，我已经看到了问题 Why is my Java based Bubble Sort Outperforming my Selection sort and my Insertion Sort? ，但它没有解决相同的问题。)

Answer 1

你的冒泡排序速度更快，因为它不起作用。

      arr[i] = temp;

应该是

      arr[i-1] = temp;

输出为 10000 * 3

选择排序:
总运行时间:216077472，平均值为72025824
冒泡排序:
总运行时间:402583050，平均值为134194350

输出为 500 * 1000

选择排序:
总运行时间:123621068 平均为123621
冒泡排序:
总运行时间:317450183，平均值为317450

使用jdk 7