【算法基础】归并排序

news/2024/11/9 5:04:38/

一、归并排序的思想

二、归并排序的步骤

三、归并的方式

四、代码模板

一、归并排序的思想

归并排序和快速排序一样，都是分治的思想。它是将一个无序的数组一分为二，最后再合二为一，将两个有序数组合并成为一个有序数组。

时间复杂度：O(nlogn)是稳定的排序

二、归并排序的步骤

①确定分界点。这个分界值通常是中间值 $mid = (l + r) / 2$

②递归排序分界点左右两部分的区间。

③归并。将两个有序序列合并成一个有序序列。【重点】

三、归并的方式

【双指针算法】

大致过程如下（后附流程图）：

第一步：使用2个指针 $i = l$ ， $j = mid + 1$ 分别指向分界点两端的数组头。

第二步：创建临时数组tmp来暂存排完有序的数组，用k来遍历tmp。

第三步：比较 $a[i]$ 和 $a[j]$ 直至其中一个数组中的元素全部比完。分为两种情况：若 $a[i] \leq a[j]$ , 则 $tmp[k++] = a [i++]$ (将小的元素先放入tmp)，同理， $a[i] > a[j]$ ,则 $tmp[k++] = a[j++]$

第三步：左右区间可能会有多余元素，则将多余元素原封不动放入数组tmp

第四步：最后再将tmp数组中的元素复制回原数组 $a[ ]$

【流程图】

四、代码模板

//定义全局变量临时数组
int tmp[10000000];
void merge_sort(int a[],int l,int r)
{if (l >= r) return; //一个数或没有数，没必要排序(递归出口) //第一步：确定分界点int mid = (l + r) / 2;//第二步：递归排序分界点左右两部分的区间//递归左部分区间merge_sort(a,l,mid);//递归右部分区间merge_sort(a,mid + 1,r);//第三步：归并(双指针)int i = l,j = mid + 1;int k = 0;//遍历临时数组kmpwhile(i <= mid && j <= r){if (a[i] <= a[j]) tmp[k++] = a[i++];else tmp[k++] = a[j++];}//如果左区间还有元素while (i <= mid) tmp[k++] = a[i++];//如果右区间还有元素while(j <= r) tmp[k++] = a[j++];//最后将tmp里的元素复制到原数组a[]for(int i = l,k = 0;i <= r;i++,k++) a[i] = tmp[k];
}