java - 为什么我的 QuickSort 方法给出 StackOverflowError？ java

Question

这是我的快速排序方法。它由两个单独的方法组成:一个将队列作为参数 (1)，另一个将数组作为参数 (2)。然后它使用参数数组将队列传递给(1)。

(2)

public static <E> void quickSort(
   E[] array,
   Comparator<E> comp,
   long start,
   long timeOut
) throws TimeoutException {
   Queue<E> queue = new LinkedQueue<>();

   for (int i = 0; i < array.length; i++)
   {
      queue.enqueue(array[i]);
   }

   quickSort(queue, comp, start, timeOut);

   Object[] newArray =  new Object[queue.size()];

   for ( int i = 0; i < queue.size(); i++)
   {
      newArray[i] = queue.dequeue();
   }

   if (System.currentTimeMillis() - start > timeOut)
   {
      throw new TimeoutException("Quick sort has timed out.");
   }       
}

(1)

public static <E> void quickSort(
   Queue<E> queue,
   Comparator<E> comp,
   long start,
   long timeOut
) throws TimeoutException {
   if (System.currentTimeMillis() - start > timeOut)
   {
      throw new TimeoutException("Quick sort has timed out.");
   }

   int n = queue.size();
   if (n < 2)
   {
      return;
   }

   // divide
   E pivot = queue.first();

   Queue<E> L = new LinkedQueue<>();
   Queue<E> E = new LinkedQueue<>();
   Queue<E> G = new LinkedQueue<>();

   while (!queue.isEmpty())
   {
      E element = queue.dequeue();
      int c = comp.compare(element, pivot);

      if (c < 0)
      {
         L.enqueue(element);
      }
      else if (c == 0)
      {
         E.enqueue(element);
      }
      else
      {
         G.enqueue(element);
      }
   }

   // conquer
   quickSort(L,comp,start,timeOut);
   quickSort(G,comp,start,timeOut);

   // concatenate results

   while (!L.isEmpty())
   {
      queue.enqueue(L.dequeue());
   }

   while(!E.isEmpty())
   {
      queue.enqueue(E.dequeue());
   }

   while(!G.isEmpty())
   {
      queue.enqueue(G.dequeue());
   }       
}

LinkedQueue 类:

import java.io.File;

public class LinkedQueue<E> implements Queue<E> {
    private SinglyLinkedList<E> list = new SinglyLinkedList<>();
    public LinkedQueue(){}
    public int size(){return list.size();}
    public boolean isEmpty(){return list.isEmpty();}
    public void enqueue(E element){list.addLast(element);}
    public E first(){return list.first();}
    public E dequeue(){return list.removeFirst();}
}

名称比较器:

public class NameComparator implements Comparator<Employee> {    
    public int compare(Employee a, Employee b)
    {
        String nameA = a.getName();
        String nameB = b.getName();
        int returnValue = 0;
        returnValue = nameA.compareTo(nameB);
        if (returnValue == 0)
        {
            return returnValue;
        }
        else if(returnValue == 1)
        {
            returnValue = -1;
            return returnValue;
        }
        else
        {
            returnValue = 1;
            return returnValue;
        }

    }
}

输出:

run:
Time to create unsorted array : 0 ms
Time to copy unsorted array : 0 ms
fvuvdm,xezvdfqvom,oqqoj,azhjksqjt,tburnf,mkyroq,yokgqrfsiz,mrexmktnz,dqbey,uvbipqag,
Exception in thread "main" java.lang.StackOverflowError
    at LinkedQueue.dequeue(LinkedQueue.java:29)
    at Sort.quickSort(Sort.java:256)
    at Sort.quickSort(Sort.java:276)
    at Sort.quickSort(Sort.java:276)
    at Sort.quickSort(Sort.java:276)
    at Sort.quickSort(Sort.java:276)
    at Sort.quickSort(Sort.java:276)
    at Sort.quickSort(Sort.java:276)
//this continues for many lines

C:\Users\jackm\AppData\Local\NetBeans\Cache\11.0\executor-snippets\run.xml:111: The following error occurred while executing this line:
C:\Users\jackm\AppData\Local\NetBeans\Cache\11.0\executor-snippets\run.xml:94: Java returned: 1
BUILD FAILED (total time: 0 seconds)

我不明白为什么会发生这种情况。

Answer 1

我认为你的问题出在你的比较器上。

考虑这个表达式:

"dog".compareTo("and")

它将返回 3。但是您的比较器仅测试 0 和 1。当我认为您确实希望它采用 returnValue == 1 情况时，它将进入 else 情况。

由于您的比较器大多数时候返回 1，因此您从队列中取出的大多数项目最终都会进入 G，以及对 quickSort 的嵌套调用数量> 将与输入数组的长度大致相同。 (请注意，在堆栈跟踪中，大多数对 quickSort 的调用都来自同一行，这可能是对 G 进行排序的行。)因此，如果项目数您的数组很大，这可能会产生您所看到的 StackOverflowError。

看起来您希望比较器反转字符串的排序顺序。你应该只使用:

return -a.getName().compareTo(b.getName())

或

return b.getName().compareTo(a.getName())