Java版八大排序之归并排序(附Java代码及详解)

小咪咪 2023-02-10 05:08 72阅读 0赞

**归并排序**：是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序**是一种稳定的排序方法**。

归并排序比较占用内存，但却是一种效率高且稳定的算法。

归并排序原理：

*  把有序表划分成元素个数尽量相等的两半
 *  把两半元素分别排序
 *  把两个有序表合并成一个

归并操作的工作原理如下：

> 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列  
> 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置  
> 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾  
> 将另一序列剩下的所有元素直接复制到合并序列尾

时间复杂度：O(nlog₂n)  
空间复杂度：O(n)

具体实现如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70]  
Java详细代码：

public class leetcode { 
        public static void main(String[] args) { 
            int[] arr = new int[]{ 8,5,3,6,2,3,5,8,9,1,32,14,32,16,7,43,45,67,86};
            //调用归并排序算法
            sort(arr);
        }
        public static void sort(int[] arr){ 
        	//定义一个链表，长度为数组长度
            Node[] noarr = new Node[arr.length];
            for (int i = 0; i <  arr.length; i++) { 
            	//新建一个节点
                Node no = new Node();
                //将数组的值赋给value
                no.value = arr[i];
                noarr[i] = no;
            }
            for (;;){ 
            	//取数据长度的一半
                int newlength = noarr.length / 2;
                if (newlength * 2 < noarr.length){ 
                    newlength += 1;
                }
                //新建一个链表
                Node[] arrnew = new Node[newlength];
                int num = 0;
                //两两进行比较排序
                for (int i = 0; i < noarr.length;) { 
                    Node no1 = noarr[i];
                    //对最后只剩单个进行判断
                    if (i + 1 >= noarr.length){ 
                        arrnew[num] = no1;
                        break;
                    }
                    Node no2 = noarr[i + 1];
                    //调用两个有序链表合并的函数
                    Node no3 = re(no1,no2);
                    i = i + 2;
                    //将合并后的链表放到数组里
                    arrnew[num] = no3;
                    num++;
                }
               
                noarr = arrnew;
                if (newlength == 1)
                    break;
            }
            System.out.println(noarr[0]);
        }
        //两个有序链表的合并
        public static Node re(Node no1,Node no2){ 
            Node result = null;
            if(no1.value <= no2.value){ 
                result = no1;
                no1 = no1.next;
            }else{ 
                result = no2;
                no2 = no2.next;
            }
            Node flag = result;
            while (no1 != null){ 
                if (no2 != null){ 
                    if (no1.value <= no2.value) { 
                        flag.next = no1;
                        no1 = no1.next;
                    }
                    else { 
                        flag.next = no2;
                        no2 = no2.next;
                    }
                }else{ 
                    flag.next = no1;
                    break;
                }
                flag = flag.next;
            }
            if(no2 != null){ 
                flag.next = no2;
            }
            return result;
        }
    }

public class Node { 
       public int value;
       public Node next;
        @Override
        public String toString() { 
            return "Node{" +
                    "value=" + value +
                    ", next=" + next +
                    '}';
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020052011051626.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1,size_16,color_FFFFFF,t_70