一、归并排序的定义：
归并排序是建立在归并操作上的一种有效的排序。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。分治，顾名思义，先分再治。
分在归并排序中就是将问题分解成最小的原子问题求解，并就是将各个原子问题的解合并。
二、归并排序的思想与实现：
2.1、思想：
举例说明，比如给定一个数组A = [5,2,6,1]
-
分割部分：
二分法分割数组，分成5、2 和 6、1 ， 5、2 又可以分成5和2， 6、1 又可以分成6和1。
分割
-
合并的过程，举例合并2、5 和 1、6 的过程
-
左指针2 和 右指针1比较，1小，把1放入临时数组，right指针右移一位（图1到图2的过程）
-
左指针2 和 右指针6比较， 2小，放入临时数组，left指针右移一位（图二 到图三的过程）
-
左指针5 和 右指针6比较，5小，放入临时数组，left指针已经到尾部，此时右移right指针到6（图三 到图4的过程）
-
把6放入临时数组，至此，left和right指针均到尾部，合并完成（图四到图五的过程）
合并
2.2、java代码实现
归并排序的思想可以用递归来实现，把问题不断分解成子问题，然后把子问题的解合并的过程就是递归调用。通常在递归问题中，
- 首先我们需要重复执行的可递归的逻辑是什么：
本题中，我们是先分解数组，将数组分解成左数组和右数组，然后合并左数组和右数组。这个逻辑是可以重复递归执行的（通常可以用原子问题来验证） - 我们需要搞清楚递归终止的条件是什么
在本题中，也就是数组分割到什么情况下不能再分割。数组分割我们需要不断根据数组的起始位置start和结束位置end来算出数组的中间位置middle是多少，直到数组的起始位置start>=middle,即递归终止。
大致的伪代码
sort(start,end,nums){
if(start >= middle){
return;
}
middle = (start + end)/2;
sort(start,middle,nums);
sort(middle+1,end,nums);
mergeSort(start,middle,end,nums);
}
完整的代码实现：
class Solution {
public int[] sortArray(int[] nums) {
int[] temp = new int[nums.length];
mergeSort(0,nums.length-1,nums);
return nums;
}
/**
* @param start
* @param end
* @param nums
* @return
*/
private void mergeSort(int start, int end, int[] nums) {
if (start >= end) {
return;
}
int mid = (start + end)/2;
mergeSort(start,mid,nums);
mergeSort(mid+1,end,nums);
mergeArray(start,mid, end,nums);
}
private void mergeArray(int start, int mid, int end, int[] nums) {
int p1 = start;
int p2 = mid+1;
int p=0;
int[] temp = new int[end-start+1];
while (p1 <= mid && p2 <= end) {
if (nums[p1] >= nums[p2]) {
temp[p++] = nums[p2++];
} else {
temp[p++] = nums[p1++];
}
}
while (p2 <= end) {
temp[p++] = nums[p2++];
}
while (p1 <= mid) {
temp[p++] = nums[p1++];
}
for (int i = 0; i < temp.length; i++) {
nums[i + start] = temp[i];
}
}
}
三、归并排序的时间复杂度和应用
- 归并的时间复杂度：
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(NlogN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(NlogN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。 - 应用：
力扣面试题：合并两个升序数组
力扣912题： 排序数组
《剑指 Offer》第 51 题：数组中的逆序对
力扣315题：计算右侧小于当前元素的个数
在实际项目中，通常用在比较大数据量的情况下可以使用到，比如对上G数据的排序。这个也可以从时间复杂度 nlogn 可以分析出来，常规的排序算法是O(n^2),当n越大时，logn 相比n^2的优势就会越大。
文末再附一个面试算法题：
给定两个允许有相同元素的升序数组，合并这两个数组到一个新数组中，当有多个相同元素时，清除这些元素，
要求不能使用 map 或者字典。例如 listA = [1,1,2,3,4,6]，listB = [3,5,6]，则合并后的数组为 [2,4,5,6]。
首先这个题目看到的时候，正常就是力扣上的一个题目：合并两个升序数组。
但是也有不同之处，就是升序之后我们要去除重复的元素。整体上就是先合并两个升序数组，然后再清除重复的元素。
合并升序数组的思路：
因为两个数组都是有序的，所以两个数组内之间的元素就不用再排序了，我们至需要比较这两个数组内的元素大小。举例说明：A数组中的1 和 B数组中的3 比较，哪个数组小，就移动哪个数组下标位置，1 < 3, 则A数组下标移动，继续比较A数组中下一个 1 < 3, 再比较 2<3 ,再比较 3= 3，继续移动A数组指针，4 > 3, 此时移动B数组下标到 5， 4<5 ....以此类推。我们在每次比较的过程中将小的数组元素放入到一个新的数组中，这样就完成了合并两个升序数组。
public void merge(int[] A, int m, int[] B, int n) {
int [] result = new int[m+n];
int acur = 0;
int bcur = 0;
while(acur < m || bcur < n){
if (acur < m && bcur < n) {
//A数组和B数组均未遍历到尾部
if (A[acur] <= B[bcur]) {
result[acur + bcur] = A[acur];
acur++;
} else{
result[acur + bcur] = B[acur];
bcur++;
}
} else if (bcur < n) {
//A数组遍历到尾部了
result[acur+bcur] = B[bcur];
bcur++;
} else if (acur < m) {
result[acur+bcur] = A[acur];
acur++;
//B数组遍历到尾部
}
}
}
去除重复元素的思路：
首先合并后的数组是升序的，所以重复元素是相邻的。我们只需要比较相邻的两个元素，如果相同，则遍历这个数组，从相同元素下标开始遍历，找到所有相同元素，数组元素值置为0。 再继续比较相邻元素，相同再遍历数组，元素值置为0，依次类推。
int[] result = {1,1,2,2,2,3,5,6,6};
int left = 0;
int right = 1;
int[] noRepeatResult = new int[result.length];
// 1,1,2,2,2,3,5,6,6
while (right < result.length) {
if (result[left] == result[right]) {
int x = result[left];
int count = 0;
for (int i = left; i < result.length; i++) {
if (result[i] == x) {
result[i] = 0;
count++;
} else {
break;
}
}
left += count;
right = left + 1;
} else {
left++;
right++;
}
}
List<Integer> a = new ArrayList<>();
for (int i=0;i<result.length;i++) {
if (result[i] != 0) {
a.add(result[i]);
}
}
另一种思路：
上面的思路是我们先合并数组，然后再去除重复元素，正常来说我们也可以在合并数组的过程判断元素有没有重复，有重复，不放到新数组中就可以，但是题目又要求我们不能使用map或者字典，那么我们有没有什么方式在不用map或者字典的前提下，判断元素存不存在呢？有的，位图就可以做到，此处不再赘述...
网友评论