归并排序算法-Java面试指南

当前位置:　首页>> 技术小册>> Java面试指南

当需要对一个较大的数组进行排序时，归并排序是一种非常高效的排序算法。它的基本思想是将一个大数组分成两个子数组，递归地对两个子数组进行排序，然后再将排序后的子数组合并成一个大数组。下面是一个使用Java编写的归并排序算法：

```java
public class MergeSort {

public void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

private void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);
            merge(arr, left, middle, right);
        }
    }

private void merge(int[] arr, int left, int middle, int right) {
        int[] temp = new int[arr.length];
        for (int i = left; i <= right; i++) {
            temp[i] = arr[i];
        }
        int i = left;
        int j = middle + 1;
        int k = left;
        while (i <= middle && j <= right) {
            if (temp[i] <= temp[j]) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            arr[k] = temp[i];
            k++;
            i++;
        }
        while (j <= right) {
            arr[k] = temp[j];
            k++;
            j++;
        }
    }
}
```

在这个算法中，sort方法调用了私有的mergeSort方法，该方法递归地对左半部分和右半部分进行排序，最后将这两个部分合并。

该分类下的相关小册推荐：

手把手带你学习SpringBoot-零基础到实战

SpringBoot合辑-高级篇

Mybatis合辑3-Mybatis动态SQL

Java语言基础14-枚举和注解

Java语言基础16-JDK8 新特性

Java必知必会-JDBC

Java语言基础13-类的加载和反射

Mybatis合辑1-Mybatis基础入门

Java语言基础3-流程控制

JAVA 函数式编程入门与实践

Java高并发秒杀入门与实战

经典设计模式Java版