您现在的位置是：首页 > Java

当前栏目

归并排序-Java

JAVA 排序

2023-03-02 11:02:59 时间

package offer;
    
    /**
     * 归并排序：
     * 原理：将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为有序序列。
     要点：归并、分治
     */
    public class MergeSort {
    
        private static void mergeSort(int[] a) {
            int[] b = new int[a.length];
            mergeSort(a, b, 0, a.length - 1);
        }
        private static void mergeSort(int[] a, int[] b, int left, int right) {
            if (left < right) {
                int center = left + (right - left) / 2;
                mergeSort(a, b, left, center);
                mergeSort(a, b, center + 1, right);
                merge(a, b, left, center + 1, right);
            }
        }
        private static void merge(int[] a, int[] b,
                                  int leftPos, int rightPos,
                                  int rightEnd) {
            int leftEnd = rightPos - 1;
            int tempPos = leftPos;
            int numElements = rightEnd - leftPos + 1;
    
            while (leftPos <= leftEnd && rightPos <= rightEnd) {
                if (a[leftPos] <= a[rightPos]) {
                    b[tempPos] = a[leftPos];
                    tempPos++;
                    leftPos++;
                } else {
                    b[tempPos] = a[rightPos];
                    tempPos++;
                    rightPos++;
                }
            }
            while (leftPos <= leftEnd) {
                b[tempPos] = a[leftPos];
                tempPos++;
                leftPos++;
            }
            while (rightPos <= rightEnd) {
                b[tempPos] = a[rightPos];
                tempPos++;
                rightPos++;
            }
            for (int i = 0; i < numElements; i++, rightEnd--) {
                a[rightEnd] = b[rightEnd];
            }
        }
    
        public static void printArray(int[] a){
            for (int i : a){
                System.out.print(i + " ");
            }
        }
    
        public static void main(String[] args){
            int[] a = {1,4,3,5,2,6,9,8,7};
            mergeSort(a);
            printArray(a);
        }
    }

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

归并排序-Java

相关文章