Java排序算法---->归并排序算法

一，归并排序算法
1，归并排序的基本思路就是把数组分为两组A和B，如果这两组组内的数据都是有序的，那么就可以很方便的将这两组数据进行排序了。如果让这两组组内数据有序？
2，可以将A，B组各自再分成两组，依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的两个小组就可以了。这样通过先递归的分解数列，再合并数据就完成了归并排序。
3，归并排序算法是一种稳定的排序。
4，归并排序算法在时间复杂度最好情况和最坏情况下都是O(nlogn)。
5，归并排序算法的空间复杂度为O(n).
6，归并排序的存储结构：可以用顺序存储，可以在链表上实现。

二，采用数组的形式完成归并排序算法（用java实现）

import java.util.*;
public class Test2{

public void sort(int []datas, int first,int last)
    {
int mid=(first+last)/2;
if(first<last)
        {
            sort(datas,first,mid);   //左边不断递归
            sort(datas,mid+1,last);   //右边不断递归

            finalmerge(datas,first,mid,last);//最后的归并排序的核心，包括了左元素，中间元素，右元素。
        }
    }

public void finalmerge(int []datas, int first,int mid,int last)
    {
int []tempdata=new int[datas.length];

int i=first;//左边数组第一个元素
int j=mid+1;//右边数组的第一个元素。

int k=first;
int yuanshi=first;
//接下来就是把两个有序的数组合并成一个新的有序数组。
while(i<=mid&&j<=last)
        {
if(datas[i]<datas[j])
            {
                tempdata[k]=datas[i];
                k++;
                i++;
            }
else
            {
                tempdata[k]=datas[j];
                k++;
                j++;
            }
        }

while(i<=mid)
        {
            tempdata[k]=datas[i];
            k++;
            i++;
        }
while(j<=last)
        {
            tempdata[k]=datas[j];
            k++;
            j++;
        }

//合并成新的数组后，再把新数组重新复制给原来的数组datas中去。
while(yuanshi<=last)
        {
            datas[yuanshi]=tempdata[yuanshi];
            yuanshi++;
        }

    }

public static void main(String []args)
    {
        Test2 test=new Test2();
int []datas=new int[]{5,2,4,8,1};

        test.sort(datas,0,datas.length-1);  //开始以0开始，以datas.length-1结尾

        System.out.println("归并排序后的结果如下：");
for(int i=0;i<datas.length;i++)
        {
            System.out.print(datas[i]+" ");
        }
        System.out.println();
    }
}

三，采用链表的存储结果完成归并排序（用java实现）

import java.util.*;   //leetcode 148
class ListNode{
int val;
    ListNode next;
    ListNode(int x)
    {
        val=x;
    }
}
public class Test2{

public ListNode getMiddle(ListNode head)
    {
        ListNode first=head; //first每次移动一个结点
        ListNode second=head;  //second每次移动两个结点，当second移动最后一个结点的时候，那么first就指向了中间的那个结点

while(first.next!=null&&first.next.next!=null)
        {
            first=first.next.next;
            second=second.next;
        }

return second;
    }


public ListNode mergetwo(ListNode firstList,ListNode secondList)
    {
        ListNode root=new ListNode(-1);
        ListNode current=root;
while(firstList!=null&&secondList!=null)
        {
if(firstList.val<=secondList.val)
            {
                current.next=firstList;
                firstList=firstList.next;
            }else
            {
                current.next=secondList;
                secondList=secondList.next;
            }
            current=current.next;
        }

if(firstList!=null)
        {
            current.next=firstList;
        }
if(secondList!=null)
        {
            current.next=secondList;
        }


return root.next;
    }

public ListNode sortList(ListNode head)
    {
if(head==null||head.next==null)
        {
return head;
        }

        ListNode mid=getMiddle(head);
        ListNode next=mid.next;
        mid.next=null;//把两个链表断开来，形成左链表和右链表

return mergetwo(sortList(head),sortList(next));   //不断递归调用
    }

public static void main(String []args)
    {
        Test2 test=new Test2();
        ListNode l1=new ListNode(5);
        ListNode l2=new ListNode(2);
        ListNode l3=new ListNode(4);
        ListNode l4=new ListNode(8);
        ListNode l5=new ListNode(1);

        l1.next=l2;
        l2.next=l3;
        l3.next=l4;
        l4.next=l5;


        ListNode node=test.sortList(l1);
while(node!=null)
        {
            System.out.print(node.val+" ");
            node=node.next;
        }
        System.out.println();
    }
}

运行结果：

1 2 4 5 8