归并排序与其例题

2024-08-27 08:20
文章标签 归并 排序 例题

本文主要是介绍归并排序与其例题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、归并排序的简述

归并排序(Merge Sort)是一种高效的排序算法,采用分治法(Divide and Conquer)的策略。它的基本思想是将一个大的问题分解成多个小问题,然后解决这些小问题,最后将结果合并起来得到最终的答案。具体来说,归并排序的算法思想可以分为以下几个步骤:

1. 分解(Divide)

将待排序的数组或列表分成两个大小相等或接近相等的子数组。这个过程会递归地进行,直到子数组的大小为1或0(即子数组已经排序好)。

2. 解决(Conquer)

当子数组的大小为1或0时,这些子数组自然是已排序的。接下来,逐步合并这些子数组,以形成较大的排序数组。

3. 合并(Merge)

将两个已排序的子数组合并成一个新的已排序的数组。这个合并操作是归并排序的关键部分,它可以通过比较两个子数组的元素并将较小的元素添加到结果数组中来完成。

详细的归并排序算法步骤:

  1. 分解

    • 如果数组的长度大于1,找到数组的中间位置,将数组分成两半。
  2. 递归排序

    • 对每个子数组递归地调用归并排序算法,直到子数组的长度为1。
  3. 合并

    • 将两个已排序的子数组合并成一个排序后的数组。可以使用两个指针分别指向两个子数组的当前元素,比较这两个元素,将较小的元素添加到结果数组中,并移动指针。

示例

假设我们要对数组 [38, 27, 43, 3, 9, 82, 10] 进行归并排序:

  1. 分解

    • [38, 27, 43, 3, 9, 82, 10] 被分成 [38, 27, 43] 和 [3, 9, 82, 10]
    • [38, 27, 43] 进一步分解为 [38] 和 [27, 43]
    • [27, 43] 进一步分解为 [27] 和 [43]
    • [3, 9, 82, 10] 被分解为 [3, 9] 和 [82, 10]
    • [3, 9] 进一步分解为 [3] 和 [9]
    • [82, 10] 进一步分解为 [82] 和 [10]
  2. 递归排序

    • 单个元素 [38][27][43][3][9][82][10] 都是已排序的。
  3. 合并

    • 合并 [27] 和 [43] 变成 [27, 43]
    • 合并 [38] 和 [27, 43] 变成 [27, 38, 43]
    • 合并 [3] 和 [9] 变成 [3, 9]
    • 合并 [82] 和 [10] 变成 [10, 82]
    • 合并 [3, 9] 和 [10, 82] 变成 [3, 9, 10, 82]
    • 最后合并 [27, 38, 43] 和 [3, 9, 10, 82] 变成 [3, 9, 10, 27, 38, 43, 82]

时间复杂度

  • 归并排序的时间复杂度为 (O(n \log n)),其中 (n) 是待排序元素的数量。这个复杂度是因为分解和合并操作都在对数级别的层次上进行,每一层需要对整个数组进行操作。

空间复杂度

  • 归并排序的空间复杂度为 (O(n)),因为需要额外的空间来存储合并后的数组。

归并排序是一种稳定的排序算法,不会改变相同元素的相对顺序。这使得它在某些需要稳定排序的场景中非常有用。

二、模板题

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行,第一行包含整数 n。

第二行包含 n 个整数(所有整数均在 1∼10^{9} 范围内),表示整个数列。

输出格式

输出共一行,包含 n 个整数,表示排好序的数列。

数据范围

1≤n≤100000

输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5

#include<iostream>using namespace std;const int N=1e5+10;
int q[N],tmp[N];void merge_sort(int q[],int l,int r){if(l>=r)  return; //当只有一个元素时,没必要递归,直接返回退出。int mid=l+r>>1,i=l,j=mid+1,k=0;//先找中点。merge_sort(q,l,mid); merge_sort(q,mid+1,r);/*找到中点后将整个要排序的序列分成了两半,然后左边右边归并排序使得左右两边的序列变成有序的,所以这里递归一下。*//*当分成的左右两个序列恰好是长度相等的时候,就执行下面while里面的操作。*/while(i<=mid&&j<=r){if(q[i]<=q[j])  tmp[k++]=q[i++];/*在左右两个序列中找更小的值,然后把这个更小的值放入已经准备好的临时数组tmp[N]。tmp[k++]=q[i++];   这句话其实等价于tmp[k]=q[i]; k++,i++;  这样只写一句话是为了代码更简洁。*/else tmp[k++]=q[j++];}/*当分成的左边的序列大于右边的序列时,直接将左边序列剩余的部分接在tmp数组后面就是。因为本来左右两边的序列就已经是有序的了,所以左边序列剩下来的数都是要大于整体的数,因为比他们小的数已经放进去tmp临时数组了,这一点要注意。*/while(i<=mid) tmp[k++]=q[i++];while(j<=r) tmp[k++]=q[j++];for(int i=l,j=0;i<=r;i++,j++)  q[i]=tmp[j];/*这是将tmp数组里面的值复制给原本的q[N],因为tmp本就是设立的临时数组,最后输出的话还得是q[N]这个实体的。*/
}int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&q[i]); merge_sort(q,0,n-1);for(int i=0;i<n;i++) printf("%d ",q[i]);return 0;
}

归并排序是一种经典的排序算法,其基本思想是分治法。它的主要步骤是将一个大问题分解成若干个小问题,对每个小问题进行解决,然后将结果合并成一个整体。下面是代码的逐行详细解释:

#include<iostream> using namespace std; const int N=1e5+10; int q[N],tmp[N];

  • #include<iostream>: 包含输入输出流库,用于输入和输出操作。
  • using namespace std;: 使用 std 命名空间中的所有符号,避免写 std:: 前缀。
  • const int N=1e5+10;: 定义常量 N,表示数组 q 和 tmp 的最大大小。1e5+10 即 100010
  • int q[N], tmp[N];: 声明两个整型数组 q 和 tmp,分别用于存储待排序的数组和临时数组。
 

void merge_sort(int q[], int l, int r){ if(l >= r) return; //当只有一个元素时,没必要递归,直接返回退出。

  • void merge_sort(int q[], int l, int r): 定义一个名为 merge_sort 的函数,接收待排序数组 q、左边界 l 和右边界 r 作为参数。
  • if(l >= r) return;: 当子数组的左边界 l 不小于右边界 r 时,说明子数组只有一个或零个元素,此时已经不需要进一步分割,直接返回。

int mid = l + r >> 1, i = l, j = mid + 1, k = 0; // 先找中点。 merge_sort(q, l, mid); merge_sort(q, mid + 1, r);

  • int mid = l + r >> 1;: 计算中点,l + r >> 1 是 (l + r) / 2 的位运算实现。
  • int i = l, j = mid + 1, k = 0;: 初始化指针 ij 和 ki 指向左子数组的起始位置,j 指向右子数组的起始位置,k 用于标记临时数组 tmp 的位置。
  • merge_sort(q, l, mid); merge_sort(q, mid + 1, r);: 对左半部分 [l, mid] 和右半部分 [mid + 1, r] 递归调用 merge_sort 函数,分别排序这两部分。
 

while(i <= mid && j <= r){ if(q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; }

  • while(i <= mid && j <= r): 当左子数组和右子数组都有剩余元素时,比较两者的当前元素。
  • if(q[i] <= q[j]) tmp[k++] = q[i++];: 如果左子数组的当前元素 q[i] 小于或等于右子数组的当前元素 q[j],将 q[i] 复制到 tmp[k],然后移动指针 i 和 k
  • else tmp[k++] = q[j++];: 如果右子数组的当前元素 q[j] 小于左子数组的当前元素 q[i],将 q[j] 复制到 tmp[k],然后移动指针 j 和 k
 

while(i <= mid) tmp[k++] = q[i++]; while(j <= r) tmp[k++] = q[j++];

  • while(i <= mid) tmp[k++] = q[i++];: 当左子数组有剩余元素时,将这些元素复制到 tmp 中。
  • while(j <= r) tmp[k++] = q[j++];: 当右子数组有剩余元素时,将这些元素复制到 tmp 中。

for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];

  • for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];: 将临时数组 tmp 中的排序结果复制回原数组 qi 遍历原数组的范围 [l, r]j 遍历临时数组 tmp 的范围。
 

int main(){ int n; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &q[i]); merge_sort(q, 0, n - 1); for(int i = 0; i < n; i++) printf("%d ", q[i]); return 0; }

  • int main(): 主函数的开始。
  • int n;: 定义整型变量 n,用于存储数组的大小。
  • scanf("%d", &n);: 从标准输入读取数组的大小 n
  • for(int i = 0; i < n; i++) scanf("%d", &q[i]);: 从标准输入读取 n 个整数并存入数组 q
  • merge_sort(q, 0, n - 1);: 调用 merge_sort 函数对数组 q 进行排序。
  • for(int i = 0; i < n; i++) printf("%d ", q[i]);: 打印排序后的数组。
  • return 0;: 主函数返回 0,表示程序正常结束。

总结

归并排序的基本流程是递归地将数组分成两半,分别对这两半进行排序,然后将它们合并成一个有序数组。该代码实现了归并排序的这一过程,通过分割、排序和合并三个主要步骤来完成数组的排序。

那上面的代码就是归并排序的模板,和快速排序一样要理解与记忆,当涉及到归并排序时,就可以用这个模板。

三、实战例题

给定一个长度为 n的整数数列,请你计算数列中的逆序对的数量。

逆序对的定义如下:对于数列的第 i 个和第 j个元素,如果满足 i<j 且 a[i]>a[j],则其为一个逆序对;否则不是。

输入格式

第一行包含整数 n,表示数列的长度。

第二行包含 n个整数,表示整个数列。

输出格式

输出一个整数,表示逆序对的个数。

数据范围

1≤n≤100000,
数列中的元素的取值范围 [1,10^{9}]。

输入样例:
6
2 3 4 5 6 1
输出样例:
5

 

#include<iostream>using namespace std;
typedef long long LL;//这里是将long long类型定义为其他名字,其实质还是一样的,就相当于自己取了一个别名。
const int N=1e5+10;
int q[N],tmp[N];/*如果只用int的话是装不下的,因为int的取值范围最大是2的31次方,这个题超过了这个范围,所以用long long类型定义为其他名字*/
LL merge_sort(int q[],int l,int r){if(l>=r) return 0;/*这里不仅仅是简单的退出,因为要统计逆序对的数量,所以当只有一个元素的时候直接返回0就行了,表示没有逆序对。*/int mid=l+r>>1,i=l,j=mid+1,k=0;LL res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);/*这个res表示两种情况的逆序对数量,都在左边的和都在右边的。为什么归并排序的结果会是逆序对的数量呢,这是因为在归并排序中虽然是比较谁更小,然后放入结果数组,但是你比较得出谁更小的同时也得到了这两个数谁更大,所以相当于一石二鸟,既能找到小的那个放入结果数组,也知道了谁更大,从而逆序对的数量也就知道了。*/while(i<=mid&&j<=r){if(q[i]<=q[j]) tmp[k++]=q[i++];else{tmp[k++]=q[j++];res+=mid-i+1;/*这是逆序对数量存在的第三种情况就是上面图里面黄色部分的地方。当已经确定i<r且q[i]>q[j]的时候,i指针后面的值是一定会比j指针所指的值大的,因为左右子数组都是已经有序了的,相当于说i指向的后面的值只会比i更大,本身i现在所指的值就已经大于j所指的值,那i后面的肯定也是大于的,也就是说i指针后面所有的值都可以与j所指的值形成逆序对,所以算出i指针及其后面值的个数就是逆序对的数量,也就是直到左子数组的边界。最后才得到这个mid-i+1。*/}}while(i<=mid) tmp[k++]=q[i++];while(j<=r)  tmp[k++]=q[j++];//这些都是归并排序的正常模板,直接写就行。for(int i=l,j=0;i<=r;i++,j++)  q[i]=tmp[j];return res;//注意返回结果res,因为最后要的是逆序对的数量而不是输出一个序列,所以要返回一下。
}int main(){int n;cin>>n;for(int i=0;i<n;i++)  scanf("%d",&q[i]);cout<<merge_sort(q,0,n-1)<<endl;return 0;
}

补充说明:

1. 逆序对的定义

在一个数组中,逆序对是指数组中前面的元素大于后面的元素。给定数组 arr,逆序对的定义是 (i, j),其中 i < jarr[i] > arr[j]

2. 归并排序简介

归并排序是一种分治算法,步骤如下:

  1. 分解:将数组分成两个子数组。
  2. 解决:递归地对这两个子数组进行归并排序。
  3. 合并:将两个已排序的子数组合并成一个有序数组。

3. 计算逆序对的思路

在归并排序的“合并”步骤中,我们可以同时统计逆序对的数量。具体步骤如下:

  1. 分解:递归地对数组进行分解,直到每个子数组只有一个元素(自然是已排序的)。

  2. 合并:在合并过程中统计逆序对。假设我们有两个已排序的子数组 leftright,我们可以用两个指针分别遍历这两个子数组:

    • 如果 left[i] <= right[j],则 left[i] 和 right[j] 不形成逆序对,移动 left 的指针。
    • 如果 left[i] > right[j],则 left[i] 与 right 子数组中的所有元素都形成逆序对。这个原因是 right 子数组中的元素已经排序,并且比 left[i] 小,所以 right 中的所有元素都和 left[i] 形成逆序对。然后移动 right 的指针。
  3. 统计逆序对:在合并的过程中,累加每次发现的逆序对的数量,最终得到整个数组的逆序对数量。

4. 合并过程中逆序对的统计示例

假设我们有两个已排序的子数组 left = [1, 3, 5]right = [2, 4, 6],我们在合并时可以这样统计逆序对:

  • left[0] 和 right[0] 比较:1 <= 2,不形成逆序对。
  • left[1] 和 right[0] 比较:3 > 2,形成逆序对。此时 right 中的所有元素都比 left[1] 小,所以 left[1] 与 right 中的所有元素形成逆序对。
  • 类似地,继续比较,统计所有可能的逆序对。

5. 时间复杂度

归并排序的时间复杂度是 O(n log n),由于在合并阶段我们额外进行逆序对的统计,这个操作也在 O(n log n) 时间内完成。因此,使用归并排序来计算逆序对是非常高效的。

总结来说,逆序对的数量可以通过归并排序来求得,主要是利用了归并过程中对已排序子数组的合并操作来统计逆序对。这样可以在 O(n log n) 的时间复杂度内完成计算。

 

这篇关于归并排序与其例题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1111133

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

鸡尾酒排序算法

目录 引言 一、概念 二、算法思想 三、图例解释 1.采用冒泡排序:   2.采用鸡尾酒排序:  3.对比总结 四、算法实现  1.代码实现  2.运行结果 3.代码解释   五、总结 引言 鸡尾酒排序(Cocktail Sort),也被称为双向冒泡排序,是一种改进的冒泡排序算法。它在冒泡排序的基础上进行了优化,通过双向遍历来减少排序时间。今天我们将学习如何在C

快速排序(java代码实现)

简介: 1.采用“分治”的思想,对于一组数据,选择一个基准元素,这里选择中间元素mid 2.通过第一轮扫描,比mid小的元素都在mid左边,比mid大的元素都在mid右边 3.然后使用递归排序这两部分,直到序列中所有数据均有序为止。 public class csdnTest {public static void main(String[] args){int[] arr = {3,

O(n)时间内对[0..n^-1]之间的n个数排序

题目 如何在O(n)时间内,对0到n^2-1之间的n个整数进行排序 思路 把整数转换为n进制再排序,每个数有两位,每位的取值范围是[0..n-1],再进行基数排序 代码 #include <iostream>#include <cmath>using namespace std;int n, radix, length_A, digit = 2;void Print(int *A,

常用排序算法分析

1. 插入排序 1.1 性能分析 时间复杂度O(n^2), 空间复杂度O(1) 排序时间与输入有关:输入的元素个数;元素已排序的程度。 最佳情况,输入数组是已经排好序的数组,运行时间是n的线性函数; 最坏情况,输入数组是逆序,运行时间是n的二次函数。 1.2 核心代码 public void sort(){int temp;for(int i = 1; i<arraytoSort.