java - 快速排序的递归参数

Question

我正在尝试实现一个简单的快速排序算法(双向链表，循环)。该算法运行得很好，但速度太慢，因为以下操作: iEl = getListElement(l); jEl = getListElement(r); 在很长的输入列表中，我必须不断地遍历整个列表，才能找到 iEl 和 jEl，这是超慢的。

解决方案是(我认为)将这两个元素作为参数传递给分区函数。问题是，我找不到正确的元素。我尝试输出很多可能性，但它们就是不正确。

代码如下:

public void partition(int l, int r, ListElement lEl, ListElement rEl) {
    if (r > l) {
        ListElement p, iEl, jEl;
        int i, j, x;
        i = l;
        j = r;

        // These two lines are very slow with long input-lists
        // If I had the two correct parameters lEL and rEl, this would be much faster
        iEl = getListElement(l);
        jEl = getListElement(r);
        // getListElement walks through x-elements (l and r) of the list and then returns the element on that position 

        // If I had the correct Elements rEl and lEl, I could directly use these Elements, instead of going all the way through the list. Something like this:
        // iEl = lEl;
        // jEl = rEl;


        x = (int) Math.floor((j + i) / 2);
        p = getListElement(x);


        while (i <= j) {

            while (iEl.getKey() < p.getKey() && i < r) {
                i++;
                iEl = iEl.next;
            }

            while (jEl.getKey() > p.getKey() && j > l) {
                j--;
                jEl = jEl.prev;
            }

            if (i <= j) {
                if (iEl != jEl) {
                    swap(iEl, jEl);
                }
                ++i;
                --j;
                break;
            }
        }

        if (l < j) {
            // Here I need the two correct parameters
            partition(l, j, ???, ???);
        }

        if (i < r) {
            // Here I need the two correct parameters
            partition(l, j, ???, ???);
        }
    }
}

函数开头为:partition(0, numOfElements - 1, list.first, list.first.prev);

我已经尝试了这两个参数的几种变体(iEl、iEl.prev、jEl、jEl.next...)，但似乎没有一个能够正确匹配。

正如我所说，该功能可以工作，但速度非常慢。通过传递这两个参数来加速函数是否可能？如果是这样，我必须使用哪些参数？

Answer 1

我不认为“元素作为参数”会有多大帮助。问题是必须遍历列表才能获取元素，不是吗？

为什么不在排序期间从列表中创建一个数组？遍历列表一次，放置对数组中每个元素的引用，然后执行我认为更正常的快速排序，对数组进行分区并将元素移动到那里。当然，当您移动数组中的元素时，您还必须重新排列其下一个/上一个指针，以便完成后链接列表完好无损，但无论如何您都必须这样做。这将节省您遍历列表来获取元素的时间。完成后只需丢弃数组(或 ArrayList)即可。