的StackOverflowError同时实施快速排序 [英] StackOverflowError while implementing QuickSort

问题描述

我想实现的一个ArrayList的快速排序算法。不过，我得到一个

 在线程异常主要java.lang.StackOverflowError
    在sorting.QuickSort.quickSort（QuickSort.java:25）
    在sorting.QuickSort.quickSort（QuickSort.java:36）
    在sorting.QuickSort.quickSort（QuickSort.java:36）
    在sorting.QuickSort.quickSort（QuickSort.java:36）
    在sorting.QuickSort.quickSort（QuickSort.java:36）
    ...
 

我不知道为什么会出现溢出。下面是我的实现：

 公共静态无效的快速排序（ArrayList中＆LT;整数GT;人，INT fromIdx，诠释toIdx）{
    INT支点，pivotIdx;

    如果（fromIdx＆LT; toIdx）{
        支点= al.get（fromIdx）;
        pivotIdx = fromIdx;

        的for（int i = 0;！I =（fromIdx + 1）;我++）{
            如果（al.get（ⅰ）所述; =枢轴）{
                pivotIdx + = 1;
                掉期（人，pivotIdx，我）;
            }
        }

        掉期（人，fromIdx，pivotIdx）;
        快速排序（人，fromIdx，pivotIdx  -  1）;
        快速排序（人，pivotIdx + 1，toIdx）;
    }
}

公共静态无效掉期（ArrayList中＆LT;整数GT;人，INT xIdx，诠释yIdx）{
    整数临时= al.get（xI​​dx）;
    al.set（xI​​dx，al.get（yIdx））;
    al.set（yIdx，温度）;
}
 

解决方案

如果你想从 fromIdx 数组的块进行排序，以 toIdx ，你不应该看的元素0，除非它是该块。但是，您的实现一样。

在中间你的索引招也是一种of..odd。我强烈建议你做运动切割出小纸片为阵，并写在纸上的跟踪信息，以便您可以通过算法追查。如果在身体上做到这一点，你看到它没有什么意义，那么就没有任何意义的电脑无论是。而保持身体纸片的行为可能看起来很可笑，但是是有很大帮助的可视化正是你在做什么。 （越precisely你可以想像你的code其实呢，你就越有可能是要能够找出是否是做错了。）

I am trying to implement an QuickSort algorithm on an ArrayList. However, I am getting a

Exception in thread "main" java.lang.StackOverflowError
    at sorting.QuickSort.quickSort(QuickSort.java:25)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    at sorting.QuickSort.quickSort(QuickSort.java:36)
    ...

I am not sure as to why is there an overflow. Below is my implementation:

public static void quickSort(ArrayList<Integer> al, int fromIdx, int toIdx) {
    int pivot, pivotIdx;

    if (fromIdx < toIdx) {
        pivot = al.get(fromIdx);
        pivotIdx = fromIdx;

        for (int i = 0; i != (fromIdx + 1); i++) {
            if (al.get(i) <= pivot) {
                pivotIdx += 1;
                swap(al, pivotIdx, i);
            }
        }

        swap(al, fromIdx, pivotIdx);
        quickSort(al, fromIdx, pivotIdx - 1);
        quickSort(al, pivotIdx + 1, toIdx);
    }
}

public static void swap(ArrayList<Integer> al, int xIdx, int yIdx) {
    Integer temp = al.get(xIdx);
    al.set(xIdx, al.get(yIdx));
    al.set(yIdx, temp);
}

解决方案

If you're trying to sort the chunk of the array from fromIdx to toIdx, you should never look at element 0 unless it is in that chunk. But your implementation does.

Your indexing trick in the middle is also kind of..odd. I highly recommend that you do the exercise of cutting out little pieces of paper for the array, and writing tracking information on a sheet of paper so that you can trace through the algorithm. If when you physically do it, you see it not make sense, then it doesn't make sense in the computer either. And the act of holding physical pieces of paper may seem silly, but is of great help in visualizing exactly what you are doing. (The more precisely you can visualize what your code actually does, the more likely you are to be able to figure out if it is doing something wrong.)

这篇关于的StackOverflowError同时实施快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！