基本原理

归并排序采用分治的思想，即分而治之，分就是将一个大问题分成一些小问题求解，治就是将分得的小问题得到的答案和在一起，得到最终的结果。体现在归并排序上，就是将大的数组分成小的序列，一直分到每个序列中只包含一个元素，此时序列内有序，然后两两合并，合并的方式即是合并两个有序数组，最终序列间有序，即整个数组有序，基本过程如下图所示

代码实现

public void mergeSort(int[] array, int start, int end, int[] temp) {//2.直至每个序列只包含一个元素，停止划分if (start >= end) {return;}//1.从中间开始，每次划分为两个序列mergeSort(array, start, (start + end) / 2, temp);mergeSort(array, (start + end) / 2 + 1, end, temp);//3。进行有序数组的合并merge(array, start, end, temp);
}public void merge(int[] array, int start, int end, int[] temp) {//找到序列中点int mid = (start + end) / 2;//left遍历左边的序列int left = start;//right遍历右边的序列int right = mid + 1;//index遍历临时数组，存储合并结果int index = 0;//两个序列均从起点到终点进行遍历while (left <= mid && right <= end) {//将两个序列中较小的元素放入临时数组中if (array[left] < array[right]) {temp[index++] =array[left++];}else {temp[index++] =array[right++];}}//此时仅剩一个序列未遍历结束，直接赋值while (left <= mid){temp[index++] =array[left++];}while (right<=end){temp[index++] =array[right++];}//将归并的结果拷贝到原数组for (int i=start;i<=end;i++){array[i] = temp[i];}
}

例题分析

数组中的第K个最大元素

问题描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
详见leetcode215

问题分析

使用归并排序对数组进行从大到小的排序，排序后，返回数组下标为K-1的值，即为数组中第K大元素。

代码实现

public int findKthLargest(int[] nums, int k) {int[] temp = new int[nums.length];mergeSort(nums,0,nums.length-1,temp);return nums[k-1];
}public void mergeSort(int[] array, int start, int end, int[] temp) {//2.直至每个序列只包含一个元素，停止划分if (start >= end) {return;}//1.从中间开始，每次划分为两个序列mergeSort(array, start, (start + end) / 2, temp);mergeSort(array, (start + end) / 2 + 1, end, temp);//3。进行有序数组的合并merge(array, start, end, temp);
}public void merge(int[] array, int start, int end, int[] temp) {//找到序列中点int mid = (start + end) / 2;//left遍历左边的序列int left = start;//right遍历右边的序列int right = mid + 1;//index遍历临时数组，存储合并结果int index = left;//两个序列均从起点到终点进行遍历while (left <= mid && right <= end) {//将两个序列中较小的元素放入临时数组中if (array[left] > array[right]) {temp[index++] =array[left++];}else {temp[index++] =array[right++];}}//此时仅剩一个序列未遍历结束，直接赋值while (left <= mid){temp[index++] =array[left++];}while (right<=end){temp[index++] =array[right++];}//将归并的结果拷贝到原数组for (int i=start;i<=end;i++){array[i] = temp[i];}
}