java - 测试排序数组方法

Question

我正在编写一个程序来测试排序函数是否正确地对程序进行了排序。我必须让它测试快速排序和合并排序方法。它还必须询问用户他们想要测试哪种方法并制作一个随机对象数组。为什么我的程序不能正常运行？它只是为快速排序吐出相同的数组，并为合并排序随机重新排列它们。问题是我的排序方法还是我的测试方法？有人请帮忙。

import java.util.Random;
import java.util.Scanner;

public class sortArrays {
    public static void main (String[] args)
    {
        Random gen = new Random();
        int[] a = new int[20];
        Scanner reader = new Scanner(System.in);
        String choice;
        int left = a[0];
        int right = a[19];
        int[] buffer = new int [a.length];

        for (int i = 0; i < a.length; i++)
            a[i] = gen.nextInt(100);

        printArray(a);

        System.out.println("Type quick to test the quick sort method.");
        System.out.println("Type merge to test the merge sort method.");
        choice = reader.nextLine();

        if (choice.equals("quick"))
            quickSort(a, left, right);
        else if (choice.equals("merge"))
            mergeSort(a, buffer, 0, 9, 19);

        printArray(a);

    }


    private static void printArray(int[] a)
    {
        for(int i : a)
            System.out.print(i + " ");
        System.out.println("");
    }


    private static void quickSort (int[] a, int left, int right)
    {
        if (left >= right) return;

        int i = left;
        int j = right;
        int pivotValue = a[(left + right) / 2];

        while (i < j)
        {
            while (a[i] < pivotValue) i++;
            while (pivotValue < a[j]) j--;
            if (i <= j)
            {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            }
        }
        quickSort(a, left, j);
        quickSort(a, i, right);
    }


    private static void mergeSort(int[] a, int[] copyBuffer, int low, int middle, int high)
    {
        int i1 = low, i2 = middle + 1;

        for(int i = low; i <= high; i++)
        {
            if(i1 > middle)
                copyBuffer [i] = a[i2++];
            else if(i2 > high)
                copyBuffer[i] = a[i1++];
            else if(a[i1] < a[i2])
                copyBuffer[i] = a[i1++];
            else
                copyBuffer[i] = a[i2++];
        }

        for(int i = low; i <= high; i++)
            a[i] = copyBuffer[i];
    }


}

Answer 1

好吧，您的 printArray() 看起来不错，但有一件事马上就突出了:

您传递给 quickSort() 的初始参数不正确。你有:

int[] a = new int[20];
...
int left = a[0];
int right = a[19];
...
quickSort(a, left, right);

您正在将 left 和 right 初始化为 0，因此您最终调用了 quickSort(a, 0, 0) (不是你想要的)。您可能打算改为这样做，因为 left 和 right 持有 index:

int left = 0;
int right = 19;

或者简单地说:

quickSort(a, 0, 19);

至于您的mergeSort()，实现是不完整的。看来您已经实现了“合并”操作(算法的基本 部分)，但没有实现“合并排序”整体算法。您可能想查看 Mergesort in Java (例如)或 Merge Sort (一般概述)。

顺便说一下，您可能希望指定 a.length - 1 而不是 19，这样您就可以更改 a 无需修改其他代码(同样适用于传递给 mergeSort() 的 9，但这没有实际意义，因为一旦您实现算法完全)。