1.归并排序

归并排序 ，归并排序是采用分治法(Divide and Conquer）的一个非常典型的应用，所以我们先来说一下什么是分治法。

分治法

定义

分治（英语：Divide and Conquer），字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

过程

分治算法的核心思想就是「分而治之」。

大概的流程可以分为三步：分解 -> 解决 -> 合并。

1. 分解原问题为结构相同的子问题。
2. 分解到某个容易求解的边界之后，进行递归求解。
3. 将子问题的解合并成原问题的解。

分治法能解决的问题一般有如下特征：

• 该问题的规模缩小到一定的程度就可以容易地解决。
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

参考链接：

递归 & 分治 - OI Wiki (oi-wiki.org)

了解清楚分治法后，我们来看归并排序

归并排序

merge

归并排序最核心的部分是合并（merge）过程：将两个有序的数组 a[i] 和 b[j] 合并为一个有序数组 c[k]。

从左往右枚举 a[i] 和 b[j]，找出最小的值并放入数组 c[k]；重复上述过程直到 a[i] 和 b[j] 有一个为空时，将另一个数组剩下的元素放入 c[k]。

import  java.util.*;public class MergeSort {public static void main(String[] args) {int[] a = {3, 4, 5};int[] b = {1, 2};System.out.println("合并后的数组: " + Arrays.toString(merge(a, b)));}public static int[] merge(int[] a, int[] b) {int i = 0, j = 0;int[] c = new int[a.length + b.length];while (i < a.length && j < b.length) {// 数组b比a小if (b[j] < a[i]) {// 将b[j]添加到c中，并增加j ，一定不能写成++jc[i + j] = b[j++];} else {c[i + j] = a[i++];}}// b数组遍历完了，将a数组中剩余元素添加到c中while (i < a.length) {c[i + j] = a[i++];}// a 数组遍历完了，将b数组中剩余的元素添加到c中while (j < b.length) {c[i + j] = b[j++];}return c;}
}

分治法

1. 当数组长度为 为1 时，该数组就已经是有序的，不用再分解。

2. 当数组长度大于 1 时，该数组很可能不是有序的。此时将该数组分为两段，再分别检查两个数组是否有序（用第 1 条）。如果有序，则将它们合并为一个有序数组；否则对不有序的数组重复第 2 条，再合并。

整个流程见下图

    public static int[] mergeSort(int[] arr) {if (arr.length <= 1) {return arr;}int middle = arr.length / 2;// 取原本数组的一个副本，左半部分int[] left = Arrays.copyOfRange(arr, 0, middle);// 取原本数组的一个副本，右半部分int[] right = Arrays.copyOfRange(arr, middle, arr.length);left = mergeSort(left);right = mergeSort(right);return merge(left, right);}

整体代码

整个归并排序的代码如下

package mbb;import java.util.Arrays;public class MergeSortExample {// 归并两个数组的辅助方法public static int[] merge(int[] left, int[] right) {int[] result = new int[left.length + right.length];int i = 0, j = 0, k = 0;while (i < left.length && j < right.length) {if (left[i] <= right[j]) {result[k++] = left[i++];} else {result[k++] = right[j++];}}// 将剩余的元素拷贝到结果数组while (i < left.length) {result[k++] = left[i++];}while (j < right.length) {result[k++] = right[j++];}return result;}// 归并排序的主要方法public static int[] mergeSort(int[] arr) {if (arr.length <= 1) {return arr;}int middle = arr.length / 2;// 取原本数组的一个副本，左半部分int[] left = Arrays.copyOfRange(arr, 0, middle);// 取原本数组的一个副本，右半部分int[] right = Arrays.copyOfRange(arr, middle, arr.length);left = mergeSort(left);right = mergeSort(right);return merge(left, right);}// 主函数，用于演示归并排序public static void main(String[] args) {int[] arr = {34, 7, 23, 32, 5, 62};System.out.println("Original array: " + Arrays.toString(arr));int[] sortedArr = mergeSort(arr);System.out.println("Sorted array: " + Arrays.toString(sortedArr));}
}

不懂的强烈建议看下面三个链接

排序算法：归并排序【图解+代码】_哔哩哔哩_bilibili

归并排序 - OI Wiki (oi-wiki.org)

图解归并排序，带你彻底了解清楚！_归并排序算法过程图解-CSDN博客

冒泡排序

冒泡排序的思想非常简单

1. 比较相邻的元素。如果第一个比第二个大（小），就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大（小）的数。
3. 针对所有的元素重复以上的步骤，除了最后已经选出的元素（有序）。
4. 持续每次对越来越少的元素（无序元素）重复上面的步骤，直到没有任何一对数字需要比较，则序列最终有序。

public class BubbleSortExample {public static void main(String[] args) {int[] array = {64, 34, 25, 12, 22, 11, 90};bubbleSort(array);System.out.println("Sorted array:");for (int i = 0; i < array.length; i++) {System.out.print(array[i] + " ");}}public static void bubbleSort(int[] array) {for (int i = 0; i < array.length - 1; i++) {for (int j = 0; j < array.length - 1 - i; j++) {if (array[j] > array[j + 1]) {// 交换array[j]和array[j+1]int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}}}
}