面试题积累篇-简单算法（二）

系统管理员 2022-07-13 00:25 177阅读 0赞

常见的算法分类几大类，这次说一下归并排序。  
采用分治法将两个（或两个以上）有序表合并成一个新的有序表，先使每个子序列有序，再使子序列段间有序。

就是将待排序的数组进行一系列的分割，在分割之后进行归并，归并时是有顺序的，通过递归将有序的子序列合成一个最终的排好顺序的数组。

package com.yang.algorithm.test;
    
    public class MergeSort {
        public static void main(String[] args) {
            int[] array = {1, 45, 20, 31, 78, 456, 123, 25, 32};
            System.out.println("排序之前：");
            for (int a : array) {
                System.out.print(a + " ");
            }
            mergeSort(array, 0, array.length - 1);
            System.out.println("\n" + "排序之前：");
            for (int a : array) {
                System.out.print(a + " ");
            }
        }
    
        // 合并两个有序数组为一个有序数组 
        private static void merge(int[] array, int low, int mid, int high) {
            //定义缓存数组 
            int[] temp = new int[high - low + 1];
            //定义左指针 
            int left = low;
            //定义右指针 
            int right = mid + 1;
            //定义缓存数组指针 
            int tPoint = 0;
            //将小数放到新的数组当中 
            while (left <= mid && right <= high) {
                if (array[left] < array[right]) {
                    temp[tPoint++] = array[left++];
                } else {
                    temp[tPoint++] = array[right++];
                }
            }
            // copy左边剩余元素 
            while (left <= mid) {
                temp[tPoint++] = array[left++];
            }
            // copy右边剩余元素 
            while (right <= high) {
                temp[tPoint++] = array[right++];
            }
            // 将缓存数组的元素赋给原数组 
            for (int tPoint1 = 0; tPoint1 < temp.length; tPoint1++) {
                array[tPoint1 + low] = temp[tPoint1];
            }
        }
    
        public static void mergeSort(int[] array, int low, int high) {
            int mid = (low + high) / 2;
            if (low < high) {
                //分割左边 
                mergeSort(array, low, mid);
                //分割右边 
                mergeSort(array, mid + 1, high);
                //左右归并 
                merge(array, low, mid, high);
            }
        }
    } 
    
                下面还有一种我感觉更易理解的方式如下：package com.yang.algorithm.test;
    
    public class MergeSort {
        public static void main(String[] args) {
            int[] array = {1, 45, 20, 31, 78, 456, 123, 25, 32};
            System.out.println("排序之前：");
            for (int a : array) {
                System.out.print(a + " ");
            }
            mergeSort(array, 0, array.length - 1);
            System.out.println("\n" + "排序之后：");
            for (int a : array) {
                System.out.print(a + " ");
            }
        }
    
        // 合并两个有序数组为一个有序数组 
        private static void merge(int[] array, int start1, int end1, int start2, int end2) {
            System.out.printf("\n开始合并,合并范围,[%d,%d],[%d,%d]", start1, end1, start2, end2);
            int start = start1;
            // 临时数组 
            int[] t = new int[end2 - start1 + 1];
            // 临时数组下标 
            int i = 0;
            // 比较开始 
            while (start1 <= end1 && start2 <= end2) {
                if (array[start1] < array[start2]) {
                    t[i] = array[start1];
                    start1++;
                    i++;
                    continue;
                }
                if (array[start1] > array[start2]) {
                    t[i] = array[start2];
                    start2++;
                    i++;
                    continue;
                }
            }
            // 拷贝剩余元素 
            while (start1 <= end1) {
                t[i] = array[start1];
                start1++;
                i++;
            }
            // 拷贝剩余元素 
            while (start2 <= end2) {
                t[i] = array[start2];
                start2++;
                i++;
            }
            // 将已排好序的元素放回对应位置 
            for (i = 0; i < t.length; i++) {
                array[start + i] = t[i];
            }
            // 打印数组 
            PrintArray(array);
        }
    
        public static void mergeSort(int[] array, int start, int end) {
            if (start >= end) {
                return;
            }
            int m = (start + end) / 2;
            int start1 = start;
            int end1 = m;
            int start2 = m + 1;
            int end2 = end;
            mergeSort(array, start1, end1);
            mergeSort(array, start2, end2);
            merge(array, start1, end1, start2, end2);
        }
    
        // 打印数组 
        private static void PrintArray(int[] s) {
            System.out.print("\n下标:");
            for (int p = 0; p < s.length; p++) {
                System.out.printf("%2d,", p);
                System.out.print(p + " ");
            }
            System.out.print("\n" + "元素:");
            for (Integer m : s) {
                System.out.printf("%2d,", m);
            }
            System.out.print("\n-----------------------------");
        }
    }

运行结果如下：

![Center][]

[Center]: /images/20220713/9242809b9d9f454aac338a0919d6e8c8.png