我正在努力研究单链表上的递归快速排序。基本情况是什么,当我到达它时我需要做什么才能让函数“倒带”并打印排序列表?这是一些代码,但我认为这是非常错误的...
public static void qSort(SLLNode first, SLLNode last)
{
SLLNode pivot = first ;
SLLNode head = pivot.succ ;
if (first!=last)
{
while (head!=null)
{
if (head.data.compareToIgnoreCase(pivot.data)<0)
{
pivot.succ = head.succ ;
head.succ = first ;
first = head ;
qSort(first, pivot) ;
qSort(head, last) ;
}
qSort(first, pivot) ;
qSort(head, last) ;
}
}
}
换句话说我的问题:当我到达基本情况 first==last
时,我需要做什么? 我怎样才能使递归倒带并产生排序列表?
这是我更新后的代码:
public static void qSort(SLLNode first, SLLNode last)
{
if (first==last)
{
return ;
}
SLLNode pivot = first ;
SLLNode head = pivot.succ ;
while (head!=null)
{
if (head.data.compareToIgnoreCase(pivot.data)<0)
{
pivot.succ = head.succ ;
head.succ = first ;
first = head ;
qSort(first, pivot) ;
qSort(head, last) ;
}
qSort(first, pivot) ;
qSort(head, last) ;
}
}
最佳答案
总则
对于快速排序的一般性回顾,您可能应该回顾 quick-sort algorithm on Wikipedia .简而言之,如果您使用 partition
会更容易帮助函数让你的列表进入一个状态,所有小于你的枢轴点的东西都在它的左边,所有大于枢轴点的东西都在它的右边。然后,您可以在枢轴的两边递归调用快速排序。
EJP也有很好的一点。我还没有在链表上看到快速排序。
不管怎样,让我们做吧
在我看来,使用链表进行快速排序的算法类似于
def qsort(head, tail)
if head == tail
return
pivot = tail
current = head
while current != pivot
if current.value < pivot.value
move/prepend current to head of the list
else
move/append current to tail of the list
current = current.next
qsort(head, pivot-1)
qsort(pivot, tail)
这有点棘手,因为您必须跟踪 pivot - 1
,这对于单向链表来说不是很自然。此外,上述算法并没有真正考虑到相等的元素。但一般的想法是你最终得到的所有东西都小于 pivot
在它之前,所有比它更伟大的东西都在它之后,然后你调用qsort
再次为双方。
你的代码
让我们用一个简单的例子来运行你的程序。
A->B->C->D
F L
是我们的开始。
SLLNode pivot = first ;
SLLNode head = pivot.succ ;
给我们
A->B->C->D
F H L
P
假设if (head.data.compareToIgnoreCase(pivot.data)<0)
给定列表的当前状态,对于每个元素都为真。
所以我们输入if
声明,并做
pivot.succ = head.succ ;
A->C->D B->C
F L H
P
head.succ = first ;
B->A->C->D
H F L
P
first = head ;
B->A->C->D
H P L
F
这给了我们
A->B->C->D
F H L
P
B->A->C->D
H P L
F
如果我有那个权利,那么调用
qSort(head, last);
应该是
qSort(pivot, last);
所以你没有调用 qSort
再次遍历整个列表。在递归调用 qSort
之前,您似乎还想继续遍历列表,直到小于枢轴的所有内容都在它的左侧。 .
关于java - 单链表递归快速排序的基本情况,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5494503/