首页 > 代码库 > 归并排序 求逆序数 链表的归并排序 多线程归并排序 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