插入排序

對鏈表進(jìn)行插入排序，是最簡單的一種鏈表排序算法，用于插入排序是迭代的，所以每次只移動(dòng)一個(gè)元素，直到所有元素可以形成一個(gè)有序的輸出列表。
每次迭代中，插入排序只從輸入數(shù)據(jù)中移除一個(gè)待排序的元素，找到它在序列中適當(dāng)?shù)奈恢茫⑵洳迦搿Ｖ貜?fù)直到所有輸入數(shù)據(jù)插入完為止。
插入排序的時(shí)間復(fù)雜度為O(N^2)，空間復(fù)雜度為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;
    }
}

歸并排序

對于歸并排序排序在數(shù)組排序中的運(yùn)用，詳細(xì)請點(diǎn)擊此處。這里主要介紹歸并排序在鏈表排序中的運(yùn)用。
在使用歸并排序算法進(jìn)行鏈表排序時(shí)，其基本思想是將鏈表細(xì)分成一個(gè)個(gè)子鏈表，將子鏈表進(jìn)行排序，然后再將相鄰的兩個(gè)有序子鏈表進(jìn)行合并，得到更長的有序鏈表，最后一步步得到整個(gè)有序鏈表，子鏈表進(jìn)行合并排序時(shí)需要用到合并兩個(gè)有序鏈表算法。
歸并鏈表排序的實(shí)現(xiàn)方式一共有兩種，遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)，兩種實(shí)現(xiàn)方式的時(shí)間復(fù)雜度都是O(nlogn），但是由于遞歸實(shí)現(xiàn)調(diào)用函數(shù)時(shí)需要消耗大量棧空間，所以遞歸調(diào)用的空間復(fù)雜度是O（logn）。對于非遞歸調(diào)用，空間復(fù)雜度就是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;
}
}

總結(jié)

以上是生活随笔為你收集整理的java链表排序方法_java链表排序(Java中@)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。