时间戳

首页 > 解决方案 > 为什么这种时间复杂度较小的排序算法耗时较长？（已编辑）

java - 为什么这种时间复杂度较小的排序算法耗时较长？（已编辑）

问题描述

我写了两个几乎相同的最简单的排序算法，但是要执行一半以上操作的排序算法需要双倍的时间。我无法理解为什么会这样。

任何指针都将不胜感激，因为我试图理解最有效的排序方式，考虑到不同的情况，这种简单的排序让我感到困惑。

public class Sort{

static long timerStart;
static long timerEnd;
static long passedTime;

public static void main(String[] args) {

        double[] arr = createDoubleArray(10000);
        double[] arr2 = Arrays.copyOf(arr,arr.length);

        startTimer();
        sortDoubleArrayFast(arr);
        stopTimer();
        computationTime();

        startTimer();
        sortDoubleArraySlow(arr2);
        stopTimer();
        computationTime();

}
public static void startTimer(){
    timerStart = System.currentTimeMillis();
}
public static void stopTimer(){
    timerEnd = System.currentTimeMillis();
}
public static void computationTime(){
    passedTime = timerEnd-timerStart;
    System.out.println("The operations took: " +passedTime+"ms");
}
public static double[] createDoubleArray(int size){

    double[] output = new double[size];
    for (int i = 0; i < size; i++) {
        output[i] = Math.random()*10000000;
    }

    return output;
}
public static double[] sortDoubleArraySlow(double[] input){
    double tmp;
    int operationNumber = 0;
    for (int j = 0; j < input.length; j++) {
        for (int i = 0; i < input.length; i++) {
            operationNumber++;
            if(input[i]>input[j]){
                tmp = input[j];
                input[j] = input[i];
                input[i] = tmp;
            }
        }
    }
    System.out.println("Operation number in Slow: "+operationNumber);
    return input;
}
public static double[] sortDoubleArrayFast(double[] input){
    double tmp;
    int operationNumber = 0;
    for (int j = 0; j < input.length-1; j++) {
        for (int i = j+1; i < input.length; i++) {
            operationNumber++;
            if(input[i]>input[j]){
                tmp = input[j];
                input[j] = input[i];
                input[i] = tmp;
            }
        }
    }
    System.out.println("Operation number in Fast: "+operationNumber);
    return input;
}

}

标签： javaarrayssorting

解决方案

我很惊讶这个问题被否决了，因为从评论中可以看出，答案一点也不明显。您的问题的答案“相对”简单 - JIT。当我们有一个每次都做完全相同的事情的循环时，JIT 将它变成一段本机代码并直接执行它。但是，当我们每次执行都改变内部循环时（改变 start i = j + 1），那么 JIT 就不起作用了，所以 JVM 必须重新解释它，这已经造成了时间开销。

推荐阅读