常用数据结构与算法实现
以下博客根据B站罗召勇老师视频：数据结构与算法基础-Java版（罗召勇）写的详细笔记
数据结构与算法基础：
数据结构与算法之基础概述
数据结构：
（一）数据结构与算法之数组
（二）数组结构与算法之栈
（三）数据结构与算法之队列
（四）数据结构与算法之链表
（五）数据结构与算法之树结构基础
（六）数据结构与算法之二叉树大全
（七）数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)
（八）数据结构与算法之多路查找树（2-3树、2-3-4树、B树、B+树）
（九）数据结构与算法之图结构
十大经典算法：
（一）数据结构与算法之冒泡排序（含改进版）
（二）数据结构与算法之选择排序（含改进版）
（三）数据结构与算法之插入排序（含改进版）
（四）数据结构与算法之希尔排序
（五）数据结构与算法之归并排序
（六）数据结构与算法之快速排序
（七）数据结构与算法之堆排序
（八）数据结构与算法之计数排序
（九）数据结构与算法之桶排序
（十）数据结构与算法之基数排序
归并排序概念
归并排序（Merge Sort）是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
动图展示：
动图1
动图2
代码实现
import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] arr = {6, 5, 3, 1, 8, 7, 2, 4}; mergeSort(arr, 0, arr.length - 1); // [5, 6, 3, 1, 8, 7, 2, 4] // [5, 6, 1, 3, 8, 7, 2, 4] // [1, 3, 5, 6, 8, 7, 2, 4] // [1, 3, 5, 6, 7, 8, 2, 4] // [1, 3, 5, 6, 7, 8, 2, 4] // [1, 3, 5, 6, 2, 4, 7, 8] // [1, 2, 3, 4, 5, 6, 7, 8] } //归并排序 public static void mergeSort(int[] arr, int low, int high) { int middle = (high + low) / 2; //递归结束 if (low < high) { //处理左边 mergeSort(arr, low, middle); //处理右边 mergeSort(arr, middle + 1, high); //归并 merge(arr, low, middle, high); } } //归并操作 //low:开始位置，middle：分割位置，high：结束位置 public static void merge(int[] arr, int low, int middle, int high) { //用于存储归并后的临时数组 int[] temp = new int[high - low + 1]; //记录第一个数组中需要遍历的下标 int i = low; //记录第二个数组中需要遍历的下标 int j = middle + 1; //用于记录在临时数组中存放的下标 int index = 0; //遍历两个数组取出小的数字，放入临时数组中 while (i <= middle && j <= high) { //第一个数组的数据更小 if (arr[i] <= arr[j]) { //把小的数组放入临时数组中 temp[index] = arr[i]; //让下标向后移一位 i++; } else { temp[index] = arr[j]; j++; } //每存入一个数字后，临时数组下标后移 index++; } //上面的循环退出后，把剩余的元素依次填入到temp中,以下两个while只有一个会执行 //前面一个数组有多余数据 while (i <= middle) { temp[index] = arr[i]; i++; index++; } //后面一个数组有多余数据 while (j <= high) { temp[index] = arr[j]; j++; index++; } //把临时数组中的数据重新存入原数组 for (int k = 0; k < temp.length; k++) { arr[k + low] = temp[k]; } //打印每次排序后的结果 System.out.println(Arrays.toString(arr)); } }
时间复杂度
最优时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
稳定性：稳定