algorithm - 如何优化我的归并排序算法？

Question

我写了一个归并排序算法，它比冒泡排序和快速排序花费更多的时间。

有人可以帮我优化一下吗？这是代码。

public static void mergeSort(List<MyElement> array, int left, int right, Comparator<? super MyElement> comp) {
    int mid;
    if(right > left) {
        mid = (right + left) / 2;
        mergeSort(array, left, mid,comp);
        mergeSort(array, mid+1, right, comp);
        merge(array, left, mid, right, comp);
    }

}


public static void merge(List<MyElement> array, int left, int mid, int right, Comparator<? super MyElement> comp) {

    PriorityQueue<MyElement> queue = 
            new PriorityQueue<MyElement>(50, comp);
    for(int i = left; i <= mid;  i++) {
        queue.offer(array.get(i));
    }
    for(int i = mid + 1; i < right;  i++) {
        queue.offer(array.get(i));
    }



    int index = left;
    while(index < right && queue.size() != 0) {
        MyElement item  = queue.remove();
        array.set(index, item);
        index++;
    }

}

提前致谢!

Answer 1

问题出在您的合并方法中。左右两边已经排好序，不需要优先级队列。通过在 merge 之前发生的对 mergeSort 的递归调用对两半进行排序。只需比较每一半的第一个元素并取较小的一个。

此外，array 参数定义为 List。除非是 ArrayList，否则访问单个元素的成本可能很高。