归并排序是一种有效的排序算法，采用分治法（Divide and Conquer）策略。它将数组分成两半，对每一半递归地进行排序，然后将两个有序的半部分合并成一个整体的有序数组。归并排序在最坏情况、平均情况和最好情况下都保持(O(n \log n))的时间复杂度，是一种稳定的排序算法。由于其分而治之的特性，归并排序特别适合于大规模数据集合的排序，尤其是链表排序。
归并排序的工作原理：
- 分解：将待排序的数组分解成两个序列，每个序列包含一半的元素。
- 解决：递归地对两个序列进行归并排序。
- 合并：将两个已排序的序列合并成一个有序的序列。
归并排序的特点：
- 稳定性：归并排序是稳定的排序算法，即相等的元素的相对顺序在排序后不会改变。
- 非原地排序：在合并过程中需要额外的存储空间来暂存数据，空间复杂度为(O(n))。
- 适合于链表：归并排序适合于链表这种数据结构，因为它不依赖于随机访问特性。
Java实现归并排序：
public class MergeSort {
// 主函数调用这个方法进行排序
public static void sort(int[] array) {
if (array.length < 2) {
return; // 基本情况
}
int middle = array.length / 2;
int[] left = new int[middle];
int[] right = new int[array.length - middle];
System.arraycopy(array, 0, left, 0, middle);
System.arraycopy(array, middle, right, 0, array.length - middle);
sort(left); // 对左半部分排序
sort(right); // 对右半部分排序
merge(array, left, right); // 合并两个已排序的部分
}
// 合并两个已排序的部分
private static void merge(int[] result, int[] left, int[] right) {
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++];
}
}
public static void main(String[] args) {
int[] array = {12, 11, 13, 5, 6, 7};
sort(array);
System.out.println(java.util.Arrays.toString(array));
}
}
这段代码首先检查数组的长度，如果小于2（即1或0），就不需要排序。接着，它将数组分成两部分，分别对这两部分进行递归排序，最后将排序后的两部分合并。合并是归并排序的核心，它负责将两个有序数组合并成一个有序数组。
归并排序因其稳定性和对大数据集的高效处理而受到青睐。如果你有关于归并排序的任何疑问或需要进一步的帮助，请随时提问。### 面试题1：合并K个升序链表
题目描述：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
这个问题可以通过归并排序的思想来解决，即两两合并链表，直到合并成一个链表。
Java实现：
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int left, int right) {
if (left == right) return lists[left];
int mid = left + (right - left) / 2;
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
面试题2：数组中的逆序对
题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
这个问题可以通过归并排序的方式来解决，通过归并排序过程中的合并操作计算逆序对。
Java实现：
public class Solution {
private int count = 0;
public int reversePairs(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
return count;
}
private void mergeSort(int[] nums, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
private void merge(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
count += mid - i + 1; // 关键步骤，计算逆序对
temp[k++] = nums[j++];
}
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
System.arraycopy(temp, 0, nums, left, temp.length);
}
}
归并排序是一种有效的排序算法，采用分治法（Divide and Conquer）策略。它将数组分成两半，对每一半递归地进行排序，然后将两个有序的半部分合并成一个整体的有序数组。归并排序在最坏情况、平均情况和最好情况下都保持(O(n \log n))的时间复杂度，是一种稳定的排序算法。由于其分而治之的特性，归并排序特别适合于大规模数据集合的排序，尤其是链表排序。
归并排序的工作原理：
- 分解：将待排序的数组分解成两个序列，每个序列包含一半的元素。
- 解决：递归地对两个序列进行归并排序。
- 合并：将两个已排序的序列合并成一个有序的序列。
归并排序的特点：
- 稳定性：归并排序是稳定的排序算法，即相等的元素的相对顺序在排序后不会改变。
- 非原地排序：在合并过程中需要额外的存储空间来暂存数据，空间复杂度为(O(n))。
- 适合于链表：归并排序适合于链表这种数据结构，因为它不依赖于随机访问特性。
Java实现归并排序：
public class MergeSort {
// 主函数调用这个方法进行排序
public static void sort(int[] array) {
if (array.length < 2) {
return; // 基本情况
}
int middle = array.length / 2;
int[] left = new int[middle];
int[] right = new int[array.length - middle];
System.arraycopy(array, 0, left, 0, middle);
System.arraycopy(array, middle, right, 0, array.length - middle);
sort(left); // 对左半部分排序
sort(right); // 对右半部分排序
merge(array, left, right); // 合并两个已排序的部分
}
// 合并两个已排序的部分
private static void merge(int[] result, int[] left, int[] right) {
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++];
}
}
public static void main(String[] args) {
int[] array = {12, 11, 13, 5, 6, 7};
sort(array);
System.out.println(java.util.Arrays.toString(array));
}
}
这段代码首先检查数组的长度，如果小于2（即1或0），就不需要排序。接着，它将数组分成两部分，分别对这两部分进行递归排序，最后将排序后的两部分合并。合并是归并排序的核心，它负责将两个有序数组合并成一个有序数组。
归并排序因其稳定性和对大数据集的高效处理而受到青睐。如果你有关于归并排序的任何疑问或需要进一步的帮助，请随时提问。
面试题3：计算右侧小于当前元素的个数
题目描述：给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
这个问题可以通过归并排序的变形来解决，在排序的过程中计算右侧小于当前元素的个数。
Java实现：
public class Solution {
private int[] count;
public List<Integer> countSmaller(int[] nums) {
List<Integer> resultList = new ArrayList<>();
count = new int[nums.length];
int[] indexes = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
indexes[i] = i;
}
mergeSort(nums, indexes, 0,