数据结构与算法|【算法】——归并排序的解析数据结构|c语言|排序算法|推荐

目录

1.归并排序的思想
2.归并排序的分析
3.内排序和外排序
1.归并排序的思想

归并是将两个或两个以上的有序表组合成一个新的有序表，假设初始序列含有n个记录，则可看成是n个子序列，每个子序列的长度为1，然后两两归并，得到[ n/2 ]个长度为2或为1的有序的子序列；在两两归并... ... ，如此重复，直到得到一个长度为n的有序序列为止。如下：

文章图片

2.归并排序的分析我们先来对两个序列合成新的有序序列进行分析; 我们以上面的第三趟排序作为例子

文章图片

这就完成了两个序列合并的算法,代码如下。

void _MergeSortNonR(int* a,int* tmp,int begin1,int end1, int begin2, int end2) { int cur1 = begin1; //cur1是子序列1的指针指向位置 int cur2 = begin2; //cur2是子序列2的指针指向位置 int cur3 = begin1; //临时数组指向的位置 //将子序列1和子序列2进行比较，然后将较小的值 //插入到临时数组中 while (cur1 <= end1 && cur2 <= end2) { if (a[cur1] < a[cur2]) { tmp[cur3] = a[cur1]; cur1++; } else { tmp[cur3] = a[cur2]; cur2++; } cur3++; } //将剩下的子序列的值插入到 //临时数组中 while (cur1 <= end1) { tmp[cur3++] = a[cur1++]; } while (cur2 <= end2) { tmp[cur3++] = a[cur2++]; } //将临时数组中的数组拷贝给原来的数组 for (int i = begin1; i <= end2; i++) { a[i] = tmp[i]; } }

其中a是为原数组，tmp是临时数组。begin1和end1为序列1的区间，begin2和end2为序列2的区间。

当然完成两个序列合并只是其中的一部分，要完成归并排序的算法，我们还要继续往下分析：

文章图片

起初begin1为指向4的位置为0，则endl为begin1+gap-1，begin2为begin1+gap，end2为begin1+2gap-1，其中gap为子序列的间隔，此时的gap为2.
当上面的子序列排完序后，则跳到下一组序列进行排序。则begin1为指向1的位置，其中的begin1由上一个being1+=2gap跳过来的。如果按照上面计算的话，我们在每一趟中的后面需要在判断end2和end1，如果end2大于n-1时，则表示end2比数组最后一个数据的地址要大，所以令end2等于n,如果end1大于n-1时，则表示end1比数组最后一个数据的地址要大，这时候最后一个就只有一个子序列，所以不用在比较了，直接跳出循环循环即可.

文章图片

当每趟归并排序完成最后一组排序时，则begin1>n,则代表这一趟的归并排序结束，再将gap乘以2倍，进行下一趟的归并排序，当最后一趟排序结束时，其中的gap>=n/2,所以当gap>n时就完成排序.

void MergeSort(int* a, int n) { //创建一个临时数组 int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { printf("malloc申请失败\n"); exit(); } int gap = 1; //第一趟排序的gap为1 while ( gap <= n) { //设i为每两个序列中begin1的值 for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //end2大于n-1，则end2改为n-1 if (n-1 < end2) { end2 =n-1; } //如果end1大于n-1，则这一趟就不需要在排序了 if (n-1 < end1) { break; } //两个序列合成为一个新的序列 _MergeSortNonR(a, tmp, begin1, end1, begin2, end2); } gap *= 2; } //释放临时数组 free(tmp); tmp = NULL; }