算法学习（四）——归并排序

今天药忘吃喽~ 2022-07-12 06:12 135阅读 0赞

# 算法学习（四）——归并排序 #

问题：给定数组，进行排序。

方法：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路[归并][Link 1]。

归并过程为：比较a\[i\]和a\[j\]的大小，若a\[i\]≤a\[j\]，则将第一个有序表中的元素a\[i\]复制到r\[k\]中，并令i和k分别加上1；否则将第二个有序表中的元素a\[j\]复制到r\[k\]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间\[s,t\]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间\[s,t\]。（摘自百度百科）

实现：

package com.xueyou;
    
    public class MergeSort {
        /**
         * 打印数组
         *
         * @param a
         */
        public static void printArray(int[] a) {
            for (int num : a) {
                System.out.print(num + "\t");
            }
            System.out.println("");
        }
    
        /**
         * 合并两个有序数组，组成一个新的有序数组
         * @param a
         * 第一个数组开始下标
         * @param s
         * 第二个数组开始下标
         * @param m
         * 第二个数组结束下标
         * @param t
         */
        public static void merge(int[] a, int s, int m, int t) {
            int[] temp = new int[t - s];
            int i = s, j = m, k = 0;
            while (i < m && j < t) {
                if (a[i] <= a[j]) {
                    temp[k] = a[i];
                    i++;
                } else {
                    temp[k] = a[j];
                    j++;
                }
                k++;
            }
            while (i < m) {
                temp[k] = a[i];
                i++;
                k++;
            }
            while (j < t) {
                temp[k] = a[j];
                j++;
                k++;
            }
            printArray(temp);
            System.arraycopy(temp, 0, a, s, temp.length);
        }
    
        /**
         * 递归 实现合并
         * @param a
         * @param s
         * @param len
         */
        public static void mergeSort(int a[], int s, int len) {
            int size = a.length;
            int times = size / (len << 1);
            int whetherOdd = size % 2;
            if (times == 0) {
                return;
            }
            for (int i = 0; i < times; i++) {
                int start = i * len * 2;
                merge(a, start, start + len, start + (len << 1));
            }
            //把剩下的一项归到倒数第一中
            if (whetherOdd != 0) {
                merge(a, size - 1 - (len << 1), size - 1, size);
            }
            mergeSort(a, 0, len * 2);
    
        }
    
        public static void main(String[] args) {
            System.out.println("奇数个：");
            int[] a = {3, 2, 1, 9, 4, 5, 8, 6, 7};
            printArray(a);
            System.out.println("===============排序中==============");
            mergeSort(a, 0, 1);
            System.out.println("===============排序中==============");
            printArray(a);
    
    
            System.out.println("偶数个：");
            int[] b = {3, 5, 4, 9, 7, 2, 6, 1};
            printArray(b);
            System.out.println("===============排序中==============");
            mergeSort(b, 0, 1);
            System.out.println("===============排序中==============");
            printArray(b);
    
    
        }
    }

运行结果：

![Center][]

![Center 1][]

[Link 1]: http://baike.baidu.com/view/711818.htm
[Center]: /images/20220711/ea083c5330344468ac767c6b485592a8.png
[Center 1]: /images/20220711/dcf43af19c074d5f9fb71e69eaac5a3d.png