合并排序与选择排序

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在递归的每个步骤会使算法慢得多.尝试重用相同的临时数组.