冒泡与选择排序的 Java 执行运行时间

Question

我是一名新手程序员，目前正在休假，所以我只是想在重新开始上学之前提高自己的技能。我已经编写了一些代码来创建一个包含 100 个元素的数组，并使用 0 到 250 之间的随机数填充所有 100 个索引。

我已经编写了使用冒泡排序算法和选择排序算法对该数组进行排序的代码(我计划执行所有已知的数组排序算法并比较执行时间。)我注意到我的选择排序运行时间比冒泡排序。

运行示例:冒泡排序时间:7.45 毫秒 ------ 选择排序时间:0.15 毫秒

所以我的问题是..我是不是搞砸了，或者这些结果是正常的吗？

这是我的代码:

import java.util.*;

public class Bubble {

        private static int[] myArray;
        private static int[] myBubbleArray;
        private static int[] mySelectionArray;


public static void main(String args[]){

    createList();
    fillArray();
    print("Original Array: ", myArray);
    long selectionStartTime = System.nanoTime();
    selectionSortArray(mySelectionArray);
    double selectionElapsedTime = (System.nanoTime() - selectionStartTime) / 1000000.0;     
    print("Selection Sorted Array: ", mySelectionArray);
    System.out.printf("Total execution time for selection sort is %.2f ms\n", selectionElapsedTime);
    long bubbleStartTime = System.nanoTime();
    bubbleSortArray(myBubbleArray);
    double bubbleElapsedTime = (System.nanoTime() - bubbleStartTime) / 1000000.0;
    print("Bubble Sorted Array: ", myBubbleArray);
    System.out.printf("Total execution time for bubble sort is %.2f ms\n", bubbleElapsedTime);
}

private static int[] selectionSortArray(int[] array) {
    int first;
    int temp;
    for(int i=array.length -1; i > 0; i--){
        first = 0;
        for(int j = 1; j <= i; j++){
            if(array[j] > array[first]) first = j;
        }
        temp = array[first];
        array[first] = array[i];
        array[i] = temp;
    }
    return mySelectionArray;
}

private static int[] bubbleSortArray(int[] array) {
    boolean swapped = true;
    int temp;
    while(swapped){
        swapped = false;
        for(int i = 0; i < array.length-1; i ++){
            for(int j = 1; j < array.length - i; j++){
                if(array[i] > array[i+1]){
                    temp = array[i];
                    array[i] = array[i+1];
                    array[i+1] = temp;
                    swapped = true;
                }
            }
        }
    }
    return myBubbleArray;
}

public static int[] createList(){
    myArray = new int[100];
    return myArray;
}

public static void print(String n, int[] array){
    System.out.print(n);
    for(int i = 0; i < array.length; i ++){
        System.out.print(array[i]+ " ");
    }
    System.out.println();
}

public static void fillArray(){
    for(int i = 0; i < myArray.length-1; i ++){
        Random rand = new Random();
        myArray[i] = rand.nextInt(250);
    }
    myBubbleArray = Arrays.copyOf(myArray, myArray.length);
    mySelectionArray = Arrays.copyOf(myArray, myArray.length);
}
}

Answer 1

如需深入解答，go here .具体总结一下，冒泡排序平均每个条目需要n/4次交换(每个条目从其初始位置按元素移动到最终位置，每个交换涉及两个条目)，而选择排序只需要1(一旦找到最小值/最大值，它就会交换一次到数组的末尾。

在比较次数方面，冒泡排序需要k×n次比较，其中k是一个条目的初始位置和最终位置之间的最大距离，对于均匀分布的初始值，通常大于n/2。然而，选择排序总是需要 (n−1)×(n−2)/2 次比较。