文章目录。

• 归并排序。
• • 合并排序的思想。
  • 实现单次排序。
  • 实现并购排序。
  • 实现非递归版本。
  • 特性总结。
• 计数排序。
• • 计数排序的思想。
  • 实现计数排序。
  • 特性总结。

归并排序。

合并排序（#xff08;MERGE-SORT）它是一种基于合并操作的有效排序算法，采用分治（Divide andConquer）一个非常典型的应用。合并已有序的子序列，获得完全有序的序列。也就是说，每个子序列都是有序的，然后使子序列段间有序。如果将两个有序表合并成有序表，称为二路归并。

合并排序的思想。

首先，打开一个长度与待排序数组相同的临时数组，用于存储并购操作后的数据。1.连续两分࿰将带排序的数据间隔c;直到范围内只有一个数据或范围不存在。每个子区间通过递归并，将归并序列写入临时数组，最后，从临时数组复制归并的内容回原数组。

实现单次排序。

首先，将两个范围内容的较小值写入tmp数组，以实现范围合并。当一个范围内的所有数组都写入࿰时c;然后将剩余区间的内容直接插入临时数组。最后，将临时数组内容复制回原数组，使用memcpy。

void。_MergeSort。(。int。*。arr。,int。begin。,int。end。,int。*。tmp。)。{ 。tmp。[。i。++]。=arr。[。begin2。++]。;}。//将归并的内容复制到原数组。memcpy。(。arr。 +begin。,tmp。 +begin。,(。end。 -。begin。 +1。)。*。sizeof。(。int。)。)。;}。

实现并购排序。

也就是说，在单次排序的基础上，递归划分间隔，直到区间不存在，才开始合并。当然，画递归展开图也可以帮助我们理解递归并排序的实现。

实现非递归版本。

实现思路如下：将递归转化为非递归󿀌事实上，类似于斐波那契数列的递归改非递归问题。但是，我们需要从11归并到22归并到44归并这里的归并思路。首先，首先开辟临时数组。然后，数据将从1开始合并。最后，单次排序思路如上，这里不赘述。

因为数据不可能每次都是完美的二分，因此，我们需要讨论范围。begin1肯定不会越界。end1󿀌begin2，end2都有越界的可能。这里我们已经以多组复制的形式进行了。当end1和begin2越界时，#xff0c;我们直接跳出循环󿀌不做处理。当end2越界时，#xff0c;将end2修改为数组长度-1的下标值。

下面我将以每组合并然后复制的形式演示代码。

下面我打印出每组间隔的值，方便观看。

这是通过多组合并后复制进行的。当然，这不是唯一的方式 ，下面我就来介绍一下如何处理梭哈拷贝的边界问题。

因为是梭哈复制，因此，有必要修改越界区间。然后我把修改后的值打出来看。

特性总结。

1、合并排序的时间复杂度为O(N*LogN)，空间复杂度为O(N)。
二、合并排序可以解决磁盘中的外排序问题。因为有时在大量数据下排序，可能无法容纳内存󿀌只能放在磁盘中进行排序。文件系统可以从递归的角度进行归并排序。类似的快速排序和堆排序无法达到这种效果。因为文件系统属于树形结构，不适合数组存储堆和左右指针遍历数组的快速排序。
合并排序是一个稳定的排序。

计数排序。

计数排序与前面介绍的有本质区别。属于非比较排序的一种。我们之前介绍的都是比较排序，比较即值的大小。

计数排序的思想。

计数࿰根据数组最大值和最小值的范围进行相对映射c;然后遍历技术数组，将相对映射值重写回原数组，以达到排序功能。

实现计数排序。

首先，最大值和最小值，根据最大值和最小值计算出数组的值范围󿀌最大值-最小值-43;1数组计数，计数࿰是根据值的相对映射进行的c;然后通过技术数组，将相对映射值重写回原数组，以达到排序功能。

特性总结。

特征总结。
1、计数排序是一种只适用于排序数据范围集中的整形数据。应用场景相对有限。绝对映射不适合，因为在有负整数的情况下无法计数。和更大的数值，在数值间差小的情况下，空间损失过大。因此，采用相对映射比较合适。