问题描述
我正在尝试实现一个简单的Quicksort算法（双向链接列表，循环）。算法效果非常好，但是由于以下操作太慢：
iEl = getListElement（l）;
jEl = getListElement（r）;
在很长的输入列表中，我必须不断地浏览整个列表，找到 iEl 和 jEl ，这是超慢的。
解决方案是（我想），要通过这两个元素作为参数到分区函数。问题是，我找不到正确的元素。我试图输出很多可能性，但是它们只是不正确。
这里是代码：
$ b $ public void partition（int l，int r，ListElement lEl，ListElement rEl）{
if（r> l）{
ListElement p，iEl ，jE1;
int i，j，x;
i = l;
j = r;
//这两行非常慢，长输入列表
//如果我有两个正确的参数lEL和rEl，这将会更快
iEl = getListElement （升）;
jEl = getListElement（r）;
// getListElement遍历列表的x元素（l和r），然后返回该位置的元素
//如果我有正确的元素rEl和lEl，我可以直接使用这些元素，而不是一直在列表中。这样的东西：
// iEl = lEl;
// jEl = rEl;
x =（int）Math.floor（（j + i）/ 2）;
p = getListElement（x）;
while（i< = j）{
while（iEl.getKey（）< p.getKey（）&& 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）{
//这里我需要两个正确的参数
分区（l，j，？ ??）
}
if（i< r）{
//这里我需要两个正确的参数
分区（l，j，???，?? ？）;
}
}
}
该功能以：partition （0，numOfElements - 1，list.first，list.first.prev）;
我已经尝试了这两个参数的几个变体（iEl，iEl。 prev，jEl，jEl.next，...），但没有一个看起来正确配合。
正如我所说，该功能有效，但速度非常慢。这是否可能，加快功能，通过传递这两个参数？如果是这样，我必须使用什么参数？
我没有看到元素作为参数将如何帮助很多问题是不得不走列表来获取元素，不是吗？
为什么不在列表中排列数组？列出一次，引用数组中的每个元素，然后做我想象的一个更正常的快速排序分区数组并将元素移动到那里。当然，当你在数组中移动一个元素的时候，你也必须重新排列它的下一个/前一个指针，这样你的链表完成后就完好无损，但是你必须这么做。这将节省您走列表获取元素。完成后抛弃数组（或ArrayList）。
I'm trying to implement a simple Quicksort Algorithm (Doubly Linked List, circular). The Algorithm works pretty well, but it's much too slow, because of the following operation: iEl = getListElement(l); jEl = getListElement(r);On very long input-list I have to constantly go through the whole list, to find iEl and jEl, which is ultra-slow.
The solution would be (I think), to pass those two Elements as Parameters to the partition Function. Problem is, I can't find the correct Elements for this. I've tried to output a lot of possibilities, but they just don't fit correctly.
Here's the code:
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, ???, ???);
}
}
}
The function starts with: partition(0, numOfElements - 1, list.first, list.first.prev);
I've tried a couple of variants for these two parameters (iEl, iEl.prev, jEl, jEl.next, ...), but none seem to fit correctly.
As I said, the function works, but its very slow. Is this even possible, to speed up the function, by passing these two parameters? If so, what parameters would I have to use?
I don't see how "elements as parameters" is going to help much. The problem is having to walk the list to get elements, isn't it?
Why not make an array out of your list for the duration of the sort? Walk the list once, put a reference to each element in an array, and then do what I think of as a more normal quicksort partitioning the array and moving your elements there. Of course, when you move an element in the array, you will also have to rearrange its next/previous pointers so that your linked list is intact when you're done, but you have to do that anyway. This will save you walking the list to get elements. Just discard the array (or ArrayList) when done.
这篇关于快速排序递归参数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！