用于快速排序的java递归参数
我正在尝试实现一个简单的快速排序算法(双链表,循环)。该算法运行得很好,但速度太慢,原因是以下操作:
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,…),但似乎都不合适
正如我所说,这个函数可以工作,但速度非常慢。这是否可能通过传递这两个参数来加速函数?如果是,我必须使用哪些参数
# 1 楼答案
我看不出“元素作为参数”有多大帮助。问题是必须遍历列表才能获取元素,不是吗
为什么不在排序期间从列表中创建一个数组呢?遍历列表一次,对数组中的每个元素进行引用,然后执行我认为更普通的快速排序,对数组进行分区并将元素移动到那里。当然,当你在数组中移动一个元素时,你还需要重新排列它的下一个/上一个指针,这样你的链表在你移动完之后就完好无损了,但是你还是必须这样做。这将节省您遍历列表以获取元素的时间。完成后只需丢弃数组(或ArrayList)