0

我正在尝试实现一个简单的快速排序算法（双向链表，循环）。该算法工作得很好，但它太慢了，因为以下操作： iEl = getListElement(l); jEl = getListElement(r); 在很长的输入列表上，我必须不断地遍历整个列表，才能找到iEland 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，...），但似乎没有一个适合。

正如我所说，该功能有效，但速度很慢。这甚至可以通过传递这两个参数来加速函数吗？如果是这样，我必须使用哪些参数？

4

1 回答 1

1

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

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

于 2013-05-11T11:25:45.303 回答