时间戳

首页 > 解决方案 > 实现合并排序算法的具体问题

java - 实现合并排序算法的具体问题

问题描述

爪哇

我正在尝试编写一个合并排序算法，以便按字母顺序对自定义对象列表进行排序，我现在已经查看了我的代码和伪代码几个小时，还没有弄清楚为什么它不起作用，

也许一些新鲜的眼睛可以帮助，

我的代码如下...

    /**
     * Merge Sort Algorithm
     * @param array array to sort
     * @param i - point to start sorting at
     * @param j - point to end sorting at
     */
    public void MergeSort(Movie[] array, int i, int j) {

        if(i < j){
            int m = (i+j)/2;

            MergeSort(array, i, m);
            MergeSort(array, m+1, j);

            merge(array,m);
        }
    }


    void merge(Movie[] array, int m){
        int p = 0;
        int q = m+1;
        int r = 0;
        int j = array.length-1;

        Movie[] temp = new Movie[array.length];

        while(p <= m && q <= j){
            if(array[p].compareTo(array[q]) == 1){
                temp[r++] = array[p++];
            }else{
                temp[r++] = array[q++];
            }
        }

        while (p <= m){
            temp[r++] = array[p++];
        }
        while (q <= j){
            temp[r++] = array[q++];
        }
        System.arraycopy(temp,0,array,0,temp.length);
    }

在测试“a,b,c,d,e,h,y,z”的情况时，输出如下...

a |
b |
d |
e | 
h |
c |
y |
z |

显然这不是按字母顺序排列的，只是无法弄清楚为什么

标签： javaalgorithmsortingmergesort

解决方案

查看您在评论中发布的伪代码，我可以告诉您，您还没有实现给定的伪代码。

The Merge(A[i...j], m) function has the parameters m, which is the mid, the array A and the parameters i and j to define the bounds for the merging in that array. In my opinion the pseudocode is just not precise and bad.

The parameters i and j are used to initialize p and r. In your current implementation you are initializing both with 0, which is not what the pseudocode does.

Your method merge needs those two parameters i and j to define the bounds for the merging.

推荐阅读