时间戳

首页 > 解决方案 > 为什么我的 quickSort 方法给了我一个 StackOverflowError？爪哇

java - 为什么我的 quickSort 方法给了我一个 StackOverflowError？爪哇

问题描述

这是我的快速排序方法。它由两种不同的方法组成：一种将队列作为参数 (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());
   }       
}

链接队列类：

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)

我无法弄清楚为什么会这样。

标签： javasortingrecursion

解决方案

我认为您的问题出在比较器中。

考虑这个表达式：

"dog".compareTo("and")

它将返回 3。但是您的比较器仅测试 0 和 1。当我认为您真的希望它处理这种情况时，它将进入 elsereturnValue == 1情况。

由于您的比较器大部分时间都返回 1，因此您从队列中拉出的大多数项目最终都会进入G，并且嵌套调用的数量quickSort将与输入数组的长度大致相同。（请注意，在您的堆栈跟踪中，大多数调用quickSort都来自同一行，这可能是排序的那一行G。）因此，如果您的数组中的项目数很大，则可能会产生您看到的 StackOverflowError。

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

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

或者

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

推荐阅读