【算法】八种常见排序算法

        所谓排序，就是一种使一串数据记录，按照其中的某个或某些关键字的大小，递增或递减地组织起来的操作。

        从数据的存储上，它被分为内部排序和外部排序。内部排序，是数据元素全部放在内存中的排序。 外部排序，是数据元素太多的时候不能同时放在内存中，根据排序过程的要求又不能在内外存之间移动数据的排序。

        稳定性是排序最重要的评价方式。假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

        排序在日常生活的方方面面都发挥着作用。例如，我们在手机上进行外卖点餐，按照距离、评分等因素来列出店家的表单以供选择；我们在网购时根据金额、销量、评价等来筛选适合自己的心仪目标；学生的考试成绩需要降序地排名，知道第一名、第二名等名次，以此来录取不同分段的学生进入大学......

       从排序方式上，排序算法一般被分为比较排序和非比较排序。从比较排序的内容上，它一般被分为插入排序、选择排序、交换排序和归并排序，其中，它们每一种又有更细致的分类。

目录

一、比较排序

1、插入排序

· 直接插入排序

· 希尔排序

2、选择排序

· 直接选择排序

· 堆排序

3、交换排序

· 冒泡排序

· 快速排序

1）Hoare版本

2）挖坑法

3）前后指针法

4）非递归版本

4、归并排序

1）递归版本

2）非递归版本

 二、非比较排序

· 计数排序

【Tips】排序算法的复杂度&稳定性总结

---

【Tips】排序的学习法门：

1. 排序一般是分为多步多趟的，将单趟的排序理清楚，就容易推导和理解整趟排序；
2. 体会需求的流程逻辑转化为代码的运行逻辑
3. 调试

一、比较排序

1、插入排序

· 直接插入排序

        当插入第 i (i >= 1)个元素时，前面的 array[ 0 ], array[ 1 ],…, array[ i - 1 ]已经排好序，此时用array[ i ]的排序码与array[ i - 1 ],array[ i - 2 ],…的排序码顺序进行比较，找到插入位置即将array[ i ]插入，然后原来位置上的元素顺序后移。

        （这里默认升序排列）

        从第二个数据开始，依次与其前面的数据分别比较，比它大，就跟它交换位置，直到遇到比它小的数据，然后又从第三个数据开始进行比较，以此类推，直到数据整体完成排序。 

void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)                                                   
	{
		int end = i-1;     //下标指针，这样写是为了方便控制边界
		int tmp = a[i];    //将tmp插入到[0,end]中并保持有序
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];    //依次将数据往后挪动，直到空出插入数据的目标位置
				--end;
			}
			else
			{
				break;
			}
		}
 
		//将tmp的值放在end+1的位置
		//即放在最后一个移动的数据之前
		a[end + 1] = tmp;
	}
}

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)(最坏情况（逆序/降序）：o(n^2);最好情况（顺序/升序）：o(n))
3. 空间复杂度：O(1)
4. 稳定性：稳定

· 希尔排序

        希尔排序是对直接插入排序的优化，又称缩小增量法，它的基本思想是：先选定一个整数，把待排序文件中所有记录分成n个组，所有距离为n的记录分在同一组内，并对每一组内的记录进行排序。然后，取n-1，重复上述分组和排序的工作，直到n=1，所有记录在统一组内排好序。

 （这里默认升序排列）

 希尔排序的基本步骤：

• step1. 预排序（分组插排） - 目标：数组接近有序

        例如：

        间隔为gap的分为一组，然后堆每组数据进行插入排序。对于a[]={9,1,2,5,7,4,8,6,3,5}，假设gap==3（一般来说，gap的值也是分组的组数），则9、5、8、5为第一组，1、7、6为第二组，2、4、3为第三组。对每组数据分别进行插入排序，则第一组结果为5、5、8、9，第二组为1、6、7，第三组为2、3、4此时，a[]={5,1,2,5,6,3,8,7,4,9}。

• step2. 直接插入排序

        对此时的a[]={5,1,2,5,6,3,8,7,4,9}整体进行插入排序

Q：gap为多少合适？
          - gap越大，跳得越快，但越不接近有序
          - gap越小，跳得越慢，但越接近有序
方案：让gap一直变化

void ShellSort(int* a, int n)
{
 
	// gap>1 - 预排序
	// gap==1 - 直接插入排序
 
	int gap = n;
	while (gap > 1)
	{
		//gap /= 2;           //gap一直自除2，最终值一定为1，此时以下代码相当于从预排序变为了直接插入排序
		gap = gap / 3 + 1;    //+1保证最后一次/3后值一定是1
 
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;            //一前
			int tmp = a[i + gap];   //一后
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
 
			a[end + gap] = tmp;    //类比直接插入排序的“a[end + 1] = tmp;”
		}
	}
}

 希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时，进行的都是预排序，目的是让数组更接近于有序；当gap == 1时，数组已经接近有序，此时进行直接插入排序会非常快（整体而言可以达到优化的效果）；
3. 希尔排序的时间复杂度并不好计算，实际中gap的取值方法很多，导致很难去计算，因此在许多教材中给出的希尔排序的时间复杂度都不固定：

《数据结构(C语言版)》（严蔚敏）

《数据结构-用面相对象方法与C++描述》（殷人昆）

        因为上文代码中的gap是按照Knuth提出的方式取值的，且Knuth进行了大量的试验统计，具有足够信服力，故本博客按照：O(N^1.25)到O(1.6 * N^1.25)（约为O(N^1.3)）来算。

2、选择排序

· 直接选择排序

        在元素集合 array[ i ] ~ array[ n - 1 ] 中选择关键码最大(或小)的数据元素,若它不是这组元素中的最后一个(或第一个)元素，则将它与这组元素中的最后一个（或第一个）元素交换，在剩余的array[ i ] ~array[ n - 2 ]（array[ i + 1 ]--array[ n - 1 ]）集合中，重复上述步骤，直到集合剩余1个元素

         （这里默认升序排列） 

        每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到待排序的数据元素全部排完。

void Swap(int* pa,int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
        //重置最小值和最大值
		int mini = left, maxi = left;
        
        //往右依次找小找大
		for (int i = left + 1; i <= right; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
 
        //找到后与左边界交换
		Swap(&a[left], &a[mini]);
 
        //修正
		//如果与左边界交换后，left和maxi重叠了，就将mini（此时最大值的下标）修正给maxi，再交换maxi与右边界
		if (left == maxi)
		{
			maxi = mini;
		}
 
        //与左边界交换后，交换maxi与右边界
		Swap(&a[right], &a[maxi]);
        
        //继续找下一组
		left++; right--;
	}
 
}

直接选择排序的特性总结：

1. 虽然容易实现，但面对各类情况，整体效率不高，故实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

· 堆排序

        堆排序是指利用堆积树的顺序结构（堆）所设计的一种排序算法，通过堆来进行选择数据，是间接实现的选择排序。一般来说，排升序要建大堆，排降序要建小堆。（关于数据结构堆的更多解释，详见【数据结构】树之二叉树）

堆排序的基本步骤：

1. 建堆（升序 - 建大堆、降序 - 建小堆）；
2. 利用堆的删根来进行排序。

void Swap(int* pa,int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
 
// 利用堆的向下调整，使用前提为左右子树都是大堆或小堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 选出左右孩子中大的那一个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
 
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	// 建堆 -- 向下调整建大堆 -- O(N)
	for (int i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
 
    //利用堆的删根来排序 -- o（N*logN）
	//一次交换后，将已交换的最大值从堆内排除，选出堆内剩余最大的，再进行下一次交换
	int end = n - 1;    //end既是堆内（数组）最后一个数据的下标，也是放在end之前的数据的个数
	while (end > 0)
	{
		Swap(&a[end], &a[0]);  //交换数组的尾部数据和头部数据
		AdjustDown(a, end, 0); //再次向下调整，选出最大值放在根部
		--end;
	}
}

 堆排序的特性总结：

1. 用来选数，效率极高。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

3、交换排序

        所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。交换排序的特点是，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的头部移动。

· 冒泡排序

        从序列的第一个数据开始，与其下一个数据（第二个数据）比较，若第一个数据（前一个数据）大于第二个数据（后一个数据），则将两者进行交换，然后继续此时的第二个和第三个数据的比较，直至将最大的一个数据移至尾部，这个过程被称为单趟的冒泡排序。

        第一趟排序完成之后，继续下一趟排序（第二趟排序）。第二趟排序从序列的第二个数据开始（将上一趟排序的起始位置剔除后的第一个数据），重复与第一趟排序同样的过程。接着，是第三趟、第四趟......直至最后一趟排序完成，使序列整体有序。

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		bool exchange = false;
		for (int i = 1; i < n-j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = true;
			}
		}
 
		if (exchange == false)    //如果单趟中没发生交换，则说明已有序，直接结束冒泡排序
		{
			break;
		}
	}
}

 冒泡排序的特性总结：

1. 是一种非常容易理解和实现的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

· 快速排序

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的任一元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

        将区间按照基准值划分为左右两半部分的常见方式有：

1）Hoare版本

        选出一个基准值（key），把它放到正确的位置（即最终排好序时要在的位置）。一般选择数组的头部数据或尾部数据作为基准值。

        如图：比6小的放左边，比6大的放右边。right下标指针（图为R小人）从数组末尾向头找小的，left下标指针（图为L小人）从数组开头向尾找大的，两者都找到后，交换两者所在位置的值；当 left == right 时，则将当前位置与基准值交换。

【补】快速排序的优化：

        法1：三数取中法选基准值key

        法2：递归到小的子区间时，可以考虑使用插入排序

【ps】左边作key，right先走，相遇位置的值一定比基准值小，或相遇位置就是key的位置
       Q：为什么相遇位置的值一定比基准值小，或者相遇位置就是key？
        A：第一种情况：R找到小，但L找大没找到，这时L会遇到R；第二种情况：R找小没找到，直接遇到L，此时要么是一个比key小的位置，要么直接到key。类似地，若右端作key，则让L先走，相遇位置值就比key大。

//三数取中
int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;    //先取[left,right]的中间下标
 
    //然后对左值、中间值、右值两两比较验证
    //情况1：左值小于中间值
    // 右值在右边：a[left] < a[mid] < a[right];
    // 右值在左边：a[right] < a[left] < a[mid];
    // 右值在中间：a[left] < a[right] < a[mid];
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])    //中间值大于左值，且小于右值，
		{
			return mid;           //中值就是中间值，故返回中间值的下标
		}
		else if (a[left] > a[right])    //中间值大于左值，且左值大于右值，
		{
			return left;                //中值就是左值，故返回左值的下标
		}
		else                //中间值大于左值，且大于右值，
		{
			return right;   //中值就是右值，故返回右值的下标
		}
	}
    //情况2：左值大于（等于）中值
    // 右值在左边：a[right] < a[mid] < a[left]
    // 右值在右边：a[mid] < a[left] < a[right]
    // 右值在中间：a[mid] < a[right] < a[left]
	else    //a[left] >= a[mid]
	{
		if (a[mid] > a[right])        //与上同理
		{
			return mid;
		}
		else if (a[left] < a[right])    //与上同理
		{
			return left;
		}
		else                //与上同理
		{
			return right;
		}
	}
}
 
void QuickSort_Hoare(int* a, int left, int right)
{
    
    //递归出不存在的区间，就结束递归（详见以下代码）   
	if (left >= right)
		return;
 
    
    //单趟的快速排序
 
	int begin = left, end = right;    //先记录一下起始的left和right（数组头部和数组尾部）
 
	//随机选key（提速）
	//int randi = left + (rand() % (right - left));
	//Swap(&a[left], &a[randi]);
 
	//三数取中值（提速x2 ）
	int midi = GetMidNumi(a, left, right);    //记录中值的下标
	if (midi != left)
	{
		Swap(&a[left], &a[midi]);    //将中值换到数组头部（最左边）
	}
 
	int keyi = left;    //将序列的头部选为基准值key的下标
	while (left < right)
	{
		//right先走，找小
		while (left < right && a[right] > a[keyi])
		{
			right--;
		}
 
		//left后走，找大
		while (left < right && a[left] < a[keyi])
		{
			left++;
		}        
    
        //注：条件“left < right”在找大和找小的过程中都是不可或缺的，
        //因为left>=right后两者会无休止地走下去，会造成死循环
 
        //找到后，交换此时left和right指向的值
		Swap(&a[left], &a[right]);
	}
 
    //key的左右两边分好后，将此时的left指向的值跟key交换
	Swap(&a[keyi], &a[left]);
       
    //以上就是单趟的快速排序
 
    //单趟排序后，原序列被分为以下区间：
	// [begin, keyi-1] keyi [keyi+1, end] （单趟排序后，keyi还指向原先的基准值key，而不是指向划分两个区间的中间值，此时的left和right才是，故需重置keyi）
    
    //重置keyi下标的值
    //此时单趟排序后的left（或right）即为将数据划分为两个区间的真实keyi
    keyi = left;
 
    //然后继续，分别递归进入[begin, keyi-1]区间和[keyi+1, end]区间进行下一趟排序
	QuickSort_Hoare(a, begin, keyi - 1);
	QuickSort_Hoare(a, keyi + 1, end);
 
    //直到出现不存在的区间（left>=right），递归结束
}

2）挖坑法

        挖坑法是后人基于Hoare版本实现的改进版。

        拿走key的值，留下一个坑位。right下标指针找小，找到后将值填到该坑位上，并留下一个新坑位；left下标指针找大，找到后将值填到新坑位上，且再留下一个坑，以此往复。
直到left与right相遇，就将key的值填到 left == right 的坑位。 

//三数取中
int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else    //a[left] >= a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
 
void QuickSort_Dig(int* a, int left, int right)
{
	if (left >= right)
		return;
 
	int begin = left, end = right;
	
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
	{
		Swap(&a[left], &a[midi]);
	}
 
	int key = a[left];    //取基准值
	int hole = left;      //取坑位
	while (left < right)
	{
		//right找小
		while (left<right && a[right] > key )
		{
			right--;
		}
        //找到后，将找到的小值放到坑位上，
		a[hole] = a[right];    
        //并留下一个新的坑位
		hole = right;
 
		//left找大
		while (left < right && a[left] < key )
		{
			left++;
		}
        //找到后，将找到的小值放到坑位上，
		a[hole] = a[left];
        //并留下一个新的坑位
		hole = left;
	}
    //调整结束后，将基准值放到此时的坑位上
	a[hole] = key;
 
    //递归由key（hole坑位）分割的左右区间，重复以上的单趟排序，直至数组整体有序
    // [begin, hole-1] hole [hole+1, end] 
	QuickSort_Dig(a, begin, hole - 1);
	QuickSort_Dig(a, hole + 1, end);
}

3）前后指针法

        对于前指针prev（左）、后指针cur（右）、基准值key（数组头部），若cur找到比key小的值，则++prev，cur与prev位置的值交换；若cur找到比key大的值，则++cur。相当于把比key大的值翻转到右边（大的值往右边运），比key小的值翻转到左边（把小的值往左边运）。

【ps】prev要么紧跟cur（即prev的下一个位置就是cur/prev紧跟在比key大的值后面），要么跟cur中间间隔着一段由比key大的值组成的区间。

//三数取中
int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else    //a[left] >= a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
 
//单趟的前后指针法
int PartSort(int* a, int left, int right)
{
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);
 
	int prev = left, cur = left + 1;    //前指针 后指针
	int keyi = left;                    //基准值的下标指针
	while (cur<=right)    //循环条件：后指针未到达数组尾部
	{
        //cur找到比key小的值，就使prev向后移动一步
        //且若两者不重合/相遇，就交换两者指向的值
		if (a[cur] < a[keyi] && ++prev!=cur)
		{
			Swap(&a[prev], &a[cur]);
		}
 
        //无论如何，cur始终向后移动找值		
		cur++;        
	}
 
    //数组调整完一趟后，交换当时prev和基准值
	Swap(&a[prev], &a[keyi]);
 
	keyi = prev;
	return keyi;
}
 
void QuickSort_Pointer(int* a, int left, int right)
{
	if (left >= right)
		return;
 
	//对数据少的小区间进行效率优化
    //小区间直接使用直接插入排序
	if ((right - left + 1) > 10)
	{
        //接受单趟调整完后的基准值下标
		int keyi = PartSort(a, left, right);    
 
        //调整完后的基准值下标将数组划分为两个区间：
        // [left, keyi-1] keyi [keyi+1, right]
        //继续分别对这两个区间递归进行调整，直至数组整体有序
		QuickSort_Pointer(a, left, keyi - 1);
		QuickSort_Pointer(a, keyi + 1, right);
	}
	else    //小区间就直接使用直接插入排序
	{
		InsertSort(a + left, right - left + 1); 
	}
	
}

4）非递归版本

        用栈实现（关于栈的完整代码和更多解释，详见【数据结构】线性表之栈和队列）。

        先将所有数据组成的区间端点端点值入栈，然后，每次从栈里取一段区间的端点值（首次是所有数据组成的区间）进行单趟的排序；单趟排序中，被划分的子区间分别入栈（因为栈的特点是后进先出，所以右先入左后入才能使序列跟入栈前保持一致）；直到划分的子区间只有一个值或子区间不存在就不再入栈。

#include"Stack.h"
 
//三数取中
int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else    //a[left] >= a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
 
//单趟的排序
int PartSort(int* a, int left, int right)
{
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);
 
	int prev = left, cur = left + 1;    
	int keyi = left;                   
	while (cur<=right)  
	{
		if (a[cur] < a[keyi] && ++prev!=cur)
		{
			Swap(&a[prev], &a[cur]);
		}
	
		cur++;        
	}
 
	Swap(&a[prev], &a[keyi]);
 
	keyi = prev;
	return keyi;
}
 
void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
    //先入右值（尾部的值），再入左值（头部的值）
	STPush(&st, right);
	STPush(&st, left);
 
	while (!STEmpty(&st))
	{
		//先出左值，再出右值
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);
        
        //进行单趟的排序，且记录排序后的基准值下标
		int keyi = PartSort(a, begin, end); 
 
		//分出区间：[begin,keyi-1] keyi [keyi+1, end]
        //并分别入栈
		if (keyi + 1 < end)    //先入右区间
		{
			STPush(&st, end);    //先入右值
			STPush(&st, keyi+1); //再入左值
		}
		if (begin < keyi - 1)    //再入左区间
		{
			STPush(&st, keyi - 1);    //先入右值
			STPush(&st, begin);       //再入左值
		}
	}
 
	STDestory(&st);
}

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

【补】时间复杂度为O(N*logN)的推导

4、归并排序

        归并排序是建立在归并操作上的一种排序算法,采用了分治法中一个非常典型的应用。先从待排序的序列中分出多个子序列，使每个子序列有序，然后，将已有序的子序列合并，得到整体有序的序列。故实现归并排序的基本步骤即为：先分解，再归并。将两个有序表合并成一个有序表的操作，称为二路归并。

1）递归版本

        将待排序的序列不断二分（这个过程由递归实现），直至二分的结果为单个数据（递归结束，准备开始返回），然后将从同一组中分出的两个数据进行比较，按大小顺序合并为一个有序（升序）区间。
        而对于两个有序区间的归并，开辟一个新的临时数组，然后将对两个有序区间中相同下标位置的值划为一组，进行比较，选出较小的值先尾插到临时数组，再将另一个值尾插到临时数组。重复这个过程，一直归并出整体有序的待排序序列。

//归并排序的子函数
void _MergeSort(int* a, int begin, int end, int* tmp) //tmp为临时数组
{
	if (begin >= end)    //划分的区间的左右下标重合或交错，则递归结束，开始返回
		return;
 
	int mid = (begin + end) / 2;    //取中间下标为划分区间的基准：[begin, mid] [mid+1,end]
 
     
    //[begin, mid] [mid+1,end] 划分的子区间递归排序
 
	_MergeSort(a, begin, mid, tmp);      //左区间
	_MergeSort(a, mid + 1, end, tmp);    //右区间
 
 
	// [begin, mid] [mid+1,end] 归并
 
	int begin1 = begin, end1 = mid;    //左区间
	int begin2 = mid + 1, end2 = end;  //右区间
 
    //依次比较两个区间相同下标位置的值，并按序放入临时数组
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
 
	//比较完后，还剩有值的区间继续归并
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
 
    //归并完后，将临时数组中有序的数据拷贝回原数组
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
 
//归并排序的主函数
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);    //开辟一个临时数组
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		return;
	}
 
	_MergeSort(a, 0, n - 1, tmp);    //进行归并排序
    
	free(tmp);    //归并整体完成后，释放临时数组
}

2）非递归版本

        通过循环实现。将从同一组中分出的两个数据进行比较，按大小（升序）合并为一个有序区间。

        将待排序的序列不断二分，直至二分的结果为单个数据，接着，将从同一组中分出的两个数据进行比较，按大小顺序一一归并为一个有序（升序）区间；归并后，重新排序，再对有序区间进行二二归并（每个有序区间有两个数据），然后是四四归并（每个有序区间有四个数据）......以此类推，直至待排序的序列整体有序。

        而对于两个有序区间的归并，同样要开辟一个新的临时数组来存排好序的数据，最后，将排好序的序列整体拷贝回原数组。

        【ps】这个写法最头疼的地方在于边界控制。 （例如，以下标红的区间涉及越界） 

void MergeSortNonR(int* a, int n)
{
    //开辟临时数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		return;
	}
 
	//（单趟）一一归并
	int gap = 1;    //gap是归并过程中，每组数据的个数
	while (gap < n)
	{		
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [begin1,end1][begin2, end2]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
 
            //关于边界控制的讨论：
			
			//printf("[%d,%d] [%d,%d] ", begin1, end1, begin2, end2);    //可以通过打印，显性地查看内存越界情况
			复杂问题分解为简单问题 => 分类讨论处理
            //
			1.end1越界了（则后面都越界了）怎么办？ - 不归并了
			2.end1没越界，begin2越界怎么办？ - 也不归并了
			3.end1、begin2没有越界，end2越界了怎么办？ - 修正end2到n-1内，然后继续归并
			
 
            修正边界
            法1：归并完全部拷贝 
			//if (end1 >= n)    //end1越界了
			//{
			//	//修正第一个区间
			//	end1 = n - 1;
			//	//把第二个区间修正为一个不存在的区间，迫使其不进入循环进行归并
			//	begin2 = n;
			//	end2 = n - 1;
			//}
			//else if (begin2 >= n)    //end1没越界，begin2越界了
			//{
			//	//把第二个区间修正为一个不存在的区间，使其不归并
			//	begin2 = n;
			//	end2 = n - 1;
			//}
			//else if (end2 >= n)  //end1、begin2没有越界，end2越界了  
            //有可能不越界，故都写else if而不写else
			//{
			//	//修正第二个区间
			//	end2 = n - 1;
			//}
			//printf("修正后：[%d,%d] [%d,%d] ", begin1, end1, begin2, end2);
 
 
            //修正边界
			//法2：归并一部分，拷贝一部分
			if (end1 >= n || begin2 >= n)
			{
				//第一个区间或第二个区间越界就不拷贝
				break;
			}
			if (end2 >= n)
			{
				//第二个区间越界就修正区间边界end2
				end2 = n - 1;
			}
            
            //依次比较两个区间相同下标位置的值，并按序放入临时数组
			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
 
 
			//没走完的区间继续归并
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
 
			//归并一部分，拷贝一部分
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
 
		//归并完了全部拷贝
		//但可能发生越界,故须控制边界（见上，法1）
		//memcpy(a, tmp, sizeof(int) * n);
 
		//一一归并 => 二二归并 => 四四归并 => ...
		gap *= 2;
	}
 
	free(tmp);
}

        去掉部分注释后的代码： 

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail\n");
		return;
	}
 
	//（单趟）一一归并
	int gap = 1;    
	while (gap < n)
	{		
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [begin1,end1][begin2, end2]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
            //修正边界
			//归并一部分，拷贝一部分
			if (end1 >= n || begin2 >= n)
			{
				//第一个区间或第二个区间越界就不拷贝
				break;
			}
			if (end2 >= n)
			{
				//第二个区间越界就修正区间边界end2
				end2 = n - 1;
			}
            
            //依次比较两个区间相同下标位置的值，并按序放入临时数组
			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
 
			//没走完的区间继续归并
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
 
			//归并一部分，拷贝一部分
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
 
 
		//一一归并 => 二二归并 => 四四归并 => ...
		gap *= 2;
	}
 
	free(tmp);
}

归并排序的特性总结：

1. 归并的缺点在于空间损耗较大，而实际中它解决的更多是在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

 二、非比较排序

        常见的非比较排序有计数排序、基数排序、桶排序等。 一般来说，计数排序的实用性更高。

· 计数排序

        计数排序的作用是，按照大小顺序排列每个数据，并保留每个数据重复出现的次数。它又称为鸽巢原理，是对哈希直接定址法的变形应用。实现它的基本步骤为：1. 统计相同元素出现次数；2. 根据统计的结果将序列回收到原来的序列中。

【Tips】统计每个数据出现的次数：
        1.为每个数据开辟一个坑位（计数数组），初始计数为0，每个数据出现一次则+1（遍历一遍原数组,o(N)）；
        2.对计数进行排序（遍历一遍计数数组，o(range)）。

void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 1; i < n; i++)
	{
		//找最大
		if (a[i] > max)
		{
			max = a[i];
		}
		//找最小
		if (a[i] < min)
		{
			min = a[i];
		}
	}
	//算范围
	int range = max - min + 1;
	//开计数数组
	int* countA = (int*)malloc(sizeof(int) * range);
	if (countA == NULL)
	{
		perror("malloc fail");
		return;
	}
	//初始化计数数组
	memset(countA, 0, sizeof(int) * range);
 
	//计数
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;    //通过相对位置映射计数（这是一种哈希的思想）
	}
 
	//排序，并覆盖原数组
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		//遍历计数数组
		while (countA[i]--)
		{
			//用数据数量的有序序列对应的数据，覆盖原数组
			a[j++] = i + min;    //countA[i]记录了某一数据出现的次数，countA[i]出现几次，就往原数组中写几个对应的值
            //i + min相当于还原出原数据
		}
	}
 
	free(countA);
}

计数排序的特性总结：

1. 适合范围集中且范围不大的整型数组，不适合范围分散或非整型（字符串、浮点数等）的数组；
2. 时间复杂度：o(N+range)；
3. 空间复杂度：o(range)；
4. 稳定性：稳定。

【Tips】排序算法的复杂度&稳定性总结