1

我正在尝试在 Java 中实现快速排序算法：

// Sort parallel arrays with quick sort

import java.util.Scanner;
import java.text.DecimalFormat;

class FunRunQuiSort {
    static int iSize = 5; // Set value
    static double[] daFinishTime = new double[iSize];
    static String[] saRunnerName = new String[iSize];

static void getInput() {
    System.out.println("\n***** 5K RUNNERS *****");
    for(int i = 0; i < saRunnerName.length; i++) {
        Scanner input = new Scanner(System.in);

        System.out.print("Enter runner name: ");
        saRunnerName[i] = input.nextLine();

        System.out.print("Enter finish time: ");
        daFinishTime[i] = input.nextDouble();

        System.out.print("\r\n");
    }
}

static void doQuickSort(double[] daFinishTime) {
    int i = daFinishTime[0], j = daFinishTime.length - 1;
    double dTemp;
    String sTemp;
    // Pivot
    double dPivot = daFinishTime[(daFinishTime[0] + daFinishTime.length - 1) / 2];
    // Partition
    do {    
        while(daFinishTime[i] < dPivot) {
            i++;
        } 
        while(daFinishTime[j] > dPivot) {
            j--;
        }
        if(i <= j) {
            dTemp = daFinishTime[i];
            daFinishTime[i] = daFinishTime[j];
            daFinishTime[j] = dTemp;

            sTemp = saRunnerName[i];
            saRunnerName[i] = saRunnerName[j];
            saRunnerName[j] = sTemp;

            i++;
            j--;
        }
    } while(i <= j);
    // Recursion
    if(daFinishTime[0] < j) {
        doQuickSort(daFinishTime, daFinishTime[0], j);
    }
    if(i < daFinishTime.length - 1) {
        doQuickSort(daFinishTime, i, daFinishTime.length - 1);
    }
}

static void printOutput() {
    DecimalFormat df = new DecimalFormat("##.00");

    System.out.println("***** SORTED RUNTIMES *****");
    for(int i = 0; i < daFinishTime.length; i++) {
        System.out.println("[" + (i + 1) + "] " +
            df.format(daFinishTime[i]) + " mins. by " +
            saRunnerName[i]);
    }

    System.out.println("\n***** TOP 3 RUNTIMES *****");
    for(int i = 0; i < 3; i++) {
        System.out.println("#" + (i + 1) + " Place: " +
            df.format(daFinishTime[i]) + " mins. by " +
            saRunnerName[i]);
    }
}

public static void main(String[] args) {
    getInput();
    doQuickSort(daFinishTime);
    printOutput();
   }
}

它正在返回精度错误，但是当我更改所述行的数据类型时，它会返回更多的精度错误。

有人可以修复代码吗？我只需要看看快速排序的实际效果。

4

4 回答 4

2 
double dPivot = daFinishTime[(daFinishTime[0] + daFinishTime.length - 1) / 2];

您如何选择枢轴元素令人困惑。如果你想要中间元素作为枢轴，它应该是

double dPivot = daFinishTime[(i+j)/2];

在@Tobias 解决方案中更新此方法

 static void doQuickSort(double[] daFinishTime, int i, int j) {
        double dTemp;
        String sTemp;

        int start = i;
        int end = j;
        // Pivot
        double dPivot = daFinishTime[(i + j) / 2];

        // Partition
        while (start <= end) {
            while (daFinishTime[start] < dPivot) {
                start++;
            }
            while (daFinishTime[end] > dPivot) {
                end--;
            }
            if (start <= end) {
                dTemp = daFinishTime[start];
                daFinishTime[start] = daFinishTime[end];
                daFinishTime[end] = dTemp;

                sTemp = saRunnerName[start];
                saRunnerName[start] = saRunnerName[end];
                saRunnerName[end] = sTemp;

                start++;
                end--;
            }
        }

        // Recursion
        if (start < j) {
            doQuickSort(daFinishTime, start, j);
        }
        if (i < end) {
            doQuickSort(daFinishTime, i, end);
        }
    }
于 2013-07-19T06:26:37.460 回答
1

你有如何改变你的快速排序的答案，所以我想我会介绍一些其他的建议和稍微不同的方法。我不确定您对拥有两个独立数组的要求是什么，但在我看来，维护这两个数组是一种不好的做法——使用它们的位置作为标识符。在我看来，您需要一个 Runner 对象，其中可能包含它们的一些详细信息（如果需要）。对于我的示例，我刚刚创建了一个“RunnerTime”对象，其中包含两个字段 Name(String) 和 Time(Double)。

然后我填充了一个 Array 或 RunnerTime 对象以发送到我的 quickSort 方法中。下面是它的工作原理。

我已经在本地添加了 4 个跑步者对此进行了测试：

RunnerTime rt1 = new RunnerTime("Bob", 10.13);
RunnerTime rt3 = new RunnerTime("Craig", 11.65);
RunnerTime rt2 = new RunnerTime("Dave", 11.45);
RunnerTime rt4 = new RunnerTime("Marley", 5.62);

然后我将它们添加到一个数组中并将它们发送到以下方法：

private static RunnerTime[] doSort(RunnerTime[] runnerTimes) {
        RunnerTime currentRunnerTime;
        RunnerTime nextRunnerTime;
        boolean swapped;

        do {
            swapped = false;
            for (int x = 0; x < runnerTimes.length - 1; x++) {
                currentRunnerTime = runnerTimes[x];
                nextRunnerTime = runnerTimes[x + 1];
                if (currentRunnerTime.time > nextRunnerTime.time) {
                    runnerTimes[x] = nextRunnerTime;
                    runnerTimes[x + 1] = currentRunnerTime;
                    swopped = true;
                }
            }
        } while (swapped);
        return runnerTimes;
    }

这样做后，他们排序为：

Runner Name: Marley  Runner Time: 5.62
Runner Name: Bob     Runner Time: 10.13
Runner Name: Dave    Runner Time: 11.45
Runner Name: Craig   Runner Time: 11.65

这样做的好处如下：

  • 你的名字和时间是一致的，所以没有机会被错误地分配给另一个跑步者。
  • 您的排序方法可以更短，因为您只需要交换一个数组。
  • “交换”布尔值意味着您的数组仅循环通过它需要的次数。一旦有一个没有进行任何交换的循环（意味着每个人都井井有条） - 循环将退出。
于 2013-07-19T10:38:42.983 回答
0

如果可能，请参阅实现快速排序算法。此外，您为什么要在程序中使用整数和双精度数。由于您的代码注释正确，因此您的程序无法编译。

于 2013-07-19T06:32:47.323 回答
0

我对 doQuickSort 方法进行了一些更改。现在它的编译，它似乎工作。

// Sort parallel arrays with quick sort

import java.text.DecimalFormat;
import java.util.Scanner;

class FunRunQuiSort {
static int iSize = 5; // Set value
static double[] daFinishTime = new double[iSize];
static String[] saRunnerName = new String[iSize];

static void getInput() {
    System.out.println("\n***** 5K RUNNERS *****");
    for(int i = 0; i < saRunnerName.length; i++) {
        Scanner input = new Scanner(System.in);

        System.out.print("Enter runner name: ");
        saRunnerName[i] = input.nextLine();

        System.out.print("Enter finish time: ");
        daFinishTime[i] = input.nextDouble();

        System.out.print("\r\n");
    }
}

static void doQuickSort(double[] daFinishTime, int i, int j) {
    double dTemp;
    String sTemp;

    // Pivot
    double dPivot = daFinishTime[(i + j) / 2];

    // Partition
    while(i <= j) {
        while(daFinishTime[i] < dPivot) {
            i++;
        } 
        while(daFinishTime[j] > dPivot) {
            j--;
        }
        if(i <= j) {
            dTemp = daFinishTime[i];
            daFinishTime[i] = daFinishTime[j];
            daFinishTime[j] = dTemp;

            sTemp = saRunnerName[i];
            saRunnerName[i] = saRunnerName[j];
            saRunnerName[j] = sTemp;

            i++;
            j--;
        }
    }

    // Recursion
    if(i < i - 1) {
        doQuickSort(daFinishTime, i, i - 1);
    }
    if(i < j) {
        doQuickSort(daFinishTime, i, j);
    }
}

static void printOutput() {
    DecimalFormat df = new DecimalFormat("##.00");

    System.out.println("***** SORTED RUNTIMES *****");
    for(int i = 0; i < daFinishTime.length; i++) {
        System.out.println("[" + (i + 1) + "] " +
                df.format(daFinishTime[i]) + " mins. by " +
                saRunnerName[i]);
    }

    System.out.println("\n***** TOP 3 RUNTIMES *****");
    for(int i = 0; i < 3; i++) {
        System.out.println("#" + (i + 1) + " Place: " +
                df.format(daFinishTime[i]) + " mins. by " +
                saRunnerName[i]);
    }
}

public static void main(String[] args) {
        getInput();
        doQuickSort(daFinishTime, 0, daFinishTime.length - 1);
        printOutput();
    }
}
于 2013-07-19T06:50:30.293 回答