欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

基于链表的快速排序及归并排序

程序员文章站 2022-05-13 19:32:27
...

归并排序

package 算法和数据结构;
/**
* Filename : LinkedList_MergeSort.java
* Author : [email protected]
* Creation time : 下午5:47:02 - 2017年3月26日
* Description :
*/

class ListNode {
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null;
    }
}
public class LinkedList_MergeSort{
    public ListNode sortList(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        ListNode mid=findMid(head);
        ListNode right=mid.next;
        mid.next=null;
        return merge(sortList(head),sortList(right));
    }
    private ListNode merge(ListNode head1,ListNode head2){
        ListNode dummy=new ListNode(0);
        ListNode cur=dummy;
        while(head1!=null&&head2!=null){
            if(head1.val<=head2.val){
                cur.next=head1;
                head1=head1.next;
            }else{
                cur.next=head2;
                head2=head2.next;
            }
            cur=cur.next;
        }
        if(head1!=null){
            cur.next=head1;
        }else if(head2!=null){
            cur.next=head2;
        }
        return dummy.next;
    }
    private ListNode findMid(ListNode head){
        if(head==null){
            return head;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

快速排序

package 算法和数据结构;
/**
* Filename : LinkedList_QuickSort.java
* Author : [email protected]
* Creation time : 下午5:50:18 - 2017年3月26日
* Description :
*/

public class LinkedList_QuickSort{
    public ListNode sortList(ListNode head){
        return quickSort(head,null);
    }
    private ListNode quickSort(ListNode head,ListNode end){
        if(head!=end){
            ListNode cur=partion(head,end);
            quickSort(head,cur);
            quickSort(cur.next,end);
        }
        return head;
    }
    private ListNode partion(ListNode head,ListNode end){
        int key=head.val;
        ListNode p=head;
        ListNode q=head.next;
        while(q!=end){
            if(q.val<key){
                p=p.next;
                swap(p,q);
            }
            q=q.next;
        }
        swap(head,p);
        return p;
    }
    private void swap(ListNode p,ListNode q){
        int temp=p.val;
        p.val=q.val;
        q.val=temp;
    }
}