关键词：
【408数据结构与算法】—归并排序（二十二）
一、归并排序基本思想
- 基本思想：将两个或两个以上的有序子序列归并为一个有序的序列。
- 在内部排序中，通常采用的是2-路归并排序
- 归并排序（ Merge Sort ）就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式
归并排序示例
整个归并排序仅需log2n趟
关键问题：如何将两个有序序列合并成一个有序序列
二、算法分析
时间效率：O（nlogn）
C语言代码实现：从上往下
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
// 归并排序：将一个数组中两个相邻有序空间合并成一个
// 参数说明
// a -- 包含两个有序区间的数组
// start -- 第一个有序区间的起始地址
// mid -- 第一个有序区间的结束地址。也是第二个有序区间的起始地址
// end -- 第二个有序区间的结束地址
void merge(int a[], int start, int mid, int end)
int* tmp = (int*)malloc((end - start + 1) * sizeof(int));
// tmp是汇总2个有序区间的临时区域。
int i = start; // 第一个有序区的索引
int j = mid + 1; // 第二个有序区的索引
int k = 0; // 临时区域的索引
while (i <= mid && j <= end)
if (a[i] <= a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
while (i <= mid)
tmp[k++] = a[i++];
while (j <= end)
tmp[k++] = a[j++]; // 将两个有序区间合并
// 排序后的元素，全部都整合到数组a中
for (i = 0; i < k; i++)
a[start + i] = tmp[i];
free(tmp);
tmp = NULL;
// 归并排序--从上往下
// 参数说明：
// a -- 待排序数组
// start -- 数组的起始地址
// end -- 数组的结束地址
//
void merge_sort_up_to_down(int a[], int start, int end)
if (a == NULL || start >= end)
return;
int mid = (end + start) / 2;
merge_sort_up_to_down(a, start, mid); // 递归排序a[start..mid]
merge_sort_up_to_down(a, mid + 1, end); // 递归排序a[mid..end]
// a[start..mid]和a[mid..end]是两个有序空间
// 将它们排序成一个有序空间a[start..end]
merge(a, start, mid, end);
int main()
int arr[] = 9,5,1,6,2,3,0,4,8,7 ;
merge_sort_up_to_down(arr, 0, 9);
for (int i = 0; i < 10; i++)
printf("%d ", arr[i]);
printf("\\n");
return 0;
从下往上
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
// 归并排序：将一个数组中两个相邻有序空间合并成一个
// 参数说明
// a -- 包含两个有序区间的数组
// start -- 第一个有序区间的起始地址
// mid -- 第一个有序区间的结束地址。也是第二个有序区间的起始地址
// end -- 第二个有序区间的结束地址
void merge(int a[], int start, int mid, int end)
int* tmp = (int*)malloc((end - start + 1) * sizeof(int));
// tmp是汇总2个有序区间的临时区域。
int i = start; // 第一个有序区的索引
int j = mid + 1; // 第二个有序区的索引
int k = 0; // 临时区域的索引
while (i <= mid && j <= end)
if (a[i] <= a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
while (i <= mid)
tmp[k++] = a[i++];
while (j <= end)
tmp[k++] = a[j++]; // 将两个有序区间合并
// 排序后的元素，全部都整合到数组a中
for (i = 0; i < k; i++)
a[start + i] = tmp[i];
free(tmp);
tmp = NULL;
// 对数组a做若干次合并：数组a的总长度为len，将它分为若干个长度为gap的数组；
// 将“没两个相邻的子数组”进项归并排序
//
// 参数说明
// a -- 待排序的数组
// len -- 数组的长度
// gap -- 子数组的长度
void merge_groups(int a[], int len, int gap)
int i;
int len_2 = 2 * gap; // 两个相邻子数组的长度
// 将“每两个相邻的子数组”进行合并排序
for (i = 0; i + 2 * gap - 1 < len; i += (2 * gap))
merge(a, i, i + gap - 1, i + 2 * gap - 1);
// 若 i+gap-1 < len-1，则剩余一个组数组没有配对
// 将该自数字合并到已排序的数组中
if (i + gap - 1 < len - 1)
merge(a, i, i + gap - 1, len - 1);
// 归并排序 从下往上
// 参数说明
// a -- 待排序的数组
// b -- 数组长度
void merge_sort_down_to_up(int a[], int len)
int n;
if (a == NULL || a <= 0)
return;
for (n = 1; n < len; n *= 2)
merge_groups(a, len, n);
int main()
int arr[] = 9,5,1,6,2,3,0,4,8,7 ;
merge_sort_down_to_up(arr, 10);
for (int i = 0; i < 10; i++)
printf("%d ", arr[i]);
printf("\\n");
return 0;
总结
408数据结构与算法—堆排序（二十一）(代码片段)
【408数据结构与算法】—堆排序（二十一）一、堆的定义从堆的定义可以看出，堆实质是满足如下性质的完全二叉树，二叉树中任一非叶子结点均小于（大于）它的孩子结点C语言代码实现#include<stdio.h>... 查看详情
408数据结构与算法—堆排序（二十一）(代码片段)
【408数据结构与算法】—堆排序（二十一）一、堆的定义从堆的定义可以看出，堆实质是满足如下性质的完全二叉树，二叉树中任一非叶子结点均小于（大于）它的孩子结点C语言代码实现#include<stdio.h>... 查看详情
408数据结构与算法—选择排序（二十）(代码片段)
【408数据结构与算法】—选择排序（二十）一、选择排序选择排序基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置。基本思想：首先通过n-1次关键字比较，从n个记录中找出关键字... 查看详情
408数据结构与算法—基数排序（桶排序）（二十三）(代码片段)
【408数据结构与算法】—基数排序（桶排序）（二十三）基本思想：分配+收集基数排序也叫桶排序或箱排序，设置若干箱子，将关键字为k的记录放入第k个箱子，然后按序号将非空的连接。基数... 查看详情
408数据结构与算法—基数排序（桶排序）（二十三）(代码片段)
【408数据结构与算法】—基数排序（桶排序）（二十三）基本思想：分配+收集基数排序也叫桶排序或箱排序，设置若干箱子，将关键字为k的记录放入第k个箱子，然后按序号将非空的连接。基数... 查看详情
408数据结构与算法—选择排序（二十）(代码片段)
【408数据结构与算法】—选择排序（二十）一、选择排序选择排序基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置。基本思想：首先通过n-1次关键字比较，从n个记录中找出关键字... 查看详情
408数据结构与算法—广义表（二十六）(代码片段)
【408数据结构与算法】—广义表（二十六）一、广义表广义表又称列表Lists是n>=0个元素a0,a1,…an-1的哟选序列，其中每一个ai或者是原子，或者是一个广义表广义表通常记作：LS=（a1,a2,…an）其中... 查看详情
408数据结构与算法—广义表（二十六）(代码片段)
【408数据结构与算法】—广义表（二十六）一、广义表广义表又称列表Lists是n>=0个元素a0,a1,…an-1的哟选序列，其中每一个ai或者是原子，或者是一个广义表广义表通常记作：LS=（a1,a2,…an）其中... 查看详情
408数据结构与算法—树和二叉树（二十七）(代码片段)
【408数据结构与算法】—树和二叉树（二十七）一、树的定义树的定义树是n(n>=0)个结点的有限集。若n=0;称为空树若n>0;则它满足如下两个条件有且仅有一个特定的称为根的结点其余结点可分为m(m>=0)个互不... 查看详情
408数据结构与算法—树和二叉树（二十七）(代码片段)
【408数据结构与算法】—树和二叉树（二十七）一、树的定义树的定义树是n(n>=0)个结点的有限集。若n=0;称为空树若n>0;则它满足如下两个条件有且仅有一个特定的称为根的结点其余结点可分为m(m>=0)个互不... 查看详情
408数据结构与算法—数组和特殊矩阵的压缩存储（二十五）(代码片段)
【408数据结构与算法】—数组和特殊矩阵的压缩存储（二十五）一、数组数组：按一定格式排列起来的具有相同类型的数据元素的集合一维数组：若线性表中的数据元素为非结构的简单元素，则称为一组数组... 查看详情
408数据结构与算法—数组和特殊矩阵的压缩存储（二十五）(代码片段)
【408数据结构与算法】—数组和特殊矩阵的压缩存储（二十五）一、数组数组：按一定格式排列起来的具有相同类型的数据元素的集合一维数组：若线性表中的数据元素为非结构的简单元素，则称为一组数组... 查看详情
408数据结构与算法—冒泡排序（十八）(代码片段)
【408数据结构与算法】—冒泡排序（十八）一、交换排序交换排序思想：两两比较，如果发生逆序则交换，直到所有的记录都排好为止常见的交换排序的方法：冒泡排序O(n^2)快速排序O(nlog2n)二、冒泡排序基... 查看详情
408数据结构与算法—快速排序（十九）(代码片段)
【408数据结构与算法】—快速排序（十九）一、🤣快速排序的基本思想任取一个元素（如：第一个）为中心所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表对各子表重新选... 查看详情
python数据结构与算法（17）---归并排序(代码片段)
目录归并排序图解归并排序实战：归并排序归并排序归并排序，又名MergeSort，是建立在归并操作上的一种有效的排序算法。其具体原理有2个关键字：分与治。分：我们需要进行分的操作，将数列均衡的分... 查看详情
408数据结构与算法—栈与递归(代码片段)
【408数据结构与算法】—栈与递归（十二）🎬博客主页：王同学要努力🎬个人简介：大三小白，喜欢前端，热爱分享🎥本文由王同学要努力原创，首发于CSDN🙉🌲JavaScript专栏推荐&#... 查看详情
数据结构与算法笔记——归并排序(代码片段)
什么是归并排序归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就... 查看详情
数据结构与算法——归并排序(代码片段)
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（DivideandConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将... 查看详情