从头开始复习算法之归并排序

前一篇文章主要讲道理基础的几个算法，论其思想还是比较基础的，但是今天开始讲解的归并排序就不那么简单了。

关于归并排序呢？其实思想也并不是很麻烦，最核心的思想我就用简单的讲述方式给大家来讲述一下：

一、 简单的归并排序步骤

1.1、 初始化数据

A数组的指针	数组A		数组B	B数组的指针
2		4
-	8		5	-
-	9		6	-
-	10		7	-

数组C	0	1	2	3	4	5	6	7
指针位置
值

如上表所示，存在两个递增的数组（A，B），然后将A，B数组的指针拨到数组的首位。另外存在一个数组C，长度是两个递增数组之和，并且将该数组的指针也拨到首位。

1.2、指针有条件的遍历数组

A数组的指针	数组A		数组B	B数组的指针
-	2		4
8		5	-
-	9		6	-
-	10		7	-

数组C	0	1	2	3	4	5	6	7
指针位置
值	2

首先我们来判断A指针指向的数值和B指针指向的数值做比较，如果A指针的数值小于B指针的数值，就将A指针指向的数值填写到数组C中，并且将A，C指针同时指向其数组的下一位。

1.3、继续指针有条件的遍历数组

A数组的指针	数组A		数组B	B数组的指针
-	2		4	-
8		5
-	9		6	-
-	10		7	-

数组C	0	1	2	3	4	5	6	7
指针位置
值	2	4

首先我们来判断A指针指向的数值和B指针指向的数值做比较，如果A指针的数值大于B指针的数值，就将B指针指向的数值填写到数组C中，并且将B，C指针同时指向其数组的下一位。

1.4、 继续重复重复

重复的操作直到一个数组遍历完全，最终的效果如下：

A数组的指针	数组A		数组B	B数组的指针
-	2		4	-
8		5	-
-	9		6	-
-	10		7	-
-

数组C	0	1	2	3	4	5	6	7
指针位置
值	2	4	5	6	7

1.4、将可能剩余的A，B数据抄写到数组C中

当B指针遍历完B数组之后，就把剩下的A数组剩下的元素抄写到数组C中，就完成了归并排序。效果如下：

A数组的指针	数组A		数组B	B数组的指针
-	2		4	-
-	8		5	-
-	9		6	-
-	10		7	-

数组C	0	1	2	3	4	5	6	7
指针位置
值	2	4	5	6	7	8	9	10

1.6、具体的代码如下：

就这样简简单单的几步操作就完成了 归并操作，是不是很简单呢？

好了，我们来简单的写一下代码。

在写代码之前，我们首先整理一下思维：前面说到的是存在两个有序的数组，明显我们在实际的操作中只可能给你一个数组做排序，我们可以创建一个数组，然后里面有两段有序的数列。如下所示：

[2,8,9,10,4,5,6,7]

然后我们将两个有序数组择出来，再进行数组的遍历比较，将比较小的元素写在原数组中，直到一个数组被遍历完全，最后将另外一个没有遍历完数组的剩余元素抄写到原数组中。就得到新排序好的数组。具体的代码如下：

/**
 * arr = [2,8,9,10,4,5,6,7]
 * leftPos:数组的开始位置
 * midPos：数组的分割点
 * rightPos：数组的结束位置
 **/
function merge(arr,leftPos,midPos,rightPos){
	let leftArray = [];
	let rightArray=[];
	// 先将数组分成两个数组
	// arr = [2,8,9,10,4,5,6,7]
	for(let i=leftPos;i<=midPos;i++) {
		leftArray.push(arr[i]);
	}
	for(let i=midPos+1;i<=rightPos;i++) {
		rightArray.push(arr[i]);
	}
	let left = 0;
	let right=0;
	let pos=leftPos;
	// 指针的偏移
	while(left<leftArray.length && right<rightArray.length){
		if(leftArray[left]>rightArray[right]) arr[pos++] = rightArray[right++];
		else arr[pos++] = leftArray[left++];
	}
	// 剩余数据的抄写
	while(left<leftArray.length){
		arr[pos++] = leftArray[left++];
	}
	while(right<rightArray.length){
		arr[pos++] = rightArray[right++];
	}
	return arr;
}

二、真正的归并排序来了

看了上面的分析可能会有这样的疑问呀：这种限制是不是太死了，需要两段有序的数列，哪有这么巧的事儿，这样的排序是不是在实际操作中到底有什么作用呢？

好了，针对这样的疑问，我们继续去完善我们的代码。首先在完善代码之前 我们得提到一个概念：分治

什么叫分治呢？我的理解就是分而治之，就是将完全没有顺序的数组，从当中一刀切开，分成两小份，如果两份是有序数组，就用上面的思想来归并，如果不是就非有序的新数组再从中切一刀…就这样不断切分，直到找到有序数组位置（数组里面只有一项，肯定是有序的）。然后再不断的向上归并。就得到了一个排序好的序列了。

有点懵逼，这货在讲什么？好，来看下面的示意图：

               [3 ,2 , 4, 1 , 10, 8, 9, 6]
                   |             |
              [3 ,2 ,4 ,1]  [ 10 , 8, 9, 6]
                  |  |          |     |
              [3 ,2] [4 ,1]  [10 ,8] [9 ,6]
               | |    | |     |  |    | |
              3 2   4 1       10 8    9 6

首先我们将数组进行切分操作。

              [3 ,2 , 4, 1 , 10, 8, 9, 6]
                   |              |
              [3 ,2 ,4 ,1]  [ 10 , 8, 9, 6]
                 |     |        |      |
              [2 ,3] [1 ,4]  [8 ,10] [6 ,9]

如上所示 我们将最底部的数据进行归并操作。得到4个有序数组，

              [3 ,2 , 4, 1 , 10, 8, 9, 6]
                   |              |
              [1 ,2 ,3 ,4]  [ 6 , 8, 9, 10]

如上所示，我们将最底部的有序数列在进行归并，得到两个有序数列，这样的两个有序数组是不是就有点熟悉了，最后我们在运用一次归并就得到了一个有序的数列。

[ 1, 2, 3, 4, 6, 8, 9, 10 ]

分治的思维就是分而治之，也叫大事儿化小，其具体的分治代码如下：

function sortArray(arr,left,right){
	if(left < right){	
		let mid = Math.floor((left+right)/2);
		sortArray(arr,left,mid)
		sortArray(arr,mid+1,right)
		arr = merge(arr,left,mid,right)
	}
	return arr;
}

全套代码如下：

/**
 * arr = [2,8,9,10,4,5,6,7]
 * leftPos:数组的开始位置
 * midPos：数组的分割点
 * rightPos：数组的结束位置
 **/
function merge(arr,leftPos,midPos,rightPos){
	let leftArray = [];
	let rightArray=[];
	// 先将数组分成两个数组
	// arr = [2,8,9,10,4,5,6,7]
	for(let i=leftPos;i<=midPos;i++) {
		leftArray.push(arr[i]);
	}
	for(let i=midPos+1;i<=rightPos;i++) {
		rightArray.push(arr[i]);
	}
	let left = 0;
	let right=0;
	let pos=leftPos;
	// 指针的偏移
	while(left<leftArray.length && right<rightArray.length){
		if(leftArray[left]>rightArray[right]) arr[pos++] = rightArray[right++];
		else arr[pos++] = leftArray[left++];
	}
	// 剩余数据的抄写
	while(left<leftArray.length){
		arr[pos++] = leftArray[left++];
	}
	while(right<rightArray.length){
		arr[pos++] = rightArray[right++];
	}
	return arr;
}

function sortArray(arr,left,right){
	if(left < right){	
		let mid = Math.floor((left+right)/2);
		sortArray(arr,left,mid)
		sortArray(arr,mid+1,right)
		arr = merge(arr,left,mid,right)
	}
	return arr;
}

说在最后

其实归并操作思想还是比较简单的，但是我昨天搞了差不多两个多小时，主要问题是在边界值的处理上面。不知道说啥了 去睡午觉去了。

最后最后提到一句，欢迎大家点赞，关注我的个人博客，我会源源不断的输出高质量文章的。