基于链表的快速排序及归并排序
程序员文章站
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;
}
}
上一篇: 快速排序和归并排序
下一篇: 解决php表单重复提交实现方法_PHP