java - MergeSort，Java代码不起作用？

合并功能：

static int[] merge(int v[], int start, int middle, int end){
    int i = start, temp, j = middle, k = 0;

    int a[] = new int[end];
    while(j < end && i < middle){
        if(v[i] > v[j]){
            a[k++] = v[j++];
        }
        else{
            a[k++] = v[i++];
        }
    }
    for(temp = i; temp < middle; temp++){
        a[k++] = v[temp];
    }
    for(temp = j; temp < end; temp++){
        a[k++] = v[temp];
    }
    for(i = 0; i < end; i++)
        v[i] = a[i];
    return v;
}

拆分功能：

static int[] split(int v[], int start, int end){
    int array[] = new int[end-start+1];
    for(int i = start, j = 0; i <= end; i++, j++){
        array[j] = v[i];
    }
    return array;
}

MergeSort函数：

static int[] mergesort(int v[], int start, int end) {
    int middle = v.length/2, left, right;
    if(end-start <= 1){
        return v;
    }
    mergesort(split(v, start, middle), start, middle);
    mergesort(split(v, middle+1, end-1), middle+1, end-1);
    merge(v, start, middle, end);
    return v;
}

主要功能：

public static void main(String[] args){
    int v[] = {6,1,8,2,9,3};
    int end = 6, i;
    v = mergesort(v, 0, end);
    for(i = 0; i < end; i++){
        System.out.print(v[i]+" ");
    }
    System.out.println();
}

给定的输出为2 6 1 8 9 3，应为1 2 3 6 8 9

我很确定它在这里：

mergesort(split(v, start, middle), start, middle);
mergesort(split(v, middle+1, end-1), middle+1, end-1);
merge(v, start, middle, end);

这些函数返回一个数组，但是我可以将其分配给什么呢？

最佳答案

这是我的解决方案，它使用列表而不是数组。

public <E extends Comparable<E>> List<E> mergeSort(List<E> unsortedList) {

    if (unsortedList == null || unsortedList.size() < 2) {
        return unsortedList;
    } else {
        List<E> left = new LinkedList<E>();
        List<E> right = new LinkedList<E>();

        int pivot = (1 + unsortedList.size()) / 2;

        while (!unsortedList.isEmpty()) {
            if (pivot > 0) {
                left.add(unsortedList.remove(0));

                pivot--;
            } else {
                right.add(unsortedList.remove(0));
            }
        }
        left = mergeSort(left);
        right = mergeSort(right);

        return merge(left, right);
    }
}

private <E extends Comparable<E>> List<E> merge(List<E> left, List<E> right) {
    List<E> sortedResult = new ArrayList<E>(left.size() + right.size());

    while (!left.isEmpty() && !right.isEmpty()) {
        E leftElem, rightElem;

        leftElem = left.get(0);
        rightElem = right.get(0);

        if (leftElem.compareTo(rightElem) < 0) {
            sortedResult.add(leftElem);

            left.remove(0);
        } else {
            sortedResult.add(rightElem);

            right.remove(0);
        }
    }
    sortedResult.addAll(left);
    sortedResult.addAll(right);

    return sortedResult;
}

输入：


[6、1、3、5、5、1、9、8、7、8]


输出：


[1、3、5、5、5、6、7、8、8、9]

关于java - MergeSort，Java代码不起作用？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26313789/