大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
插入排序
对链表进行插入排序，是最简单的一种链表排序算法，用于插入排序是迭代的，所以每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。
插入排序的时间复杂度为O(N^2)，空间复杂度为O（1）
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode move=head;
ListNode emptyHead=new ListNode();
emptyHead.next=head;
while(move!=null&&move.next!=null){
if(!reInsert(move,emptyHead))
move=move.next;
}
return emptyHead.next;
}
private Boolean reInsert(ListNode node,ListNode emptyHead){
ListNode temp=node.next;
node.next=temp.next;
while(emptyHead!= node){
if(temp.val<=emptyHead.next.val){
temp.next=emptyHead.next;
emptyHead.next=temp;
return true;
}
emptyHead=emptyHead.next;
}
temp.next=node.next;
node.next=temp;
return false;
}
}
归并排序
对于归并排序排序在数组排序中的运用，详细请点击此处。这里主要介绍归并排序在链表排序中的运用。
在使用归并排序算法进行链表排序时，其基本思想是将链表细分成一个个子链表，将子链表进行排序，然后再将相邻的两个有序子链表进行合并，得到更长的有序链表，最后一步步得到整个有序链表，子链表进行合并排序时需要用到合并两个有序链表算法。
归并链表排序的实现方式一共有两种，递归实现和非递归实现，两种实现方式的时间复杂度都是O(nlogn），但是由于递归实现调用函数时需要消耗大量栈空间，所以递归调用的空间复杂度是O（logn）。对于非递归调用，空间复杂度就是O（1）。
递归代码：
class Solution {
public ListNode sortList(ListNode head) {
if(head==null)
return head;
return mergeSort(head);
}
public ListNode mergeSort(ListNode head){
if(head.next==null)
return head;
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
if(fast!=null)
slow=slow.next;
}
ListNode tempHead=slow.next;
slow.next=null;
ListNode left=mergeSort(head);
ListNode right=mergeSort(tempHead);
head=mergeList(left,right);
return head;
}
public ListNode mergeList(ListNode head,ListNode tempHead){
ListNode emptyHead=new ListNode(0,head);
ListNode move=emptyHead;
while(head!=null&&tempHead!=null){
if(head.val<= tempHead.val){
move.next=head;
head=head.next;
}else{
move.next=tempHead;
tempHead=tempHead.next;
}
move=move.next;
}
move.next=head==null?tempHead:head;
return emptyHead.next;
}
}
非递归代码：
class Solution {
public ListNode sortList(ListNode head) {
if(head==null)
return null;
ListNode end=head;
int length=0;
while(end!=null){
length++;
end=end.next;
}
ListNode emptyHead = new ListNode(0, head);
for(int i=1;i<length;i<<=1){
ListNode prev = emptyHead;
ListNode cur = emptyHead.next;
while(cur!=null) {
ListNode start1 =cur;
for (int j = 1; j < i&&cur.next!=null; j++) {
cur = cur.next;
}
ListNode start2 = cur.next;
cur.next = null;
cur = start2;
for (int j = 1; j < i && cur != null&&cur.next!=null; j++) {
cur = cur.next;
}
if(cur!=null){
ListNode temp=cur;
cur=cur.next;
temp.next=null;
}
prev.next = mergeList(start1, start2);
while(prev.next!=null){
prev=prev.next;
}
}
}
return emptyHead.next;
}
public ListNode mergeList(ListNode head,ListNode tempHead){
ListNode emptyHead=new ListNode(0,head);
ListNode move=emptyHead;
while(head!=null&&tempHead!=null){
if(head.val<= tempHead.val){
move.next=head;
head=head.next;
}else{
move.next=tempHead;
tempHead=tempHead.next;
}
move=move.next;
}
move.next=head==null?tempHead:head;
return emptyHead.next;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/183986.html原文链接：https://javaforall.net
