精华内容
下载资源
问答
  • 归并排序基本思想

    2021-07-06 19:40:09
    一、归并排序算法的基本思想:分治思想 分治思想:分:划分成很多个小的问题,然后递归处理,治:将分阶段得到的答案整合起来,即为分治思想。 快速排序算法的基本流程如下: ![在这里插入图片描述]...

    前言

    今天跟着AcWing研究了一下归并排序算法,对归并排序算法有了一定的体会,所以写了以下文章。

    一、归并排序算法的基本思想:分治思想

    分治思想:分:划分成很多个小的问题,然后递归处理,治:将分阶段得到的答案整合起来,即为分治思想。


    快速排序算法的基本流程如下:

    在这里插入图片描述

    二、归并排序的基本内容

    1. 找出数组的基准值位置mid=(l+r)/2,其中l,r分别表示当前数组的头尾位置
    2. 分别递归调用merge_sort(arr ,l ,mid)和merge(arr,mid+1,r)
    3. 从基准值将数组一分为二
    4. 构造一个临时数组对两个数组进行从小到大的合并
    5. 将临时数组里面的元素放到arr数组里面

    三、代码如下:

        public static void merge_sort(int[] arr,int l,int r) {
            if (l >= r) return;
            int mid = (l+r)/2;
            merge_sort(arr,l,mid);
            merge_sort(arr,mid+1,r);
            int i = l,j = mid+1,k = 0;
            int[] temp = new int[arr.length];
            while(i<=mid&&j<=r){
                if(arr[i] <= arr[j]) temp[k++]=arr[i++];
                else temp[k++] = arr[j++];
            }
            while (i<=mid)temp[k++] = arr[i++];
            while (j<=r)temp[k++] = arr[j++];
            for (int m=l,s=0;m <= r; m++,s++){
                arr[m]=temp[s];
            }
        }
    

    总结

    例如:以上就是今天要讲的内容,本文主要讲述了归并排序的基本思想,归并排序和快速排序算法一样主要体现了分治思想,归并排序是一个稳定的算法。
    展开全文
  • 排序算法1:归并排序归并排序1:归并排序基本思想2:归并排序的应用:小和问题和逆序对问题2.1 小和问题和逆序对问题2.2 C++的代码示例2.3 python代码示例 归并排序 1:归并排序基本思想 1:归并排序的过程:递归+...

    归并排序

    1:归并排序基本思想

    1:归并排序的过程:递归+合并
      递归:每一次将数组分为左右2个子数组,然后再将左右2个子数组划分为2个子数组。base是当划分的子数组只有1个数字时,就直接返回。返回了两个base的结果之后,然后进行合并操作。

      合并:首先最基础的base是,左边子数组返回只有1个数,右边子数组返回只有1个数,两个数之间可以比较大小排序。那么这时返回后,左边子数组有2个数,右边子数组有2个数;相应地,如果数组很长,那么之后是左边排序后是4个数,右边排好序后是4个数。。左8,右8。。

    这个时候怎么较快地对左右进行合并后排好序呢?
      常用方法是使用双指针方法,即额外准备一个和左边子数组的长度(eg:4)与右边子数组的长度(eg:4)的和一样长的数组,即额外空间复杂度为8。然后左指针p指向左边子数组的第一个元素,右指针q指向右边子数组的第一个元素。
    process:
     1)哪个指针指向的数小,则拷贝该数到新数组中,同时该指针指向下一个数;
     2)直到有一个左右中有一个子数组拷贝完了,则直接拷贝另一个子数组的所有元素到新数组中;
     3)最后再把新数组中的元素全部拷贝回原来数组的位置;
    下面是具体的图的说明,该图使用了参考链接[1]中的图片:
    第一步是递归:
    在这里插入图片描述
    第二步是合并:
    在这里插入图片描述

    2:归并排序的应用:小和问题和逆序对问题

    2.1 小和问题和逆序对问题

      小和问题:在一个随机数组中,找出左边比右边元素小的所有元素之和。
      逆序对问题:一个随机数组中,如果左边的数大,右边的数小,则称这两个数位一个逆序对。 求出一个数列中有多少个逆序对。
    分析
    小和问题:
      归并排序在第二步合并的操作时,对于左边子数组有一个指针p,右边子数组有一个指针q。由于在两个子数组内部是有序的,所以如果p指针指向的元素小于q指针指向的元素,那么对于p指针所指向的值(eg:3)来说,从右边子数组的q指针到最后的所有元素的个数(eg:5)都肯定是大于p指针指向的值,所以此时对于这个3来说,小数和sum = sum + 3*5。
      具体可以参考下面的C++的代码。即对于左边子数组的p指针指向的值N,如果小于右边子数组的q指针指向的值M,那么右边子数组的q到右边子数组的边界Right就有(Right - p2 + 1)个N,所以有:

    sum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;  // 计算小数和
    

    逆序对问题:
      同理,逆序对问题也是一样的性质,只是逆序对是当左边子数组的p指针指向的值N,大于右边子数组的q指针指向的值M时,形成了一对逆序对。同理这个时候应该是左边子数组的指针q到左边子数组的边界mid的所有元素都是大于q指针指向的值M的。具体的C++代码如下:

    sum += arr[p1] > arr[p2] ? (mid - p1 + 1) : 0; 计算逆序对的对数 
    

    2.2 C++的代码示例

    2.2.1 main.c文件

    #include <iostream>
    #include <time.h>
    #include <stdlib.h>
    #include "MergeSort.h"
    using namespace std;
    
    // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR] 闭区间
    int *generateRandomArray(int n, int rangeL, int rangeR) {
        if (rangeL >= rangeR){
            cout << "lt is wrong!" << endl;
        }
    	int *arr = new int[n]; // 创建一个 n个元素的数组
    
    	srand(time(NULL)); // 随机种子
    	for (int i = 0; i < n; i++)
    	    arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
    	return arr;
    }
    
    int main()
    {
        int len = 15;
        int minnum = 0;
        int maxnum = 100;
        int *arr = generateRandomArray(len, minnum, maxnum);
        cout << "Orignal array:" << endl;
        for (int i=0; i<len; i++){
            cout << arr[i] << "   ";
        }
        cout << endl;
        int brr[len];
        for (int i=0; i<len; i++){
            brr[i] = arr[i];
        }
    
        //归并排序
        int* result =  MergeSortArr(brr, len);
        cout << "print the MergeSortArr result!" << endl;
        for (int i=0; i<len; i++){
            cout << result[i] << "   ";
        }
        cout << endl;
    
        return 0;
    }
    }
    

    2.2.2 MergeSort.h头文件

    #ifndef MERGESORT_H_INCLUDED
    #define MERGESORT_H_INCLUDED
    #endif // MERGESORT_H_INCLUDED
    int* MergeSortArr(int arr[], int len);
    

    2.2.3 MergeSort.cpp文件

    #include <iostream>
    #include "MergeSort.h"
    using namespace std;
    
    int Merge(int arr[],int left,int mid,int right){
    	int * help = new int[right- left + 1];
    	int p1 = left;
    	int p2 = mid + 1;
    	int i = 0;
    	int sum = 0;
    	while(p1 <= mid && p2 <= right){
    		sum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;  // 计算小数和
    		//sum += arr[p1] > arr[p2] ? (mid - p1 + 1) : 0; 计算逆序对的对数
    		help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    	}
    	while(p1 <= mid){
    		help[i++] = arr[p1++];
    	}
    	while(p2 <= right){
    		help[i++] = arr[p2++];
    	}
    	for(int j = 0;j < i;j++){
    		arr[left + j] = help[j];
    	}
    	delete []help;
    	return sum;
    }
    int MergeSort(int arr[],int left,int right){
    	if(left == right) return 0;
    	int mid = left + ((right - left)>>1);
    	return MergeSort(arr,left,mid) + MergeSort(arr,mid+1,right) + Merge(arr,left,mid,right);
    }
    
    int* MergeSortArr(int arr[], int len){
        cout << "####################" << endl;
        cout << "Begin to merge sort!" << endl;
        MergeSort(arr,0,len - 1);
        return arr;
    }
    

    2.2.4 结果展示
      由于初始无序数组是随机的,所以结果可能不会完全相同,仅作展示。
    在这里插入图片描述

    2.3 python代码示例

    这里仅给出归并排序python代码的核心部分:

    def merge_sort(items, le=lambda x, y: x <= y):
        """主函数体"""
        if len(items) <= 1:
            return items
        mid = len(items) // 2
        items1 = merge_sort(items[:mid], le)
        items2 = merge_sort(items[mid:], le)
        return merge(items1, items2, le)
    
    def merge(items1: list, items2: list, le=lambda x, y: x <= y) -> list:
        """将两个有序列表合并为一个新的有序列表"""
        items3 = []
        index1, index2 = 0, 0
        while index1 < len(items1) and index2 < len(items2):
            if le(items1[index1], items2[index2]):
                items3.append(items1[index1])
                index1 += 1
            else:
                items3.append(items2[index2])
                index2 += 1
        items3 += items1[index1:]
        items3 += items2[index2:]
        return items3
    
    def main():
        """执行函数"""
        items = [35, 12, 99, 18, 57, 66, 43, 32, 90]
        print('Orignal array:', items)
        print('Array after mergesort: ', merge_sort(items))
    if __name__ == '__main__':
        main()
    

    3:归并排序的时间复杂度、空间复杂度、稳定性

    3.1 时间复杂度

      归并排序中每一次都进行2分递归调用,深度为O(logN),而归并操作中的常数操作为O(N),因此归并排序的时间复杂度是O(N*logN)

    3.2 空间复杂度

      由于归并操作中,每一次要额外申请和所要排序数组一样长的数组空间,所以空间复杂度为O(N)

    3.3 稳定性

      排序算法在归并操作中,当左边子数组的数等于右边子数组的数时,可以先复制左边子数组的数,所以是可以做成稳定的排序算法的。

    展开全文
  • 归并排序基本思想

    2021-01-30 22:02:44
    归并排序 归并,就是把元素合并在一起,在这里我们主要是通过把数据元素分开,当数组元素细化后将它在合并起来。 在归并算法中,主要用到了分治和合并的两种思想。分治:将数组元素细化,分成n多个单个元素序列。...

    归并排序

    归并,就是把元素合并在一起,在这里我们主要是通过把数据元素分开,当数组元素细化后将它在合并起来。

    在归并算法中,主要用到了分治和合并的两种思想。分治:将数组元素细化,分成n多个单个元素序列。合并:一步一步将分治的数组元素合并起来,合并的同时进行顺序排序。

    //归并排序
    void Merge(int TR2[], int TR1[], int i, int m, int n)
    {   // 合并两个数组
        int j, k, l;
        for (j = m + 1, k = i; i <= m && j <= n; k++)
        {
            if (TR2[i] < TR2[j])
                TR1[k] = TR2[i++];
            else
                TR1[k] = TR2[j++];
        }
        if (i <= m)
        {
            for (l = 0; l <= m - i; l++)
                TR1[k + l] = TR2[i + l];
        }
        if (j <= n)
        {
            for (l = 0; l <= n - j; l++)
                TR1[k + l] = TR2[j + l];
        }
    }
    void MSort(int SR[], int TR1[], int num, int Array_length)
    {   // 分治实现
        int merger_len;  // 设置临时变量,记录每次归并的长度
        int TR2[MAX_SIZE + 1]; // 用来合并分治的元素,进行重新排列
        if (num == Array_length) {  // 当分治的每个序列只有一个元素,则停止分治,否则继续分治
            TR1[num] = SR[num];
        }
        else {
            merger_len = (num + Array_length) / 2; 
            // 进行递归方法实现每层分治 
            MSort(SR, TR2, num, merger_len);  // 对分治后的前merger_len进行递归分治 
            MSort(SR, TR2, merger_len + 1, Array_length);  // 对分治后的merger_len后的元素进行递归分治
            Merge(TR2, TR1, num, merger_len, Array_length);  // 对分治部分进行合并
        }
    }
    void MergeSort(SqList* L) // 归并排序主函数
    {
        MSort(L->Array, L->Array, 1, L->length);
    }
    

    对于具体的过程分析我们用图来展示:
    在这里插入图片描述
    在这里插入图片描述

    我们把分治过程和合并过程分开展示(实际过程分治和合并时同时进行的)

    对于分治递归中的红色框图是第一部,紧接着进行合并,随后在惊醒蓝色框图中的分治,接着进行合并,依据这样的方式不断将原数组进行分治合并,便可得到有序的数组序列。

    以上是鄙人对该算法的理解,若与实际算法思想有出入,还请多多指教。

    展开全文
  • 1,基本思想 将两个或两个以上的有序表合并成一个新的有序表。(本文所指内容为两路归并排序) 两路归并:将原始序列中的两个有序表,归并成一个有序表,存在于另一个对象序列中。 迭代的归并排序算法:将初始序列中...

    归并排序

    1,基本思想
    将两个或两个以上的有序表合并成一个新的有序表。(本文所指内容为两路归并排序)

    两路归并:将原始序列中的两个有序表,归并成一个有序表,存在于另一个对象序列中。

    迭代的归并排序算法:将初始序列中的n个对象,看成n个长度为1的有序子序列,先做两两归并,得到int(n/2)个长度为2的归并项(如果n为奇数,则最后一个有序子序列为1);在做两两归并,重复直到最后得到一个长度为n的有序序列。

    2,代码实现
    归并两个序列

    
    //将两个数组进行归并
    void merge(int data[], int res[], int left, int mid, int right)
    {
    	int i = left;//左序列指针
    	int j = mid + 1;//右序列指针
    	int t = 0;
    	while (i <= mid && j <= right) {
    		if (data[i] <= data[j]) {
    			res[t++] = data[i++];
    		}
    		else {
    			res[t++] = data[j++];
    		}
    	}
    	while (i <= mid) {//将左边剩余元素填充进res中
    		res[t++] = data[i++];
    	}
    	while (j <= right) {//将右序列剩余元素填充进res中
    		res[t++] = data[j++];
    	}
    	
    	//将归并后的数组的值赋给data
    	for (i = 0; i < t; i++)
    		data[left + i] = res[i];
    }
    

    递归的归并整个数组

    //递归的对整个数组进行归并排序
    void mergeSort(int data[], int res[], int s, int e)
    {
    	if (s < e)
    	{
    		int m = (s + e) / 2;
    		mergeSort(data, res, s, m);
    		mergeSort(data, res, m + 1, e);
    		merge(data, res, s, m, e);
    	}	
    

    测试

    
    int main()
    {
    	int data[] = {2,5,4,7,5,3,1,9,7,6,2,4};
    	int res[12] = { 0 };
    	cout << "初始序列:" << endl;
    	for (int i = 0; i < 12; ++i)
    		cout << data[i] << " ";
    	cout << endl;
    
    	cout << "每趟后的data:" << endl;
    	mergeSort(data, res, 0,11);
    	cout << "排序后:";
    
    	for (int i = 0; i <12; ++i)
    		cout << res[i] << " ";
    	cout << endl;
    	return 0;
    }
    

    运行结果:
    在这里插入图片描述
    3,性能分析
    ①时间复杂度为O(nlogn)

    一趟归并的时间复杂度为O(n),一共进行int(log2n)趟。

    ②空间复杂度
    o(n)
    需要一个同样大小的辅助数组。

    ③稳定性
    稳定

    展开全文
  •  二路归并排序的主要思想:核心是分治,就是把一个复杂的问题分成两个或多个相同或相似的子问题,然后把子问题分成更小的子问题,直到子问题可以简单的直接求解,最原问题的解就是子问题解的合并。  例题:假设...
  • 归并排序归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到...
  • 文章目录1. 基本思想2. 代码实现2.1 递归实现2.2 优化—非递归实现3...归并排序与快速排序的思想基本一致,唯一不同的是归并排序的基准值是数组的中间元素 快排 Link:[排序算法] 6. 快速排序多种递归、非递归实现及性能
  • 归并排序基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并为一个子序列,经过多次合并后整合为一张有序表。 排序过程如图: 代码如下: ...
  • 归并排序(基本思想以及算法实现)

    千次阅读 2013-10-30 16:20:13
    归并排序是简历在归并操作上的一种有效的排序算法,该算法的递归实现方式是采用分治法的一个典型的应用,它是一个稳定的排序算法,其时间复杂度为O(N*logN),空间复杂度为O(N). 在介绍其具体实现之前,我们先来回忆...
  • 归并排序算法

    2021-01-31 16:21:37
    一、归并排序算法基本思想 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法,将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一...
  • 归并排序-分治思想

    2021-01-20 14:07:14
    归并排序基本思想是: 将待排序的元素分成大小大致的两个子集合, 再分别对两个子集合调用归并排序, 最终将排序好的子集合合并成要求的排序好的集合。 用一个8位的数组举例: 将待排序的数组一分为二直到只剩下一...
  • 基本思想归并排序也是一类高效的基于比较的排序算法,是分治思想的典型应用。它的工作原理是首先将未排序序列分成n份元素个数为1的子序列(个数为1被认为是有序的),然后进行合并,最后子序列数为1即已排序序列。...
  • java实现归并排序思想与实现)

    千次阅读 2019-06-07 14:34:08
    归并排序思想就是先递归分解数组,再合并数组。 将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,...
  • 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段...
  • 6种常用的排序算法的基本思想,性质和比较:快速排序,归并排序,冒泡排序、选择排序、插入排序、希尔排序。 (转载请注明出处) 了解并掌握排序的概念,并熟悉常见的几种排序算法; 掌握常见的几种排序算法的...
  • 原理:将数组分解最小之后,然后合并两个有序数组,基本思想是比较两个数组的最前面的数,谁小就取谁,取完后,将相应的指针后移以为。然后再比较,直到一个数组为空,最后把另一个数组的剩余部分复制过来即可。 ...
  • 归并排序 排序

    2018-01-13 09:13:40
    它的基本思想是:将待排序的数列分成两个小的数列,先对两个子集进行排序,然后进行两个有序子集的合并,形成排序后的数一列,然后对子的处理方法与刚才的处理方法是一致的,直到子集中只存在一个整数为止。...
  • 基本思想 二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]为第一个有序表,arr[center]到arr[right]是第二个有序表...
  • 归并排序基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序、自底向上合并相邻的两个链表。 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和...
  • 归并排序是根据将两个有序数组合并成一个有序数组的思想发展而来,如果两个数组有序,那么只需要依次比较两个数组中的每个数,小的数放进空数组中,并原数组游标向前移动一位进行下一次比较,直到当一个数组的游标...
  • 基本思想  归并排序是建立在二路归并和分治法的基础上的一个高效排序算法,将已有序的子序列合并,得到完全有序的序列;即先使每个子序 列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并...
  • 归并排序

    2019-08-08 18:30:45
    归并排序基本思想算法步骤图解代码示例java 基本思想 归并排序的思想是,利用二分的特性,将序列分成两个子序列进行排序,将排序后的两个子序列归并(合并),当序列的长度为2时,它的两个子序列长度为1,即视为有序...
  • 排序算法之归并排序

    2020-03-10 16:04:08
    归并排序介绍 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer )策略,分治法将问题分(divide)成...归并排序基本思想 (1)分(分解):一开始对当前数组一分...
  • 基本思想归并排序是一种典型的分治思想,把一个无序列表一分为二,对每个子序列再一分为二,继续下去,直到无法再进行划分为止。然后,就开始合并的过程,对每个子序列和另外一个子序列的元素进行比较,依次把小...
  • 详解归并排序算法

    2020-04-27 14:10:54
    归并排序基本思想是: 先将序列一次次分成子序列,直到子序列长度为1; 再将已有序的子序列合并,得到完全有序的序列。 可以看出归并排序运用了 ** 分而治之的思想** 。 例子 输入数组 [ 2, 5, 3 , 10,-3,1 , 6 ...
  • C++实现归并排序

    2021-01-29 19:17:19
    基本思想归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将...
  • 排序算法之归并排序和外部排序

    千次阅读 2018-06-11 09:29:12
      归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,670
精华内容 12,668
关键字:

归并排序基本思想