合并排序与选择排序

Question

我写了这两种排序算法，看起来选择排序比归并排序快，这不是对的吗？我的测试数据是 10 个大小为 5000 到 50000 的随机数组，其中数组中最大可能的数字是 100。

这是我的选择排序实现：

int i, j, iMin;
int n = c.length;

startTime = System.currentTimeMillis();
for (i = 0; i < n - 1; i++) {
    iMin = i;
    for (j = i + 1; j < n; j++)
        if (c[j] < c[iMin]) {
            iMin = j;
            if (sorting) {
                theDelay();
            }
        }

    if (iMin != i) {
        swap(c, iMin, i);
        if (sorting) {
            theDelay();
        }
    }
}
endTime = System.currentTimeMillis();
overallTime = endTime - startTime;
// System.out.println(overallTime);

theDelay() 方法只是延迟排序算法在其中运行的线程，以便可视化图形可以绘制到 JPanel 以显示正在执行的排序，在此测试用例中它被忽略，因此不会影响我的排序时间。

这是我的合并排序实现：

public void mergeSort(int[] d) throws InterruptedException {
    startTime = System.currentTimeMillis();
    MergeSort(d, 0, d.length - 1);
    endTime = System.currentTimeMillis();
    overallTime = endTime - startTime;
    //System.out.println("Merge" +overallTime);
}

private void MergeSort(int[] array, int low, int high) throws InterruptedException {
    int[] temp = new int[array.length];
    if (low < high) {
        int middle = low + (high - low) / 2;
        MergeSort(array, low, middle);
        MergeSort(array, middle + 1, high);
        ReMerge(array, temp, low, middle, high);
    }
}

private void ReMerge(int[] array2, int[] temp, int low, int middle, int high) throws InterruptedException {
    for (int i = low; i <= high; i++) {
        temp[i] = array2[i];
    }
    int i = low;
    int j = middle + 1;
    int k = low;

    while (i <= middle && j <= high) {
        if (temp[i] <= temp[j]) {
            array2[k] = temp[i];
            i++;
            if (sorting) {
                theDelay();
            }
        } else {
            array2[k] = temp[j];
            j++;
            if (sorting) {
                theDelay();
            }
        }
        k++;
    }
    while (i <= middle) {
        array2[k] = temp[i];
        k++;
        i++;
        if (sorting) {
            theDelay();
        }
    }
}

我的实现中是否有某些因素会影响完成合并排序所需的时间？？？

Answer 1

你有：

private void MergeSort(int[] array, int low, int high) throws InterruptedException
{
    int[] temp = new int[array.length];

当然，在递归的每一步分配长度为5000到50000的数组会使算法变慢。尝试重复使用相同的临时数组。

合并排序与选择排序

Merge Sort vs Selection Sort

java

algorithm

sorting

mergesort

selection-sort