深入学习C语言中常见的八大排序-C/C++开发

排序编程中非常基础的的理论方法，虽然排序的方法多，但是理解起来并不难，它是最基本的，初学者一定要掌握的东西。本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来

1.算法描述

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2.动图展示

3.图解展示

4.代码实现


void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
		
		for (int j = 0; j < n - 1 - i; j++) {
			if (a[j] > a[j + 1]) {
				
				swap(a[j], a[j + 1]);
			}
		}
	
	}
}

5.冒泡排序的优化

如果我们的冒泡排序比较了一圈之后发现没有发生交换，说明此时已经有序了。我们就可以退出循环。


void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
		int flag = 1;
		for (int j = 0; j < n - 1 - i; j++) {
			if (a[j] > a[j + 1]) {
				flag = 0;
				swap(a[j], a[j + 1]);
			}
		}
		if (flag) {
			break;
		}
	}
}

6.复杂度分析

时间复杂度：O（N^2)

若数组为倒序，即所有的轮次都必须执行完（最坏情况），比较次数为 n-1 + n-2 +...+ 1 = n(n-1)/2，交换次数与比较次数相同，所以时间复杂度为O(N^2)。

空间复杂度:O(1)

稳定性：插入排序是稳定的排序算法，满足条件nums[j] > nums[j + 1]才发生交换，这个条件可以保证值相等的元素的相对位置不变

插入排序

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

1.算法描述

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）

2.动图展示

3.图解展示

4.代码实现


void Insert(int* a, int n)
{
	for (int i = 0; i < n - 1; i++) {
 
		int j = 0;
		int tmp = a[i + 1];
 
		for (j = i; j >= 0 && tmp < a[j]; j--) {
			a[j + 1] = a[j];
		}
		a[j + 1] = tmp;
	}
}

或者也可以这样写，这样写逻辑更清晰：


void Insert(int* a, int n)
{
	for (int i = 0; i < n - 1; i++) {
 
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0) {
			if (tmp < a[end]) {
				a[end + 1] = a[end];
				--end;
			}
			else {
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

5.复杂度分析

时间复杂度：O(n²)
空间复杂度：O(1)，只需要一个额外空间用于交换
稳定性：插入排序是稳定的排序算法，满足条件nums[j] > nums[j + 1]才发生交换，这个条件可以保证值相等的元素的相对位置不变

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

1.算法描述

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

2.动图展示

3.图解展示

或者：

4.代码实现


void ShellSort(int* a, int n) {
	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++) {
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0) {
				if (a[end] > tmp) {
					a[end + gap] = a[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			a[end + gap] = tmp;
	  }
 
	}
}

5.复杂度分析

1、时间复杂度：O(N^2)
希尔排序最坏的时间复杂度依然为 O ( N 2 )
但其能够有效改善直接插入排序序列无序且长度大时的大长度数列移位。希尔排序中对于增量序列的选择十分重要，直接影响到希尔排序的性能，本文使用的是希尔增量，还有 Hibbard 增量，时间复杂度为 O(N^1.5) 也可以认为是O ( N^log N)空间复杂度：O(1)
未借助其它辅助空间。

稳定性分析：
与直接插入排序不同，希尔排序中的分组插入可能导致顺序移位。

所以，插入排序是稳定的排序算法。

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

1.算法描述

① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点
② 依次将根节点与待排序序列的最后一个元素交换
③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列先将初始的R[0…n-1]建立成最大堆，此时是无序堆，而堆顶是最大元素。
再将堆顶R[0]和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1]，且满足R[0…n-2].keys ≤ R[n-1].key
由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
直到无序区只有一个元素为止。

2.动图展示

3.图解展示

1.预备知识：

堆的结构可以分为大根堆和小根堆，是一个完全二叉树，而堆排序是根据堆的这种数据结构设计的一种排序，下面先来看看什么是大根堆和小根堆

2.大根堆和小根堆：

性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆。如下图

对应成数组便是：

4.堆的一些基本性质

查找数组中某个数的父结点和左右孩子结点，比如已知索引为i的数，那么

1.父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）

2.左孩子索引：2*i+1

3.右孩子索引：2*i+2

所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质：

大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

小根堆：arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

5.堆的构造

将无序数组构造成一个大根堆（升序用大根堆，降序就用小根堆）

假设存在以下数组

主要思路：第一次保证0~0位置大根堆结构（废话），第二次保证0~1位置大根堆结构，第三次保证0~2位置大根堆结构...直到保证0~n-1位置大根堆结构（每次新插入的数据都与其父结点进行比较，如果插入的数比父结点大，则与父结点交换，否则一直向上交换，直到小于等于父结点，或者来到了顶端）

插入6的时候，6大于他的父结点3，即arr(1)>arr(0)，则交换；此时，保证了0~1位置是大根堆结构，如下图：

插入8的时候，8大于其父结点6，即arr(2)>arr(0),则交换；此时，保证了0~2位置是大根堆结构，如下图

插入5的时候，5大于其父结点3，则交换，交换之后，5又发现比8小，所以不交换；此时，保证了0~3位置大根堆结构，如下图

插入7的时候，7大于其父结点5，则交换，交换之后，7又发现比8小，所以不交换；此时整个数组已经是大根堆结构

此时，我们已经得到一个大根堆，下面将顶端的数与最后一位数交换，然后将剩余的数再构造成一个大根堆

此时最大数8已经来到末尾，则固定不动，后面只需要对顶端的数据进行操作即可，拿顶端的数与其左右孩子较大的数进行比较，如果顶端的数大于其左右孩子较大的数，则停止，如果顶端的数小于其左右孩子较大的数，则交换，然后继续与下面的孩子进行比较

下图中，5的左右孩子中，左孩子7比右孩子6大，则5与7进行比较，发现5<7，则交换；交换后，发现5已经大于他的左孩子，说明剩余的数已经构成大根堆，后面就是重复固定最大值，然后构造大根堆

如下图：顶端数7与末尾数3进行交换，固定好7，

剩余的数开始构造大根堆，然后顶端数与末尾数交换，固定最大值再构造大根堆，重复执行上面的操作，最终会得到有序数组

重点建堆的时间复杂度：因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

6.代码实现


void AdjustDown(int*a,int root,int n) {
	int parent = root;
	int child = 2 * parent + 1;//向下调整算法
	while (child < n) {
		if (child+1<n&&a[child] < a[child + 1]) {
			++child;
		}
		if (a[child] > a[parent]) {
			swap(a[child], a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else {
			break;
		}
 
	  }
}
 
void  HeapSort(int* a, int n) {
	for (int i = (n - 2) / 2; i >= 0; i--) {
		 AdjustDown(a, i, n);       
	}
	int end = n - 1;
	while (end>0) {
		swap(a[0], a[end]);
		AdjustDown(a, 0, end);
		end--;
	}
 
}

7.复杂度分析

时间复杂度：O（N*log N)

空间复杂度：O（1）

稳定性：不稳定

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零

1.算法描述

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕

2.动图展示

3.图解展示

4.代码实现


void SelectSort(int* a, int n) {
	int left = 0;
	int right = n - 1;
	int minIndex = left, maxIndex = left;
	while (left < right) {
 
 
		for (int i = left; i <= right; i++) {
			if (a[i] < a[minIndex]) {
				minIndex = i;
			}
			if (a[i] > a[maxIndex]) {
				maxIndex = i;
			}
		}
		
		swap(a[left], a[minIndex]);
		if (left == maxIndex) {//如果max和left位置重叠，修正一下
			maxIndex = minIndex;
		}
		swap(a[right], a[maxIndex]);
		left++;
		right--;
	}
}

5.复杂度

时间复杂度：O（N^2)

空间复杂度O（1）

稳定性：不稳定

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

1.算法简介

从数列中挑出一个元素，称为 "基准"（pivot）;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

2.动图展示

3.图解展示

挖坑法：

挖坑法：
1、定义begin和end分别指向数据的第一个元素和最后一个元素，找一个基准值key（一般三数取中法）,置array[begin]的位置上的值为基准值，并为第一个坑。
2、end从后往前走，找比key小的值，找到之后，将array[end]赋值给array[begin]，填充begin位置的坑，此时end位置为一个新的

3、begin从前往后走，找比key大的值，找到之后，将array[begin]赋值给array[end]，填充end位置的坑，此时begin位置为一个坑
4、此类方法依次填坑，当begin和end相遇，则循环结束，将key的值填最后一个坑。

上面这种种单趟排序的方法我们称为挖坑法

4.代码实现


int partition2(int* a, int left, int right) {
	int mid = GetMindIndex(a, left, right);//三数取中
	
	int key = a[left];
	swap(key, a[mid]);
	while (left < right) {
		while (left < right && a[right] >= key) {
			--right;
		}
		a[left] = a[right];
		while (left < right && a[left] <= key) {
			++left;
		}
		a[right] = a[left];
 
	}
	a[left] = key;
	return left;
}

三数取中代码：


int GetMindIndex(int* a, int left, int right) {
	int mid = (left + right) >> 1;
	if (a[left] < a[mid]) {
		if (a[mid] < a[right]) {
			return mid;
		}
		else if (a[left] > a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {
		if (a[mid] > a[right]) {
			return mid;
		}
		else if (a[left] < a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}

总代码：


int GetMindIndex(int* a, int left, int right) {//三数取中
	int mid = (left + right) >> 1;
	if (a[left] < a[mid]) {
		if (a[mid] < a[right]) {
			return mid;
		}
		else if (a[left] > a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {
		if (a[mid] > a[right]) {
			return mid;
		}
		else if (a[left] < a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}
 
、
 
int partition2(int* a, int left, int right) {//挖坑法
	int mid = GetMindIndex(a, left, right);
	
	int key = a[left];
	swap(key, a[mid]);
	while (left < right) {
		while (left < right && a[right] >= key) {
			--right;
		}
		a[left] = a[right];
		while (left < right && a[left] <= key) {
			++left;
		}
		a[right] = a[left];
 
	}
	a[left] = key;
	return left;
}
 
 
void QuickSort(int* a, int left, int right) {//快速排序
	if (left >= right)
		return;
	int mid = partition2(a, left, right);
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid + 1, right);
 
}

下面我们来看一下前后指针法：

前后指针法：

1、选择一个基准值key，定义两个指针prev和cur（prev指向pPcur的前一个位置）
2、当cur标记的元素比key小时，prev和cur同时走，当cur标记的元素比key大时，只有cur继续向前走（此时prev停下来），当cur走到标记的元素比key值小时，cur停下，prev向前走一步，此时交换arr[cur]和arr[prev],然后，cur继续往前走。
3、当cur走出界了，将prev位置的值与key交换。

对应动图：

对应代码实现：


int partition3(int* a, int left, int right) {
	int cur = left + 1;
	int prev = left;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur) {
			swap(a[cur], a[prev]);
		  }
		++cur;
	}
	swap(a[prev], a[key]);
	return prev;
}

总代码：


int GetMindIndex(int* a, int left, int right) {
	int mid = (left + right) >> 1;
	if (a[left] < a[mid]) {
		if (a[mid] < a[right]) {
			return mid;
		}
		else if (a[left] > a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {
		if (a[mid] > a[right]) {
			return mid;
		}
		else if (a[left] < a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}
 
 
 
 
int partition3(int* a, int left, int right) {
	int cur = left + 1;
	int prev = left;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur) {
			swap(a[cur], a[prev]);
		  }
		++cur;
	}
	swap(a[prev], a[key]);
	return prev;
}
 
 
 
 
void QuickSort(int* a, int left, int right) {
	if (left >= right)
		return;
	int mid = partition2(a, left, right);
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid + 1, right);
 
}

左右指针法

1、定义两个指针begin（指向首元素）和end（指向尾元素），找一个基准值key（一般三数取中法），置于序列的第一个元素，也就是begin的位置。
2、end从后往前走找比基准值小的元素（找到后也停下），begin从前往后走找比基准值key大的元素（找到后停下），
然后，交换arr[begin]和arr[end]，依次循环操作。
3、当begin与end相遇，将array[begin]或array[end]与基准值交换。

对应图解：

对应代码：


int partition(int* a, int start,int end) {
	int mid = GetMindIndex(a, start, end);
	int key = start;
	swap(a[key], a[mid]);
	while (start < end){
		while (start<end && a[end]>=a[key]) {
			--end;
		}
		while (start < end && a[start] <= a[key]) {
			++start;
		}
		swap(a[start], a[end]);
	 }
	swap(a[key], a[start]);
	return start;
}

代码汇总：


int GetMindIndex(int* a, int left, int right) {//三数取中
	int mid = (left + right) >> 1;
	if (a[left] < a[mid]) {
		if (a[mid] < a[right]) {
			return mid;
		}
		else if (a[left] > a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {
		if (a[mid] > a[right]) {
			return mid;
		}
		else if (a[left] < a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}
 
 
int partition(int* a, int start,int end) {//左右指针法
	int mid = GetMindIndex(a, start, end);
	int key = start;
	swap(a[key], a[mid]);
	while (start < end){
		while (start<end && a[end]>=a[key]) {
			--end;
		}
		while (start < end && a[start] <= a[key]) {
			++start;
		}
		swap(a[start], a[end]);
	 }
	swap(a[key], a[start]);
	return start;
}
 
 
void QuickSort(int* a, int left, int right) {
	if (left >= right)
		return;
	int mid = partition2(a, left, right);
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid + 1, right);
 
}

快速排序需要注意的是：

如果选取左边做key,并且使用的是左右指针法或者是挖坑法那么右边要先走才能保证结果的正确性


int partition2(int* a, int left, int right) {//挖坑法
	int mid = GetMindIndex(a, left, right);
	
	int key = a[left];
	swap(key, a[mid]);
	while (left < right) {
		while (left < right && a[right] >= key) {//这里一定要加等于否则有些情况会死循环
			--right;
		}
		a[left] = a[right];
		while (left < right && a[left] <= key) {//这里一定要加等于否则有些情况会死循环
			++left;
		}
		a[right] = a[left];
 
	}
	a[left] = key;
	return left;
}

挖坑法也是一样的要加等于如果不加等于在某些极端情况下会死循环

比如：

5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

那么它就会死循环！！！！！！！！！！

快速排序非递归

在数据结构中，即使递归能解决的，我们也有必要掌握非递归的方法。我们知道，堆空间比栈的空间大得多，当我们在栈中递归调函数，会增加栈的开销，栈帧会多。导致栈溢出程序崩溃。而在堆上递归调用函数，即使大的递归调用也不会使程序崩溃。这在安全方面就解决了栈溢出的问题。

递归就是自上而下，再自下而上。也就满足了我们数据结构中的栈。所以这里我们可以借助栈来实现非递归的快速排序。

对应代码实现：


 
int partition2(int* a, int left, int right) {
	int mid = GetMindIndex(a, left, right);
	
	int key = a[left];
	swap(key, a[mid]);
	while (left < right) {
		while (left < right && a[right] >= key) {
			--right;
		}
		a[left] = a[right];
		while (left < right && a[left] <= key) {
			++left;
		}
		a[right] = a[left];
 
	}
	a[left] = key;
	return left;
}
 
 
 
void QuickSortNonR(int* a, int n) {
	int right = n - 1;
	int left = 0;
	stack<int>ans;
	ans.push(right);
	ans.push(left);
	while (!ans.empty()) {
		int left = ans.top();
		ans.pop();
		int right = ans.top();
		ans.pop();
		int mid = partition(a, left, right);
		if (left + 1 < mid) {
			ans.push(mid - 1);
			ans.push(left);
		}
		if (mid + 1 < right) {
			ans.push(right);
			ans.push(mid + 1);
		}
	}
 
}

时间复杂度

归并排序：

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代；然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

1.算法分析

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾

2.动图展示

3.图解展示

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤

对应代码实现：


 
void _MerageSort(int* a, int* tmp , int left, int right) {
	if (left >= right)return;
	int mid = (left + right) >> 1;
	_MerageSort(a,tmp, left, mid);
	_MerageSort(a,tmp, mid + 1, right);
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {
			tmp[index++] = a[begin1++];
		}
		else {
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1<=end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[index++] = a[begin2++];
	}
	for (int i = left; i <= right; i++) {
		a[i] = tmp[i];
	}
 }
 
 
 
 
 
void MerageSort(int* a, int n) {
	
	int* tmp = new int[n];
	_MerageSort(a, tmp, 0, n - 1);
delete[] tmp;
 
}

非递归：

基本思路：看作是一颗倒过来的满二叉树，两两成对

实现思路

基本思路：

1、在State0初始状态时，两两合并，合并用到的算法是“合并有序的数组 merge sorted array”。即每次合并得到的都是有序的数组。

2、两两合并的规则是：将两个相同序列长度的序列进行合并，合并后的序列长度double。

第一趟合并（merge 1）调用了4次merge sorted array，得到了4个有序的数组："5, 8"，"3, 9"，"6, 4"，"1, 4"（每个合并后的序列长度为2）

第二趟合并（merge 2）调用了2次merge sorted array，得到了2个有序的数组："3, 5, 8, 9"，"1, 4, 6, 11''（每个合并后的序列长度为4）

3、按步骤1的思想以此类推，经过多次合并最终得到有序的数组，也就是State3。

可以看出经过一共3趟合并，最终得到有序的数组。

可以看出每趟要执行的合并次数不同，第一趟合并执行4次，第二趟合并执行2次，第三趟合并行1次。

看了上述的算法思想，可以知道算法可以设计成两层循环

外层循环遍历趟数
内层循环遍历合并次数

但是我们会发现排序元素的个数不一定是2^i

如图可知，一般数组元素的个数不一定是2i个。右边多出的"10, 7, 2"子树可以视作一般情况的情形。虽然元素个数不一定是2i个，但是任意元素个数的n，必然可以拆分成2j + m个元素的情形（数学条件不去深究）由图可知，特殊情形思想中的两两合并的规则不能满足一般情况的合并需求

图中灰色的箭头代表无需合并，因为找不到配对的元素。
图中墨蓝色的箭头代表两个长度不相等的元素也需要进行合

将上述的合并需求称为长短合并，容易知道长短合并仅存在1次或0次。

下面讨论的合并前/后的序列长度特指两两合并后得到的序列长度。

合并循环设计：

虽然一般情形与特殊情形的合并规则有差别（一般情形复杂），但是可以设计一个通用的合并趟数条件。

设置变量：记录每趟合并后序列的长度，其中k是趟次

通过观察发现：每次合并后序列的大小有规律，第一趟后合并的序列大小都是2，第二趟合并后的序列大小都是4，以此类推..
"10, 7, 2"这三个元素组合而成的序列长度虽然不满足上述的规律，但是并不影响趟数的计算。24 = 16 ≥ 11，4趟后循环结束。
可以设计成：if 最后合并后的序列长度≥实际元素的个数n，这时可以说明循环结束

对应代码实现：


void _Merge(int* a, int* tmp, int begin1, int end1, int begin2, int end2) {
	int i = begin1;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {
			tmp[index++] = a[begin1++];
		}
		else {
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1 <= end1) {
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[index++] = a[begin2++];
	}
 
	for (; i <= end2; i++) {
		a[i] = tmp[i];
	}
}
void mergeSort(int* a, int n) {
	int* tmp = new int[n];
	int gap = 1;
	while (gap < n) {
 
		for (int i = 0; i < n; i+=2*gap) {
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			if (begin2 >= n) {//说明已经排序完成
				break;
			}
 
			if (end2 >= n) {//修正区间
				end2 = n - 1;
			}
 
			_Merge(a, tmp, begin1, end1, begin2, end2);
 
		}
 
		gap *= 2;
	}
	delete[]tmp;
}