今天会是有Offer的一天么：面试时你真的会写归并排序么
47 浏览量
2020-12-21
09:28:21
上传
评论
收藏 233KB PDF 举报
今天会是有今天会是有Offer的一天么：面试时你真的会写归并排序么的一天么：面试时你真的会写归并排序么
UP打算把八大排序算法中最难理解的几种整理一下，分别是归并排序、快排和堆排序。今天先介绍归并排序。打算把八大排序算法中最难理解的几种整理一下，分别是归并排序、快排和堆排序。今天先介绍归并排序。
先说一下归并排序的图解先说一下归并排序的图解
所谓的归并，是将两个或两个以上的有序文件合并成为一个新的有序文件，归并排序是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成
的文件，然后进行两两归并，如此重复，直至最后形成包含n个归并，得到n/2个长度为2或者1的有序文件，再两两归并，如此重复，直至最后形成包含n个
记录的有序文件位置，这种反复将两个有序文件归并成一个有序文件的排序方法称为二路归并排序。
废话不多说直接上代码废话不多说直接上代码
import java.util.ArrayList;
import java.util.Arrays;
public class MergeSortTest {
public static void main(String[] args) {
int[] num = new int[]{12, 2, 3, 18, 9, 10, 21, 7, 6, 1, 23};
System.out.println("需要排序的数组；" + Arrays.toString(num));
MergeSort(num, 0, num.length - 1);
System.out.println(Arrays.toString(num));
}
public static void MergeSort(int[] num, int left, int right) {
int middle = (left + right) / 2;
if (left >= right) {
return;
}
MergeSort(num, left, middle);
MergeSort(num, middle + 1, right);
//注意这里
Merge(num, left, middle, right);
System.out.println(Arrays.toString(num));
}
public static void Merge(int[] num, int left, int middle, int right) {
int[] num_copy = new int[right - left + 1];
int left_copy = left;
int right_copy = middle + 1;
int index = 0;
///每次进行比较，把较小的数移入新数组
while (left_copy <= middle && right_copy <= right) {
if (num[left_copy] < num[right_copy]) {
num_copy[index++] = num[left_copy++];
} else {
num_copy[index++] = num[right_copy++];
}
}
//把左边剩余的数字移入数组
while (left_copy <= middle) {
评论0