java - 使用字符串实现时，合并排序会生成任意顺序

Question

我正在为作业编写一个程序，但是当我尝试调整合并排序以处理字符串(按字母顺序排序)时，它会生成看似随机的标题顺序，如下所示。我前段时间问过这个问题，但没有得到真正的答案，所以我觉得我需要更好地表达它并包含我的完整代码。

按标题升序

Titanic, 1997 by Paramount, Marvel's The Avengers, 2012 by Disney  Harry Potter and the Deathly Hallows Part 2, 2012 by Warner Brothers  Furious 7, 2015 by Universal  Avengers: Age of Ultron, 2015 by Disney  Avatar, 2009 by Fox  Star Wars: The Force Awakens, 2015 by Disney  Jurassic World, 2015 by Universal  Avengers: Infinity War, 2018 by Disney  Black Panther, 2018 by Disney  

I have to arrange alphabetically specifically using merge sort that I write myself, and while I have tried all sorts of different configurations of the compareTo statement, like:

else if ((a[j].getTitle()).compareTo(a[i].getTitle()) > 0)
else if ((a[i].getTitle()).compareTo(a[j].getTitle()) < 0)
else if ((a[i].getTitle()).compareTo(a[j].getTitle()) > 0)

它们都不起作用。

/**
 * Write a description of class MovieV3Tester here.
 *
 * @author (your name)
 * @version (a version number or a date)
 */
public class MovieV3Tester
{
    public static void main(String [] args)
    {
        MovieV3 [] movies = {new MovieV3 ("Avatar", 2009, "Fox"), 
                           new MovieV3 ("Titanic", 1997, "Paramount"), 
                           new MovieV3 ("Star Wars: The Force Awakens", 2015, "Disney"),
                           new MovieV3 ("Avengers: Infinity War", 2018, "Disney"),
                           new MovieV3 ("Jurassic World", 2015, "Universal"),
                           new MovieV3 ("Marvel's The Avengers", 2012, "Disney"),
                           new MovieV3 ("Furious 7", 2015, "Universal"),
                           new MovieV3 ("Avengers: Age of Ultron", 2015, "Disney"),
                           new MovieV3 ("Black Panther", 2018, "Disney"),
                           new MovieV3 ("Harry Potter and the Deathly Hallows Part 2", 2012, "Warner Brothers")
                           };
    System.out.println("Original\n");
    print(movies);
    System.out.println("\nBy Title Ascending\n");
    mergeTitle(movies, 0, (movies.length-1));
    mergeTitle(movies, 0, (movies.length-1));
    print(movies);
    System.out.println("\nBy Year Ascending\n");
    mergeYear(movies, 0, (movies.length-1));
    print(movies);
}
public static void print(MovieV3 [] movies)
{
    for(MovieV3 movie : movies)
    {
        System.out.println(movie.getTitle() + ", " + movie.getYear() + " by " + movie.getStudio());
    }
}
public static void merge( MovieV3[] a, int low, int mid, int high, int compare)
{
    MovieV3[] temp = new MovieV3[ high - low + 1 ];

    int i = low, j = mid + 1, n = 0;
    if(compare == 1)
    {
    while( i <= mid || j <= high )
    {
        if( i > mid )
        {
            temp[ n ] = a[ j ];
            j++;
        }
        else if( j > high )
        {
            temp[ n ] = a[ i ];
            i++;
        }
        else if( a[ i ].getYear() < a[ j ].getYear() )
        {
            temp[ n ] = a[ i ];
            i++;
        }
        else
        {
            temp[ n ] = a[ j ];
            j++;
        }
        n++;
    }
    }
    else if(compare ==2)
    {
        while( i <= mid || j <= high )
    {
        if( i > mid )
        {
            temp[ n ] = a[ j ];
            j++;
        }
        else if( j > high )
        {
            temp[ n ] = a[ i ];
            i++;
        }
        else if((a[ j ].getTitle()).compareTo(a[i].getTitle())< 0)
        {
            temp[ n ] = a[ i ];
            i++;
        }
        else
        {
            temp[ n ] = a[ j ];
            j++;
        }
        n++;
    }
    }
    else
    {
        while( i <= mid || j <= high )
    {
        if( i > mid )
        {
            temp[ n ] = a[ j ];
            j++;
        }
        else if( j > high )
        {
            temp[ n ] = a[ i ];
            i++;
        }
        else if( a[ i ].getYear() < a[ j ].getYear() )
        {
            temp[ n ] = a[ i ];
            i++;
        }
        else
        {
            temp[ n ] = a[ j ];
            j++;
        }
        n++;
    }
    }
    for( int k = low ; k <= high ; k++ )
        a[ k ] = temp[ k - low ];
} // end of merge
public static void mergeYear(MovieV3[] a, int low, int high)
{
    if( low == high )
        return;

    int mid = ( low + high ) / 2;

    mergeYear( a, low, mid );       // recursive call
    mergeYear( a, mid + 1, high);   // recursive call

    //Debugging Statements 
    //uncomment to print the listings after each pass through the sort
    //System.out.println("\nCurrent list");
    //for(Movie h : a)  
    //    if( h != null) System.out.printf("$%10.2f \n", h.getCost() );

    merge( a, low, mid, high, 1);
}

public static void mergeTitle(MovieV3[] a, int low, int high)
{
    if( low == high )
        return;

    int mid = ( low + high ) / 2;

    mergeYear( a, low, mid );       // recursive call
    mergeYear( a, mid + 1, high);   // recursive call

    //Debugging Statements 
    //uncomment to print the listings after each pass through the sort
    //System.out.println("\nCurrent list");
    //for(Movie h : a)  
    //    if( h != null) System.out.printf("$%10.2f \n", h.getCost() );

    merge( a, low, mid, high, 2);
}
public static MovieV3 [] insertionTitle(MovieV3[] source,int compare)
{
   MovieV3[] dest = new MovieV3[ source.length ];

    for( int i = 0 ; i < source.length ; i++ )
    {
        MovieV3 next = source[ i ];
        int insertIndex = 0;
        int k = i;
        while( k > 0 && insertIndex == 0 )
        {
            if(compare == 1)
            {
            if( next.getTitle().compareTo( dest[k-1].getTitle() ) > 0 )
            {
                insertIndex = k;
            }
            else
            {
                dest[ k ] = dest[ k - 1 ];
            }
            }
            else
            {
            if( next.getTitle().compareTo( dest[k-1].getTitle() ) < 0 )
            {
                insertIndex = k;
            }
            else
            {
                dest[ k ] = dest[ k - 1 ];
            }  
            }
            k--;
        }

        dest[ insertIndex ] = next;

        //Debugging Statements 
        //uncomment to print the listings after each pass through the sort
        //System.out.println("\nPass # " + i);
        //for(MovieV3 h : dest)  
        //    if( h != null) System.out.printf("%-15s \n", h.getCity() );
    } // end of for
    return dest;
}

}

希望它最终会输出以下内容

Avatar, 2009 by Fox, Avengers: Age of Ultron, 2015 by Disney, Avengers: Infinity War, 2018 by Disney, Black Panther, 2018 by Disney, Furious 7, 2015 by Universal, Harry Potter and the Deathly Hallows Part 2, 2012 by Warner Brothers, Jurassic World, 2015 by Universal, Marvel's The Avengers, 2012 by Disney, Star Wars: The Force Awakens, 2015 by Disney, Titanic, 1997 by Paramount

这个程序对整数进行排序很好，但字符串排序不起作用。

Answer 1

你的大部分程序都是正确的；只有一些小错误。

这是经过细微修复和注释的代码版本:

public class MovieV3Tester
{
    public static void main(String[] args)
    {
        MovieV3[] movies = {
            new MovieV3 ("Avatar", 2009, "Fox"), 
            new MovieV3 ("Titanic", 1997, "Paramount"), 
            new MovieV3 ("Star Wars: The Force Awakens", 2015, "Disney"),
            new MovieV3 ("Avengers: Infinity War", 2018, "Disney"),
            new MovieV3 ("Jurassic World", 2015, "Universal"),
            new MovieV3 ("Marvel's The Avengers", 2012, "Disney"),
            new MovieV3 ("Furious 7", 2015, "Universal"),
            new MovieV3 ("Avengers: Age of Ultron", 2015, "Disney"),
            new MovieV3 ("Black Panther", 2018, "Disney"),
            new MovieV3 ("Harry Potter and the Deathly Hallows Part 2", 2012, "Warner Brothers")
        };

        System.out.println("Original\n");
        print(movies);
        System.out.println("\nBy Title Ascending\n");
        mergeTitle(movies, 0, (movies.length-1)); 
        // Removed extra unnecessary call to `mergeTitle()`
        print(movies);
        System.out.println("\nBy Year Ascending\n");
        mergeYear(movies, 0, (movies.length-1));
        print(movies);
    }

    public static void print(MovieV3[] movies)
    {
        for (MovieV3 movie : movies)
        {
            System.out.println(movie.getTitle() + ", " + movie.getYear() + " by " + movie.getStudio());
        }
    }

    public static void merge(MovieV3[] a, int low, int mid, int high, int compare)
    {
        MovieV3[] temp = new MovieV3[high - low + 1];

        int i = low, j = mid + 1, n = 0;
        // Changed from `compare == 1` to this so that the last `else` block could be 
        // removed, as it was identical to this first block
        if (compare != 2)
        {
            while (i <= mid || j <= high)
            {
                if (i > mid)
                {
                    temp[n] = a[j];
                    j++;
                }
                else if (j > high)
                {
                    temp[n] = a[i];
                    i++;
                }
                else if (a[i].getYear() < a[j].getYear())
                {
                    temp[n] = a[i];
                    i++;
                }
                else
                {
                    temp[n] = a[j];
                    j++;
                }
                n++;
            }
        }
        else if (compare == 2)
        {
            while (i <= mid || j <= high)
            {
                if (i > mid)
                {
                    temp[n] = a[j];
                    j++;
                }
                else if (j > high)
                {
                    temp[n] = a[i];
                    i++;
                }
                // Changed the operator from `<` to `>` so that the titles are printed 
                // the way you showed in your post
                else if ((a[j].getTitle()).compareTo(a[i].getTitle()) > 0)
                {
                    temp[n] = a[i];
                    i++;
                }
                else
                {
                    temp[n] = a[j];
                    j++;
                }
                n++;
            }
        }

        for (int k = low ; k <= high ; k++)
            a[k] = temp[k - low];

    } // end of merge

    public static void mergeYear(MovieV3[] a, int low, int high)
    {
        if (low == high)
            return;

        int mid = (low + high) / 2;

        mergeYear(a, low, mid);       // recursive call
        mergeYear(a, mid + 1, high);   // recursive call

        merge(a, low, mid, high, 1);
    }

    public static void mergeTitle(MovieV3[] a, int low, int high)
    {
        if (low == high)
            return;

        int mid = (low + high) / 2;

        // I'm not sure if it was just a typo but in your code you had called `mergeYear()` 
        // twice instead of `mergeTitle()`, which was causing the sorting to not work
        mergeTitle(a, low, mid);       // recursive call
        mergeTitle(a, mid + 1, high);   // recursive call

        merge(a, low, mid, high, 2);
    }
}

尽管编辑很小，而且您基本上已经有了正确的代码，但希望这会有所帮助。