用linkedlist实现稳定的就地快速排序
我正在尝试实现快速排序,对于通常的非稳定版本,我有以下代码:
private static Integer partition(ArrayList<Integer> a , Integer p , Integer r )
{
Integer x = a.get(p) ;
Integer i = p ;
Integer j = r ;
while ( j > i )
{
while ( a.get(i) <= x && i < j )
i++ ;
while ( a.get(j) > x && i < j )
j-- ;
if ( i < j )
Collections.swap(a,i,j) ;
}
return j ;
}
private static void quickSort ( ArrayList<Integer> a , Integer p , Integer r )
{
if ( p < r )
{
Integer q = partition(a,p,r) ;
quickSort(a,p,q-1) ;
quickSort(a,q+1,r) ;
}
}
但我需要一个稳定的版本
我的导师告诉我,使用链表并使用每个列表的第一个元素作为轴心,这是可能的(一种就地且稳定的快速排序)。所以我在寻找一种算法,它能把我引向这个?!谢谢
共 (0) 个答案