[算法] 單連結清單插入排序（java）

實作

• 首先保證插入前的連結清單是個完整的，最後一個節點要斷開
• 然後在插入前連結清單中找到比待插入節點大的最小元素，插到前面即可

Link.java

class Link {

    private class Node {
        int data;
        Node next;

        public Node(int x) {
            data = x;
        }
        public void addNode(Node newNode){
            if(this.next == null){
                this.next = newNode;
            }else{
                this.next.addNode(newNode);
            }
        }
    }

    public Node root;

    public void add(int data){
        Node newNode = new Node(data);
        if(this.root==null){
            this.root=newNode;
        }else{
            this.root.addNode(newNode);
        }
    }

    public void printLink(){
        Node head = this.root;
        while(head!=null) {
            System.out.println(head.data);
            head = head.next;
        }
    }

    public void insertionSortList() {
        Node head = this.root;
        if(head==null || head.next==null)
            return;
        Node dummy = new Node(-1);
        dummy.next = head;
        Node cur = head.next;
        head.next = null;
        while(cur != null) {
            Node pre = dummy;
            Node temp = cur.next;

            while (pre.next!=null && cur.data > pre.next.data){
                pre = pre.next;
            }

            cur.next = pre.next;
            pre.next = cur;
            cur = temp;
        }
        this.root=dummy.next;
        return;
    }
}
      

main.java

import java.lang.reflect.Array;

public class Main {

    public static void main(String[] args) {
       Link all = new Link();

       int data[] = new int[]{5,4,3,2,1};

//       for(int i = 0;i < data.length;i++){
//           data[i] = i;
//       }

//       data[0] = 0;
//       int j = data.length-1;
//       for(int i = 1;i < data.length;i++){
//           data[i] = j;
//           j--;
//       }

//        int j = data.length;
//        for(int i = 0;i < data.length;i++){
//            data[i] = j;
//            j--;
//        }

        for(int i = 0;i < data.length;i++){
            System.out.println(data[i]);
        }


       for(int i = 0;i < data.length;i++){
           all.add(data[i]);
       }

        long startTime=System.currentTimeMillis();
        all.insertionSortList();
        long endTime=System.currentTimeMillis();
        System.out.println(endTime-startTime);

        System.out.println("==================");
        all.printLink();

    }
}
      

資料結構分析

• 倒序連結清單：3->2->1

data	next
R1	R2
A	3	B	null
B	2	C	A
C	1
S	-1	A

• 順序連結清單：1->2->3

	1
	3		null

• 亂序連結清單：3->2->4

				C
	4
			B	B

變量分析

• 共需定義5個變量：head、dummy、cur、pre、temp，可分為兩類
• head、dummy、cur為初始變量，即為了操作連結清單初始建立的變量，head是連結清單頭節點，dummy是啞節點，用于操作頭節點，cur為目前節點，為頭節點的下一個節點
• pre、temp為循環變量，是為了在循環中的操作建立，pre從啞節點開始，每次循環後移，比較每個元素和cur的大小，到cur的前一節點為止，temp是cur的下一個節點，用于在循環中将cur後移