(Java) 对数组中的整数进行排序和记录时间

Question

我在使用这个程序时遇到了问题。我正在尝试记录每种排序方法在 10 次运行的试验中执行所花费的最快、最慢和平均时间。

唯一看起来有效的是第一种排序方法（选择）。该程序在一个数组中使用 50000 个随机整数。谁能帮我找出为什么时间只适用于一种方法而不适用于其他 5 种方法？其他排序方法的每个试用代码都与第一种相同，但似乎无法正常工作。

import java.util.Random;
import java.util.Arrays;
import java.util.concurrent.TimeUnit;

public class Sorting
{
    public static void main(String[] args)
    {
        int N = 50000;
        int randNum[] = new int[N];
        long total = 0;
        long min = Integer.MAX_VALUE;
        long max = Integer.MIN_VALUE;

    Random rand = new Random();
    for(int i = 0; i < N; i++)
    {
        randNum[i] = rand.nextInt(N);
    }

    System.out.println("_____Selection Sort_____");
    for(int trial = 1; trial <= 10; trial++)
    {
        long start = System.nanoTime();
        SelectionSort(randNum);
        long end = System.nanoTime();
        long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
        total = total + time;
        if(time < min)
        {
            min = time;
        }
        if(time > max)
        {
            max = time;
        }
    }
    System.out.println("The fastest time: " + min + " nanoseconds");
    System.out.println("The slowest time: " + max + " nanoseconds");
    System.out.println("The average time: " + (total/10) + " nanoseconds");

    System.out.println("\n_____Insertion Sort_____");
    for(int trial = 1; trial <= 10; trial++)
    {
        long start = System.nanoTime();
        InsertionSort(randNum);
        long end = System.nanoTime();
        long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
        total = total + time;
        if(time < min)
        {
            min = time;
        }
        if(time > max)
        {
            max = time;
        }
    }
    System.out.println("The fastest time: " + min + " nanoseconds");
    System.out.println("The slowest time: " + max + " nanoseconds");
    System.out.println("The average time: " + (total/10) + " nanoseconds");

    System.out.println("\n_____Bubble Sort_____");
    for(int trial = 1; trial <= 10; trial++)
    {
        long start = System.nanoTime();
        BubbleSort(randNum);
        long end = System.nanoTime();
        long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
        total = total + time;
        if(time < min)
        {
                min = time;
            }
            if(time > max)
            {
                max = time;
            }
        }
    System.out.println("The fastest time: " + min + " nanoseconds");
    System.out.println("The slowest time: " + max + " nanoseconds");
    System.out.println("The average time: " + (total/10) + " nanoseconds");

        System.out.println("\n_____Merge Sort_____");
        for(int trial = 1; trial <= 10; trial++)
        {
            long start = System.nanoTime();
            MergeSort(randNum);             long end = System.nanoTime();
            long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
            total = total + time;
            if(time < min)
            {
                min = time;
            }
            if(time > max)
            {
                max = time;
            }
        }
        System.out.println("The fastest time: " + min + " nanoseconds");
        System.out.println("The slowest time: " + max + " nanoseconds");
        System.out.println("The average time: " + (total/10) + " nanoseconds");

        System.out.println("\n_____Quick Sort_____");
        for(int trial = 1; trial <= 10; trial++)
        {
            long start = System.nanoTime();
            QuickSort(randNum, 0, randNum.length - 1);
            long end = System.nanoTime();
            long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
            total = total + time;
            if(time < min)
            {
                min = time;
            }
            if(time > max)
            {
                max = time;
            }
        }
        System.out.println("The fastest time: " + min + " nanoseconds");
        System.out.println("The slowest time: " + max + " nanoseconds");
        System.out.println("The average time: " + (total/10) + " nanoseconds");

        System.out.println("\n_____No Comparison Sort_____");
        for(int trial = 1; trial <= 10; trial++)
        {
            long start = System.nanoTime();
            NoComparisonSort(randNum, 0, randNum.length - 1);
            long end = System.nanoTime();
            long time = TimeUnit.MILLISECONDS.convert(end - start, TimeUnit.NANOSECONDS);
            total = total + time;
            if(time < min)
            {
                min = time;
            }
            if(time > max)
            {
                max = time;
            }
        }
        System.out.println("The fastest time: " + min + " nanoseconds");
        System.out.println("The slowest time: " + max + " nanoseconds");
        System.out.println("The average time: " + (total/10) + " nanoseconds");
}

public static int[] SelectionSort(int num[])
{
     int i, j, first, temp;  
     for (i = num.length - 1; i > 0; i-- )  
     {
          first = 0;
          for(j = 1; j <= i; j ++) 
          {
               if(num[j] < num[first] )         
                 first = j;
          }
          temp = num[first];
          num[first] = num[i];
          num[i] = temp; 
      }
    return num;           
}

public static void InsertionSort(int [] num)
{
     int j;
     int key;
     int i;

     for (j = 1; j < num.length; j++)
     {
         key = num[j];
         for(i = j - 1; (i >= 0) && (num[ i ] < key); i--)
         {
             num[i+1] = num[i];
         }
         num[i+1] = key;
     }
}

public static void BubbleSort(int [] num)
{
     int j;
     boolean flag = true;
     int temp;

     while (flag)
     {
         flag = false;
         for(j = 0; j < num.length -1; j++)
         {
             if (num[j] < num[j+1])
             {
                 temp = num[j];
                 num[j] = num[j+1];
                 num[j+1] = temp;
                 flag = true;
             } 
         } 
     } 
}

public static void QuickSort(int[] num, int low, int high)
{    
    if (num == null || num.length == 0)
        return;

    if (low >= high)
        return;

    int middle = low + (high - low) / 2;
    int pivot = num[middle];

    int i = low, j = high;
    while (i <= j) {
        while (num[i] < pivot)
        {
            i++;
        }

        while (num[j] > pivot)
        {
            j--;
        }

        if (i <= j)
        {
            int temp = num[i];
            num[i] = num[j];
            num[j] = temp;
            i++;
            j--;
        }
    }

    if (low < j)
        QuickSort(num, low, j);

    if (high > i)
        QuickSort(num, i, high);
}

public static void MergeSort(int[] array)
{
    if (array.length > 1)
    {
        int[] left = leftHalf(array);
        int[] right = rightHalf(array);

        MergeSort(left);
        MergeSort(right);

        merge(array, left, right);
    }
}

public static int[] leftHalf(int[] array)
{
    int size1 = array.length / 2;
    int[] left = new int[size1];
    for (int i = 0; i < size1; i++)
    {
        left[i] = array[i];
    }
    return left;
}

public static int[] rightHalf(int[] array)
{
    int size1 = array.length / 2;
    int size2 = array.length - size1;
    int[] right = new int[size2];
    for (int i = 0; i < size2; i++)
    {
        right[i] = array[i + size1];
    }
    return right;
}

public static void merge(int[] result, int[] left, int[] right)
{
    int i1 = 0;
    int i2 = 0;

    for (int i = 0; i < result.length; i++)
    {
        if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2]))
        {
            result[i] = left[i1];
            i1++;
        }
        else
        {
            result[i] = right[i2];
            i2++;
        }
    }
}

public static void NoComparisonSort(int[] a, int low, int high)
{
    int[] counts = new int[high - low + 1];
    for (int x : a)
        counts[x - low]++;

    int current = 0;
    for (int i = 0; i < counts.length; i++)
    {
        Arrays.fill(a, current, current + counts[i], i + low);
        current += counts[i];
    }
}
}

输出显示为： _____Selection Sort_____ 最快时间：3307纳秒最慢时间：7117 纳秒平均时间：6399 纳秒

_____Insertion Sort_____ 最快时间：0纳秒最慢时间：7117 纳秒平均时间：6399 纳秒

_____Bubble Sort_____ 最快时间：0纳秒最慢时间：7117 纳秒平均时间：6400 纳秒

_____Merge Sort_____ 最快时间：0纳秒最慢时间：7117 纳秒平均时间：6412纳秒

_____Quick Sort_____ 最快时间：0纳秒最慢时间：7117 纳秒平均时间：6416 纳秒

_____No比较Sort_____ 最快时间：0纳秒最慢时间：7117 纳秒平均时间：6419 纳秒

Answer 1

问题是您没有重新初始化 min 和 max。您应该在每次排序前重做此操作：

min = Integer.MAX_VALUE;
max = Integer.MIN_VALUE;

(Java) 对数组中的整数进行排序和记录时间

(Java) Sorting Integers in Array and Recording Time

java

arrays

sorting

random

time