首页 > 代码库 > 归并排序 求逆序数 链表的归并排序 多线程归并排序 java
归并排序 求逆序数 链表的归并排序 多线程归并排序 java
import java.util.Scanner;public class Main { private static int count=0; public static void mergesort(int a[],int low,int high) { if(low<high) { int mid=(low+high)>>1; mergesort(a,low,mid); mergesort(a,mid+1,high); merge(a,low,mid,high); } } private static void merge(int[] a, int low, int mid, int high) { int temp[]=new int[high-low+1]; //开辟额外空间 int index=0; int beg1=low; int beg2=mid+1; while(beg1<=mid&&beg2<=high) //如果两者都存在,选在较少的一个 { if(a[beg1]<=a[beg2]) { temp[index++]=a[beg1++]; } else { temp[index++]=a[beg2++]; count+=mid-beg1+1; // 如果选中后者,对于后者会出现mid-beg1+1的逆序数 } } while(beg1<=mid) //剩下的元素 { temp[index++]=a[beg1++]; } while(beg2<=high) { temp[index++]=a[beg2++]; } for(int i=0;i<index;i++) { a[low+i]=temp[i]; } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner scn=new Scanner(System.in); int len=scn.nextInt(); while(len-->0) { count=0; int len2=scn.nextInt(); int a[]=new int[len2]; for(int i=0;i<len2;i++) { a[i]=scn.nextInt(); } mergesort(a,0,len2-1); System.out.println(count); } }}
leetcode 中的链表排序
public class Solution { public ListNode sortList(ListNode head) { if(head==null) return null; if(head.next==null) return head; ListNode list=split(head); return merge(sortList(head),sortList(list)); } //divide into two part ,return the middle address private ListNode split(ListNode head) { ListNode qucik=head; ListNode slow=head; ListNode pre=null; while(qucik!=null) { pre=slow; slow=slow.next; qucik=qucik.next; if(qucik!=null) qucik=qucik.next; } pre.next=null; return slow; } public ListNode merge(ListNode head,ListNode middle) { ListNode p1=head; ListNode p2=middle; ListNode h=new ListNode(-1); ListNode tail=h; //insert into tail; while(p1!=null&&p2!=null) { if(p1.val<=p2.val) { tail.next=p1; tail=tail.next; p1=p1.next; } else { tail.next=p2; tail=tail.next ; p2=p2.next; } } if(p1!=null) { tail.next=p1; tail=tail.next ; } if(p2!=null) { tail.next=p2; tail=tail.next ; } return h.next; } }
多线程 的归并排序
归并排序 求逆序数 链表的归并排序 多线程归并排序 java
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。