首页 > 递归/分治：归并排序

递归/分治：归并排序

前言

分治算法:

将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出 子问题的解后进行合并，就可得到原问题的解。

步骤如下:

  1. 分解，将要解决的问题划分成若 干规模较小的同类问题;
  2. 求解，当子问题划分得足够小时 ，用较简单的方法解决;
  3. 合并，按原问题的要求，将子问题 的解逐层合并构成原问题的解。
归并排序

在描述归并排序之前，我们先来看看如何合并两个有序数组，大概过程类似与之前描述过的两个有序链表的合并

实现过程如下:

void merge_two_arr(std::vector<int> &arr1, std::vector<int> &arr2, std::vector<int> &result) { int i = 0;int j = 0;/*在下标不断累加的过程中优先插入较小的一个元素，且对应的下标累加*/while(i < arr1.size() && j < arr2.size()) { if (arr1[i] <= arr2[j]) { result.push_back(arr1[i]);i++;} else { result.push_back(arr2[j]);j++;}}if (i == arr1.size()) {  //将剩余的未合并的元素合入for (;j < arr2.size(); ++j) { result.push_back(arr2[j]);}} else { for (;i < arr1.size(); ++i) { result.push_back(arr1[i]);}}
}

依据分治算法的步骤，我们回到归并排序的过程上

以上过程即实现了分治算法的第三步：合并；

那么分治算法的第一步：分解，第二步：求解该如何做呢？

显然，我们的一个无序数组同样可以不断得二分，最终拆解为对底层的两两合并，对于每一个分解后的集合，我们同样使用合并有序数组（因为只有两个元素了，要做的就是对两个元素的合并）的过程。

实现如下:

void merge_sort(std::vector<int> &arr) { if (arr.size() < 2) { return ;}int mid = arr.size() / 2;std::vector<int> arr1;std::vector<int> arr2;for (int i = 0; i < mid; ++i) { arr1.push_back(arr[i]);}for (int i = mid; i< arr.size(); ++i){ arr2.push_back(arr[i]);}merge_sort(arr1);merge_sort(arr2);arr.clear();/*以上递归返回的arr1和arr2为有序数组，最终合并两个有序数组即可*/merge_two_arr(arr1,arr2,arr); 
}

测试代码如下:

#include 
#include 
#include 
#include 
#include using namespace std;
/*合并两个有序数组*/
void merge_two_arr(std::vector<int> &arr1, std::vector<int> &arr2, std::vector<int> &result) { int i = 0;int j = 0;while(i < arr1.size() && j < arr2.size()) { if (arr1[i] <= arr2[j]) { result.push_back(arr1[i]);i++;} else { result.push_back(arr2[j]);j++;}}if (i == arr1.size()) { for (;j < arr2.size(); ++j) { result.push_back(arr2[j]);}} else { for (;i < arr1.size(); ++i) { result.push_back(arr1[i]);}}
}
/*归并排序*/
void merge_sort(std::vector<int> &arr) { if (arr.size() < 2) { return ;}int mid = arr.size() / 2;std::vector<int> arr1;std::vector<int> arr2;for (int i = 0; i < mid; ++i) { arr1.push_back(arr[i]);}for (int i = mid; i< arr.size(); ++i){ arr2.push_back(arr[i]);}merge_sort(arr1);merge_sort(arr2);arr.clear();merge_two_arr(arr1,arr2,arr);
}int main(int argc, char const *argv[])
{ std::vector<int> arr;int n; cin >> n;int tmp;for (int i = 0; i < n; ++i) { cin >> tmp;arr.push_back(tmp);}	merge_sort(arr);for (int i = 0;i < arr.size(); ++i) { cout << arr[i] << " ";}cout << endl;return 0;
}

输出如下:

#输入
5
-7 3 -4 -1 2
#输出
-7 -4 -1 2 3

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • 剑指offer: 面试题40. 最小的k个数

    题目：最小的k个数 入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例 1： 输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1] 示例 2： 输入：arr = [0,1,2,1], k = 1 输出：[0...

  • JS如何深度复制对象和数组，避免指针变量引用修改值

    //自定义深度复制对象or数组的递归方法---------------------------------------- let copyObjOrArr = o => {let isArray = o instanceof Array;let isObject = o instanceof Object;if (!isObject)...

  • 【数组方法大合集】原生js数组array常用工具方法大合集

    var array = {/* 数组求和*/sum: arr => eval(arr.join("+")),/* 判断一个数组(支持一个字符串)里面的是否有任何一个元素被包含在了某个字符串里面 */isStringContain(str, arr) {Array.isArray(arr) || (arr = [arr]);for (v...

  • 快速排序的两种实现方法(c语言版本)

    经过调研发现，对任意无序整数数组，快速排序有两种实现方法，这里简单阐述下思路： 思路一：随意选择一个基准元，一般选择数组的起始元或末尾元，Weiss这本书上特意搞了个算法来选择基准元，……，总之就是基准元的选择要尽量随机。选定基准元之后，比如选择数组起始元为基准元，从数组右边开始，向左边遍历，遇到比基准元大的跳过，直至遇到比基准元小...

  • 十种经典排序算法精粹(c语言版本)

    下面给出这段时间我苦心研究验证过的十种经典排序算法的C语言版本，即下面的排序算法： 插入排序，shell排序，冒泡排序，快速排序，选择排序，堆排序，归并排序，桶排序，基数排序和计数排序。整理出来以作备忘，不足之处，欢迎大家批评指正！其中计数排序分别给出了不稳定和稳定两种排序算法，测试时，使用随机生成大数组和随机手动输入的方法来测试。...

©2024 11GX.COM