0

我写了一个程序，我必须写出快速排序的代码。我正在使用 Comparable [] 数组。为了交换数组的两个元素，我必须将一个元素存储在一个变量中。通常，使用字符串数组，我可以将元素存储在字符串变量中，但不允许将值存储在具有可比较数组的字符串变量中。如何将这个 Comparable 数组中的一个元素存储在这个数组之外，以便交换这两个元素？这就是我的程序的样子，我卡在的部分没有代码。

import java.io.*;

public class QuickSort{
public static void main (String args[]) {       
    Comparable[] q = Read();
    int l = 0; 
    int x = q.length-1;
    QSortr(q, l, x);
    PrintFxn(q);
}

public static Comparable[] Read() {
String hold[] = new String[1000];
int numin=0;
try{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s; 
        s=br.readLine();
        while (s!=null&& !s.equals("")) {
            hold[numin]= s;
            numin++;
            s=br.readLine();
        }
        br.close();

    } catch (Exception e) {System.out.println("Ack!:" + e); }
    Comparable q[] = new String[numin];
    for(int a=0; a<numin; a++) {
        q[a] = hold[a];
    }
    return q; }

public static int QSort( Comparable q[], int l, int x) {
    int r = l +1;
    int m= l;
    int k = l;

while(r<q.length-1){
    if( q[r].compareTo(q[k])<=0){
        m++; r++;  }
    else{ 
        while(q[r].compareTo(q[k])>0&&r<q.length-1){
            r++; }
        m++; 
         //This is where i'm stuck...
        q[r] = q[m];
        q[m] = a[0]; }
    }
    return m;}
public static Comparable [] QSortr(Comparable q [], int l, int x) {
    while(l<x) {
        int a = QSort(q, l, x);
        QSortr(q, l, a-1);
        QSortr(q, a+1, x); }
    return q; }

public static void PrintFxn(Comparable[] q) {
    for(int a=0; a<q.length; a++) {
    System.out.println(q[a]); }
}
}
4

1 回答 1

0

在这种“就地”快速排序的实现中有很多错误的地方，其中之一是条件：while(r<q.length-1)- 你应该停止循环 when r > x。另一个问题是您x在 QSort 中根本不使用（右边界）。查看以下quickSort的实现——即使它是在 Ruby 中的——它很容易理解：主要思想是使用两个指针运行——一个从右到左，另一个从左到右，当它们相互交叉时停止，但同时运行检查以查看是否有元素小于枢轴右侧的枢轴和大于枢轴左侧的枢轴 - 并在它们之间切换。

于 2013-10-12T23:32:15.423 回答