设为首页 加入收藏

TOP

单链表排序
2014-11-24 02:23:01 】 浏览:369
Tags:单链表 排序

无外乎是冒泡、选择、插入等排序方法。关键是交换算法,需要额外考虑。第7题我编写了一个交换算法,在本题的排序过程中,我们可以在外层和内层循环里面,捕捉到pre1和pre2,然后进行交换,而无需每次交换又要遍历一次单链表。
在实践中,我发现冒泡排序和选择排序都要求内层循环从链表的末尾向前走,这明显是不合时宜的。
所以我最终选择了插入排序算法,如下所示:
先给出基于数组的算法:


代码
static int[]
InsertSort(int[] arr)
{
for(int i=1; i {
for(int j =i; (j>0)&&arr[j] {
arr[j]=arr[j]^arr[j-1];
arr[j-1]=arr[j]^arr[j-1];
arr[j]=arr[j]^arr[j-1];
}
}


return arr;
}
仿照上面的思想,我们来编写基于Link的算法:
public static Link SortLink(Link head)
{
Link pre1 = head;
Link pre2 = head.Next;
Link min = null;
for (Link curr1 = head.Next; curr1 != null; curr1 = min.Next)
{
if (curr1.Next == null)
break;
min = curr1;
for (Link curr2 = curr1.Next; curr2 != null; curr2 = curr2.Next)
{
//swap curr1 and curr2
if (curr2.Data < curr1.Data)
{
min = curr2;
curr2 = curr1;
curr1 = min;
pre1.Next = curr1;
curr2.Next = curr1.Next;
curr1.Next = pre2;
//if exchange element n-1 and n, no need to add reference from pre2 to curr2, because they are the same one
if (pre2 != curr2)
pre2.Next = curr2;
}
pre2 = curr2;
}
pre1 = min;
pre2 = min.Next;
}
return head;
}


值得注意的是,很多人的算法不能交换相邻两个元素,这是因为pre2和curr2是相等的,如果此时还执行pre2.Next = curr2; 会造成一个自己引用自己的环。


交换指针很是麻烦,而且效率也不高,需要经常排序的东西最好不要用链表来实现,还是数组好一些。



单链表排序 https://www.cppentry.com/bencandy.php?fid=43&id=35959

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Oracle database administrator面.. 下一篇Java程序员常见笔试题之基础简答题