精华内容
下载资源
问答
  • 排序算法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 稳定性

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

    展开全文
  • 归并排序思想

    2014-02-24 21:22:49
    归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,归并排序将两个已排序的表合并...归并排序基本思想 设两个有序的子序列(相当于输入序列)放在同一

     归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,归并排序将两个已排序的表合并成一个表。
       

    归并排序基本原理

    通过对若干个有序结点序列的归并来实现排序。

    所谓归并是指将若干个已排好序的部分合并成一个有序的部分。

     

    归并排序基本思想

    设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上:array[low..m],array[m + 1..high],先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中,待合并完成后将 temp 复制回 array[low..high]中,从而完成排序。


    在具体的合并过程中,设置 i,j 和 p 三个指针,其初值分别指向这三个记录区的起始位置。合并时依次比较 array[i] 和 array[j] 的关键字,取关键字较小(或较大)的记录复制到 temp[p] 中,然后将被复制记录的指针 i 或 j 加 1,以及指向复制位置的指针 p加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空),此时将另一非空的子序列中剩余记录依次复制到 array 中即可。


    若将两个有序表合并成一个有序表,称为2-路归并。

     

    举例说明"归并排序的排序过程"

    看下面归并排序的两种排序过程


     1.待排序列(14,12,15,13,11,16)

    假设我们有一个没有排好序的序列,那么首先我们使用分割的办法将这个序列分割成一个个已经排好序的子序列。然后再利用归并的方法将一个个的子序列合并成排序好的序列。分割和归并的过程可以看下面的图例。

     

     

                       

                      先"分割"再"合并"

     


    从上图可以看出,我们首先把一个未排序的序列从中间分割成2部分,再把2部分分成4部分,依次分割下去,直到分割成一个一个的数据,再把这些数据两两归并到一起,使之有序,不停的归并,最后成为一个排好序的序列。

     


    2.待排序列(25,57,48,37,12,92,86)

     

     

     


    展开全文
  • 归并排序基本思想: 利用归并的思想,采用经典的分治策略(将问题分divide成一些小的问题后递归求解,治conquer的阶段则将分的阶段得到的各答案修补在一起,即分而治之) 思路: 1.将序列分成子列 直至无法再分解,...

    排序算法——归并排序 -基本思想&推导&优化&算法&测试

    归并排序基本思想
    利用归并的思想,采用经典的分治策略(将问题分divide成一些小的问题后递归求解,治conquer的阶段则将分的阶段得到的各答案修补在一起,即分而治之)
    思路
    1.将序列分成子列 直至无法再分解,对子列排序;
    2.将两个有序子列合并成一个有序序列;
    3.将该有序序列拷贝至原数组覆盖。

    示例:[8,4,5,7,1,3,6,2]
    输出:[1,2,3,4,5,6,7,8]
    归并排序过程

    理解
    最后一次合并:
    归并排序最后一次合并

    package DataStructureAlgorithm.sort;
    
    import java.util.Arrays;
    
    public class sort_mergeSort {
    	public static void main(String[] args) {
    		int[] nums = {8,4,5,7,1,3,6,2};//
    		mergeSort(nums, 0, nums.length-1);
    		System.out.println("after mergeSort: "+Arrays.toString(nums));
    	}
    	
    	//方法:分+合
    	public static void mergeSort(int[] arr,int left,int right) {
    		if(left<right) {
    			int mid=(left+right)/2;//中间索引
    			//向左递归分解
    			mergeSort(arr, left, mid);
    			//向右递归分解
    			mergeSort(arr, mid+1, right);
    			
    			//合并
    			merge(arr, left, mid, right);
    		}
    	}
    	
    	//方法:合
    	/**
    	 * @param arr 待排序数组
    	 * @param left 数组的左侧索引
    	 * @param mid 右侧索引
    	 * @param right 中间索引
    	 */
    	public static void merge(int[] arr,int left,int mid,int right) {
    		int[] temp = new int[arr.length];//做中转的数组
    //		int[] temp = new int[right-left+1];
    		int i=left;//左边有序序列的初始索引为left
    		int j=mid+1;//右边有序序列的初始索引为mid+1
    		int t=0;//temp数组的索引
    		
    		//比较左右两边有序序列,将更小的值放入temp,并将指针后移,直至有一边处理完毕(索引超过末尾元素的下标)
    		while(i<=mid&&j<=right) {
    			if (arr[i]<=arr[j]) {
    				temp[t++]=arr[i++];
    			}else {
    				temp[t++]=arr[j++];
    			}
    		}
    		//完成后只有一边序列还有元素(已经排好序)还未放入temp,将其全部依次拷贝至temp
    		//每拷贝一个数到temp后 就将指针后移,当i指向左边序列的最后一个数时,该数还未被拷贝 故i<=mid
    		while(i<=mid) {
    			temp[t++]=arr[i++];
    		}
    		while(j<=right) {
    			temp[t++]=arr[j++];
    		}
    		
    		//将temp数据拷贝至原数组arr,每次只拷贝已合并的数据
    		t=0;//temp数组的索引
    		int arrLeft=left;//arr数组索引,从其左侧下标开始
    		while(arrLeft<=right) {
    			arr[arrLeft++]=temp[t++];
    		}
    //		for (int k = 0; k < temp.length; k++) {
    //			arr[k+left]=temp[k];
    //		}
    	}
    }
    

    参考:
    https://www.bilibili.com/video/BV1E4411H73v?p=69

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

    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);
    }
    

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

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

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

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

    展开全文
  • 归并排序算法思想

    2019-07-02 14:33:00
    ###### 这次我们来讲述归并排序基本思想归并排序,首先把一个数组中的元素,按照某一方法,先拆分了之后,按照一定的顺序各自排列,然后再归并到一起,使得归并后依然是有一定顺序的 。 归并排序算法可以利用...
  •  二路归并排序的主要思想:核心是分治,就是把一个复杂的问题分成两个或多个相同或相似的子问题,然后把子问题分成更小的子问题,直到子问题可以简单的直接求解,最原问题的解就是子问题解的合并。  例题:假设...
  • 1,基本思想 将两个或两个以上的有序表合并成一个新的有序表。(本文所指内容为两路归并排序) 两路归并:将原始序列中的两个有序表,归并成一个有序表,存在于另一个对象序列中。 迭代的归并排序算法:将初始序列中...
  • java实现归并排序思想与实现)

    千次阅读 2019-06-07 14:34:08
    归并排序思想就是先递归分解数组,再合并数组。 将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,...
  • 归并排序-分治思想

    2021-01-20 14:07:14
    归并排序基本思想是: 将待排序的元素分成大小大致的两个子集合, 再分别对两个子集合调用归并排序, 最终将排序好的子集合合并成要求的排序好的集合。 用一个8位的数组举例: 将待排序的数组一分为二直到只剩下一...
  • 基本思想归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有 序,...
  • 归并排序

    2019-08-08 18:30:45
    归并排序基本思想算法步骤图解代码示例java 基本思想 归并排序的思想是,利用二分的特性,将序列分成两个子序列进行排序,将排序后的两个子序列归并(合并),当序列的长度为2时,它的两个子序列长度为1,即视为有序...
  • 基本思想归并排序也是一类高效的基于比较的排序算法,是分治思想的典型应用。它的工作原理是首先将未排序序列分成n份元素个数为1的子序列(个数为1被认为是有序的),然后进行合并,最后子序列数为1即已排序序列。...
  • 归并排序基本思想是将n个元素的初始序列看成n个成都为1的子序列,两两归并,得到n/2个长度为2或1的子序列,再两两归并,直到得到一个长度为n的有序序列为止。归并排序的核心操作时归并,而整个归并排序的处理过程...
  • 归并排序归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到...
  • 归并排序 基本思想:将两个或两个以上的有序子序列“归并”为一个有序子序列。在内部排序中,通常采用的是2-路归并排序,即将两个位置相邻的有序子序列“归并”为一个有序序列。类似于快排,其使用的也是分治的策略...
  • 归并排序(基本思想以及算法实现)

    千次阅读 2013-10-30 16:20:13
    归并排序是简历在归并操作上的一种有效的排序算法,该算法的递归实现方式是采用分治法的一个典型的应用,它是一个稳定的排序算法,其时间复杂度为O(N*logN),空间复杂度为O(N). 在介绍其具体实现之前,我们先来回忆...
  • 前面的文章讲了二分查找算法,这种算法使用了一种非常常见的思想–“分治思想”。...本文讲解的归并排序就是分治思想的经典应用。一.基本思想分解:给出包含若干个数的一段序列。按照分治思想要...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,285
精华内容 914
关键字:

归并排序基本思想