【数据结构】排序

1.排序的概念及其运用

1.1排序的概念

排序：指的是将一组数据（通常是一个列表、数组或任何有限集合）按照某种特定的顺序重新排列的过程。这个特定的顺序可以是升序（从小到大）、降序（从大到小）或者根据自定义的规则进行排序。

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

比较排序：通过比较元素的值来决定它们的顺序，如冒泡排序、选择排序、插入排序、归并排序、快速排序等。

非比较排序：不直接比较元素的值，而是通过元素的某些属性或分布来进行排序，如计数排序、桶排序、基数排序等。这些算法通常在某些特定条件下（如数据范围已知或分布均匀）表现出更高的效率。

1.2排序的应用

信息检索 ：在搜索引擎中，排序是必不可少的功能。通过对搜索结果进行排序，用户可以更快地找到最相关、最有价值的信息。

文件整理 ：在日常生活和工作中，我们经常需要对文件、图片、视频等进行排序，以便更高效地管理和查找。

商品销售排序：电商平台可以根据商品的销量、评价等信息进行排序，以便向用户推荐最受欢迎的商品。

1.3常见的排序算法

2.常见的算法排序实现 （升序举例）

2.1冒泡排序 

单趟：两两比较，将最大的数换到数组的最后面

全程：除去已完成单趟排序的元素，继续两两比较 ，直到已完成单趟排序的元素 == 数组总元素

冒泡排序比较简单，它只有教学意义，在实践中无意义，因它为太慢了 O(N²)

实现：

void MaoPaoPaiXu(int* a, int n) {int flag = 0;//优化，让数组在有序时，时间复杂度为O(N)for (int j = 0; j < n; j++){for (int i = 1; i < n - j; i++)//一趟{if (a[i] < a[i - 1]){JiaoHuan(&a[i], &a[i - 1]);flag = 1;}}if (flag == 0)break;}
}

2.2简单选择排序 

单趟：遍历一遍数组，选出最小的数，放至数组前面

全程：重复单趟的操作，直至数组有序

优化：单趟选出最小和最大的数，数组头部尾部

选择排序在优化后也是一个经典的O(N²)算法，非常慢，也没有教学意义

实现：

void XuanZhePaiXu(int* a, int n) {int begin = 0;//排序完成的下一个位置int end = n - 1;while (begin < end){int min = begin, max = begin;for (int i = begin; i < end; i++){if (a[i] < a[min])min = i;if (a[i] > a[max])max = i;}JiaoHuan(&a[min], &a[begin]);if (begin == max)//如果max的位置与begig相同，当mini的数据换到begin时//原先的max的数据已经被换到mini的位置了，要将max的位置更新一下max = min;JiaoHuan(&a[max],&a[end]);begin++;end--;}}

2.3直接插入排序

插入排序的思想非常简单：

单趟：把一个需要比较的数据与前面已经有序的数据进行比较，将它插入到前面比它小后面比它大的位置

全程：重复单趟操作，直至所有数据都完成单趟插入排序

插入排序的单趟与我们在整理扑克牌的时候很相似

 实现：

void ChaRuPaiXu(int* a, int n) {for (int i = 0; i < n - 1; i++)//i控制 end 的下标{//认为前[0,end]的数据是有序的，end + 1位置开始插入int end = i;int temp = a[end + 1];while (end >= 0){if (a[end] > temp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = temp;}
}

继续条件 i < n -1

2.4希尔排序 

希尔排序是由唐纳德·希尔通过插入排序改造而成的，希尔发现，插入排序的思想是一个好思想，但是插入排序有一个硬伤 ： 当遇到待排序的数据距离它该所处的位置较远时，那么就需要更多的时间将它放至正确位置，例如：

如何解决：将 n个数分成 gap 组先去进行基础的插入排序，这里我们假设gap是3，分成3组进行插入排序

第一组进行排序：

达到的效果：

当一个数据距离正确的位置较远时，通过先分组后排序的方法，可以让这个数更快的达到正确的位置。

预排序：

对整个数组数据进行先分组在排序，这样的处理方式我们也称为 ———— 预排序，而预排序随着gap的逐步减小，数组的有序性逐渐增强，这为后续的排序操作（尤其是在增量较小或接近1时）提供了更好的基础。

随着gap的值不断的缩小，数组也会更加接近有序，当gap == 1 时，它所执行的操作就与普通的插入排序一致了，这时数组将变的有序

实现：

在进行实现之前还有一个小问题，gap该如何取值？

初始gap的选取：

• Shell原始方法：Shell最初提出的方法是将gap初始化为数组长度n的一半，即gap = n / 2，然后每次将gap减半，直到gap为1。
• Knuth方法：Donald Knuth提出另一种方法，将gap初始化为n / 3 + 1，然后每次也进行类似的减小操作，直至gap为1。这种方法在某些情况下可能比Shell原始方法效率更高。

gap的减小方式：

• 减半法：最常见的减小方式是每次将gap除以2，即gap = gap / 2。这种方法简单直接，但可能不是最优的。
• Knuth递减法：如上文所述，Knuth建议使用gap = gap / 3 + 1的方式减小gap，这种方法在某些情况下可以产生更好的排序效果。

这里我们选取Kunth选取gap的方式来实现我们的希尔排序

void XiErPaiXu(int* a, int n) {int gap = n / 3 + 1;  //gap的初始取值while (gap > 1){gap = gap / 3 + 1;//gap自身调整，+ 1 是为了让最后一次循环只有一组（gap == 1）for (int j = 0; j < gap; j++)//gap等于某个值的整体循环{for (int i = 0; i < n - gap; i += gap) //一组的插入排序{int end = i;int temp = a[end + gap];while (end >= 0){if (a[end] > temp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}}	}}

void XiErPaiXu(int* a, int n) {int gap = n / 3 + 1;//gap初始取值while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++)//每次循环都是不同的组
//先是第一组第一个 -- 第二组第一个 ---- 第一组第二个......以此类推{int end = i;int temp = a[end + gap];while (end >= 0){if (a[end] > temp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}}}

分成gap组后的继续条件 i < n - gap

 在 n - 4结束后，这一gap组的排序就完成了，所以它的继续条件是 i < n -gap(gap == 3这一组)

想一下，如果在继续来到 n - 3 的位置，再去与这组的后一个数n去比较，那么就会存在越界问题、

2.5堆排序

【数据结构】 - 堆排序

2.6快速排序

快速排序是由hoare在1962年提出的一种交换排序的方法，到如今快速排序已经成为算法中应用最广泛、最出名的一个算法

hoaer版本 

hoare版本基本思想：取一基准值 key，将小于key的值通过交换全部放置在key的左边，将大于key的值通过交换全部放置在key的右边（这时key在这一趟排序中，已经处在有序数组中的正确位置），再将key的左右区间用重复的方法去处理，直到所以元素都排列到数组中的正确的位置上

单趟：

1.选择基准：从数组中选取一个元素作为基准值（pivot），通常选择第一个元素或最后一个元素

2.初始化指针：设置两个指针left指向数组的第一个元素，right指向数组的最后一个元素

3.双向遍历：

• 从right指针开始向左遍历，找到第一个小于基准值的元素。(大前提：left 与 right 未相遇)
• 而后left指针开始向右遍历，找到第一个大于基准值的元素。(大前提：left 与 right 未相遇)
• 如果 left < right，则交换这两个元素。
• 重复上述步骤，直到left和right相遇。

4.放置基准：将基准值放置在left（或right，因为此时它们相等）所在的位置，这个位置就是基准值的最终位置。

全程：对基准值左边的子数组和右边的子数组分别进行快速排序。

实现：

void KuaiShuPaiXu(int* a, int left, int right) {if (left >= right)//当区间只有一个数，或者区间不存在时，递归停止return;int keyi = left;int begin = left, end = right;while (begin < end) //在左与右未相遇的情况下找一直是大前提{while (a[end] >= a[keyi] && begin < end)//右边找小end--;while (a[begin] <= a[keyi] && begin < end)//左边找大begin++;JiaoHuan(&a[begin], &a[end]);}JiaoHuan(&a[begin], &a[keyi]);//begin与end相遇的位置，循环停止，这里的数一定比key小KuaiShuPaiXu(a, left, begin - 1);//递归左区间KuaiShuPaiXu(a, begin + 1, right);//递归右区间}

小问题 ：为什么一定要让right左走先找小？为什么 left 与 right 相遇的位置一定是小于 key的数

首先回答第一个问题：为什么一定要让right左走先找小？

因为从让right左走先找小是保证 left 与 right相遇位置一定是小于 key 的前提。如果让left右走先找大，当 left 与 right 相遇位置就不一定小于 key 了 

如果让left左走先先找大，当 left 与 right 相遇位置不一定小于 key：

此场景下 left 与 right 刚完成一次交换

这时 left 先左走找大，找到 9 后停止，right 找小直到与left相遇时也没有找到（停止），此时 left 与 right 相遇位置比key大。

---

right左走先开始能保证 left 与 right相遇位置一定小于 key

大前提1：left 与 key 并未发生任何交换

情况一：right 一直往左并为找到比key小的元素，直到与 left 相遇

此时left 与 right 相遇位置就是key的位置，right一直往左边找小并未找到，也就是说key的右边全是比它大的数，然后自己与自己发生交换。

大前提2：left 与 key 发生了一次以上的交换

情况一：right 一直走并未找到比key小的元素，直到与 left 相遇

由于left 与 key 发生过交换，此时 left 位置的元素一定比 key小，然后 key 与相遇位置交换，满足了交换位置小于key的条件

情况二：right 找到比key小的元素，接着 left 找比 key 大的元素，直到与 right 相遇

此时 right 已经找到 比key小的元素，所以left 与 right 相遇的地方的元素比key小

满足了交换位置小于key的条件

情况三：right 找到了比 key 小的元素 ，left找到了比key大的元素

这种情况正常交换

前后针版本

在快速排序出来后大家都觉得 hoare 版本的方法有点难理解，所以有人就研究出来了前后针版本的快速排序，这个版本的快排不用考虑：到底让左边先走还是右边先走的问题。所以它比较好理解

前后指针基本思想：前后指针法通过维护两个指针（通常称为prev和cur）来遍历数组，其中prev指针用于指向当前已经排序好的序列的最后一个元素，cur指针用于遍历未排序的序列以寻找新的元素来扩展已排序序列

单趟：

1.选择基准：从数组中选取一个元素作为基准值（pivot），通常选择第一个元素。

2.初始化指针：设置prev指针指向数组的第一个元素（即基准值的位置），cur指针指向数组的第二个元素。

3.遍历数组：

• cur指针向右遍历，寻找小于基准值的元素。
• 如果找到，则检查prev的下一个位置是否是cur的当前位置。如果不是，则prev向右移动一位，然后交换prev和cur指向的元素。
• 重复上述步骤，直到cur遍历完整个数组。

4.放置基准：将基准值（原本在prev的下一个位置）与prev指向的元素交换，此时基准值就位于其最终位置。

全程：

对基准值左边的子数组和右边的子数组分别进行快速排序。

实现：

void KuaiShuPaiXu_1(int* a, int left, int right) {if (left >= right) //当区间只有一个数，或者区间不存在时，递归停止return;int keyi = left;int prev = left, cur = left + 1;while (cur <= right)//循环继续条件，cur没有越界{if (a[cur] < a[keyi] && ++prev != cur)JiaoHuan(&a[cur], &a[prev]);cur++;}JiaoHuan(&a[keyi], &a[prev]); //当循环停止，把key数据的位置放到orev位置上KuaiShuPaiXu_1(a, left, prev - 1); //处理左区间KuaiShuPaiXu_1(a, prev + 1, right); //处理右区间}

挖坑法版本

挖坑法思想：在排序过程中，选择一个元素（通常是数组的第一个或最后一个元素）作为基准值（pivot），然后将这个元素的值暂时存储起来，视为其所在位置为一个“坑”。接下来，算法会遍历数组，通过比较和交换操作，将比基准值小的元素移到“坑”的左边，将比基准值大的元素移到“坑”的右边。在遍历过程中，会不断地更新“坑”的位置，直到整个数组被遍历完。最后，将基准值放回到“坑”中，这样基准值左边的所有元素都比它小，右边的所有元素都比它大，从而完成了一趟排序。

单趟：

1.选择基准：通常选择数组的第一个元素作为基准（pivot）

2.挖坑：将基准元素暂存（比如放到数组的最后一个位置或者单独的一个变量中），这个位置就形成了一个“坑”。

3.遍历数组：从数组的末尾开始向前遍历（即右边先走），寻找一个比基准元素小的元素，并将其放到“坑”里（即填坑），然后这个元素原本的位置又形成了一个新的“坑”。

4.继续遍历：继续向前遍历，寻找一个比基准元素大的元素（或者等于基准元素，取决于你的排序稳定性需求），将其放到最新形成的“坑”里，然后重复这个过程，直到遍历完所有需要比较的元素。

5.放置基准：最后，将暂存的基准元素放到其最终位置上（即所有小于它的元素都在它左边，所有大于它的元素都在它右边）。

全程：

对基准元素左边和右边的子数组分别进行快速排序。 

实现： 

void KuaiShuPaiXu_2(int* a, int left, int right) {if (left >= right)return;int key = a[left];int begin = left, end = right;while (begin < end){while (a[end] >= key && begin < end)end--;if (left < right)a[begin] = a[end];//将end位置的值放入坑中while (a[begin] <= key && begin < end)begin++;if (left < right)a[end] = a[begin];//将begin位置的值放入坑中}a[begin] = key;//把基准值放入坑中KuaiShuPaiXu_2(a, left, begin - 1);//递归左区间KuaiShuPaiXu_2(a, begin + 1, right);//递归右区间}

快排的时间复杂度

最优情况：

在最优情况下，每次分区操作都能将数组均匀地分为两部分

这时的递归的深度 = log2n 每一层的时间复杂度都是O(N)

所以在最好情况下的时间复杂度 = O(N logn )

最坏情况：

如果每次选择的key（基准值）都是当前子数组中的最大或最小元素，那么每次分区后，都会有一个子数组是空的，而另一个子数组包含除了基准元素之外的所有元素。

这时递归的深度 = N，每一层的时间复杂度都是O(N)，算法的算力就会退化成O(N²) 

快速排序算法的优化

1. 选 key 的优化

根据上面的最坏情况我们知道，如果每次选到的 key（基准值）是最大或最小的，那么它就会退化成一个O(N²)的算法。针对这种情况对于选key上就要下点功夫了，不能每次都选数组最左边的值做key。

方法一 : 随机数选key

随机从数组中选取一个元素作为基准。这种方法可以显著减少遇到最坏情况（即每次分区都极度不平衡）的概率，从而提高算法的平均性能。

方法二 ：三数取中选key

选择数组的第一个元素、中间元素和最后一个元素，然后计算这三个元素的中值（即既不是最大也不是最小的元素），并将该中值作为基准。

这种方法比固定位置法更健壮，因为它可以减少因输入数据特定顺序而导致的性能下降。然而，它仍然可能不是全局最优的，但它在实践中表现良好。

2.小区间优化

在快速排序递归的过程中当待排序的区间变得非常小时（占栈非常多）：

继续使用递归排序可能会导致不必要的函数调用开销和可能的栈溢出问题。因此，小区间优化通过在这些小区间上采用更高效的排序算 （如插入排序）来减少这些开销，并提高整体排序的效率。

小区间优化具体实现

判断区间大小：
在快速排序的递归过程中，首先检查当前待排序区间的大小。如果区间大小小于某个阈值（通常是一个较小的常数，如10或更小），则不再进行递归排序。

应用插入排序：
对于小于阈值的区间，通常改用插入排序进行排序。插入排序在数据规模较小时具有较高的效率，因为其时间复杂度为O(n^2)，但在n较小时，其常数项较小，因此实际执行速度可能优于快速排序的递归调用。

代码实现：

int SanShuQuZhong(int *a,int left,int right) {int mid = (left + right) / 2;if (a[mid] < a[right]){if (a[mid] > a[left]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}else//a[mid] > a[right]{if (a[mid] < a[left]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}
}void KuaiShuPaiXu(int* a, int left, int right) {if (left >= right)return;//小区间优化if (right - left + 1 < 10){ChaRuPaiXu(a + left, right - left + 1);//当区间只剩10个不到时，我们改为插入排序return;  //这里的插入排序要注意传数组的对应区间}//三数取中int mid = SanShuQuZhong(a,left,right);JiaoHuan(&a[mid], &a[left]);int keyi = left;int begin = left, end = right;while (begin < end){while (a[end] >= a[keyi] && begin < end)end--;while (a[begin] <= a[keyi] && begin < end)begin++;JiaoHuan(&a[begin], &a[end]);}JiaoHuan(&a[begin], &a[keyi]);//begin与end相遇的位置，循环停止，这里的数一定比key小KuaiShuPaiXu(a, left, begin - 1);//递归左区间KuaiShuPaiXu(a, begin + 1, right);//递归右区间}

2.7归并排序

归并排序（Merge Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的基本思想是：将已有序的子序列合并，得到完全有序的序列；

归并排序的主要过程可以分解为三个步骤：

1. 分解：将数组分解成两个较小的子数组，直到子数组的大小为1，此时认为子数组已经是有序的（因为只有一个元素）。

2. 递归进行排序并合并：递归地对子数组进行归并排序，并将已排序的子数组合并成一个大的有序数组，直到合并为1个完整的数组。

3. 合并：合并两个已排序的数组段。在合并过程中，比较两个数组段的当前元素，将较小的元素放入临时数组中，直到其中一个数组段的元素全部被放入临时数组。然后，将另一个数组段中剩余的元素直接复制到临时数组的末尾。

 实现：

void _GuiBingPaiXu(int* a,int *temp,int left, int right) {if (left >= right)return;//分左右区间int mid = (left + right) / 2; int begin1 = left, end1 = mid;int begin2 = mid + 1,end2 = right;int begin = left;_GuiBingPaiXu(a, temp, left, mid); //先让左区间有序_GuiBingPaiXu(a, temp, mid + 1, right);//再让右区间有序while (begin1 <= end1 && begin2 <= end2)//接下来合并两个区间{if (a[begin1] < a[begin2]) //谁小谁先进拷贝空间{temp[begin++] = a[begin1++];}else{temp[begin++] = a[begin2++];}}//将未合并完成的区间，处理完成while (begin1 <= end1){temp[begin++] = a[begin1++];}while (begin2 <= end2){temp[begin++] = a[begin2++];}memcpy(a + left, temp + left, sizeof(int) * (right - left + 1));//将数据拷贝回原数组}void GuiBingPaiXu(int* a, int n) {int* temp = (int*)malloc(sizeof(int) * n);//开辟拷贝空间_GuiBingPaiXu(a,temp,0,n - 1);free(temp);
}

2.8非比较排序

计数排序

计数排序（Counting Sort）是一种非比较型整数排序算法，其核心在于将待排序数组中出现元素的次数统计并存储在开辟的数组空间中（计数数组），作为一种线性时间复杂度的排序，它要求输入的数据必须是有确定范围的整数。

计数排序的思想和算法步骤：

1.找出待排序数组的最大值和最小值（为了确定计数数组的大小）

2.遍历原数组，将出现的元素统计到计数数组中

3.将计数数表中的数据反向填充到原数组中

实现：

void JiShuPaiXu(int* a, int n) {int min = a[0], max = a[0];//确定计数数组范围for (int i = 0; i < n; i++){if (min > a[i])min = a[i];if (max < a[i])max = a[i];}int fanwei = max - min + 1;//开辟计数数组int *count = (int*)calloc(fanwei,sizeof(int));//统计数组出现元素次数for (int i = 0; i < n; i++){count[a[i] - min]++;}//将统计的数据还原回原数组int j = 0;for (int i = 0; i < fanwei; i++){while (count[i]--){a[j++] = i + min;//i是count对应的下标}}free(count);
}

3.快速排序与归并排序的非递归实现

3.1快速排序非递归

快速排序的非递归实现，我们考虑使用栈来模拟实现

在快速排序中，每完成一趟的快速排序都会把整个数组分成：左区间与右区间。然后递归的去处理这两个区间。

而后去处理左右两个区间，实际上就是把这两个区间的 left 与 right 做根这次单挑一样的处理。所以我们只需要将每一次处理的区间大小给存起来，然后模拟递归的方式取出就可以做到快速排序的非递归实现。

实现： 

// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right) {Stack ps;//创建栈int begin;int end;StackInit(&ps);/初始化栈//存入一个区间的left 与 rightStackPush(&ps,right);//先存rihgt 在存 left到时取出时，就是先去left 在取 rightStackPush(&ps,left);while (!StackEmpty(&ps))//当栈不为空时继续处理{begin = StackTop(&ps); //取区间 leftStackPop(&ps);         //left出栈end = StackTop(&ps);   //取区间rightStackPop(&ps);         //right出栈int key = PartSort1(a,begin,end);  //随便用一种快速排序的单趟去处理这段区间//先入右区间 if (key + 1 < end){StackPush(&ps, end);StackPush(&ps, key + 1);}//在入右区间if (begin < key - 1){StackPush(&ps, key - 1);StackPush(&ps,begin);} }StackDestroy(&ps);//销毁栈
}

3.2归并排序非递归实现

归并排序的非递归实现，我们考虑用循环实现

归并排序实际上就是将数组不停的分解，直到只有数组只有一个元素时我们就认为这个数组是有序的，之后就是不停的合并。1个元素认为有序，2个元素开始合并.合并完后有序，4个元素开始合并.合并完后有序......直到只剩左右两个区间，这两个区间 = 整个数组，此时它们完成合并后数组就有序了。从两个元素开始我们就要进行归并了

用循环来实现归并排序，我们就要手动分解的区间，具体步骤：

在常规的递归中会将数组不断的分解，直到最小开始合并。

（一次循环）

红圈里面的数，可以看成一组组（例如10就是一组），接下来将两组看成一对的方式将红圈中的组全部处理完，就是一次循环。重要条件：每一组中的数将它视为有序

（整体循环）

当一次循环结束后，进入第二次循环，这次的循环将每组的数扩大至2个，依旧是两两成对的方式处理。第三次循环，将每组的数扩大至4个，此次循环过后数组就有序了。

（如何判断数组整体有序）

判断数组整体有序的方法其实非常简单，还记得重要条件：每一组中的数将它视为有序吗？

实际上这个例子中还有第四次循环：将每组的数扩大至8个。当每组的数来到8个时，我们将它视为有序，而这一组中的元素 == 数组的总元素。

所以当 一组数元素 >= 数组总元素时，数组就有序了

---

（会出现的坑）

先说在代码中是怎么表示两组的范围的：

在代码中通常会使用4个变量表示两组的头尾：[begin1,en1]（第一组头尾）,[begin2,end2]

（第二组组头尾）

而在计算这两组范围时难免会出现一些意想不到的坑，接下来我们 一 一 看去

场景一：[begin1,end1] [begin2,end2]  (红色表示越界)

这里计算的end2 越界了，但是还要就行归并排序，所以更新一下end2 == n 的位置即可

场景二：[begin1,end1] [begin2,end2] (红色表示越界)

这种情况说明一组数元素 >= 数组总元素，数组有序了

场景三：[begin1,end1] [begin2,end2] (红色表示越界)

这种情况也是一组数元素 >= 数组总元素，数组有序了

实现：

// 归并排序非递归实现
void GuiBingFeiDiGui(int* a, int n) {int begin;int begin1, end1;int begin2, end2;int gap = 1;//一组的数据个数int* temp = (int*)malloc(sizeof(int) * n);//拷贝数组if (temp == NULL){perror("malloc");return;}while(gap < n)//gap是一组的数据个数，当一组的数据个数 >= 全部的数据个数时，就没有归并的必要了，已经全部有序{begin = 0; //分成n/gap组，每两组归并，直到所有组都完成归并for (int i = 0; i < n; i += (2 * gap)) //i控制begin1的位置{begin1 = i;end1 = i + gap - 1;begin2 = end1 + 1;end2 = i + (2 * gap) - 1;if (end1 > n - 1 || begin2 > n - 1)//这两种情况不用继续归并了{break;}if (end2 > n - 1)//这种情况更新一下end2{end2 = n - 1;}//开始合并两个有序数组while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){temp[begin++] = a[begin1++];}else{temp[begin++] = a[begin2++];}}//合并完成后把可能剩下的数据按顺序放入if (begin1 <= end1){while (begin1 <= end1)temp[begin++] = a[begin1++];}else{while (begin2 <= end2)temp[begin++] = a[begin2++];}memcpy(a + i, temp + i, (end2 - i + 1) * sizeof(int));//i控制的是数组的下标，也就是两组中，第一组开始的位置，end2 - begin1 + 1 = 两组总共的数据个数}gap *= 2;   //增加一组的元素}}

4.排序算法的时间复杂度和稳定性分析