精华内容
下载资源
问答
  • 2022-03-10 23:01:40

    **

    归并排序算法

    **


    一、基本概念

    归并算法一共分成两个部分:

    1. 分治
    2. 归并

    分治:将需要排序的一组数不断地一分为二,直至每组只有一个数
    归并:将排好序的两组数不停地合并起来,在还原成一组数的过程中,完成排序,即合并完成,排序完成

    示意图如下:
    在这里插入图片描述
    为什么出现归并排序呢?
    因为它速度快,属于以空间换时间,所以要根据具体情况来决定是否使用,当然一般情况下是没有问题的。

    二、具体思路

    归并排序算法,采用递归的思路:
    • 先考虑一步

    • 1.此时仅需要比较两个数组,设为arr1[],arr2[]

    • 2.比较arr1[i]和arr2[j],小的填入result[k],大的不动与另一组的下一个比较

    • 3.循环下去,直至其中一个数组全部填入result[]

    • 4.再将另一个数组剩下的部分依次按序填入result即可

    • 剩下的部分递归实现

    • 1.首先判断左是否大于等于右,是则递归结束,否则继续

    • 2.将需要排序的数组分治

    • 3.分治过后进行归并排序

    三、编写代码

    1.归并算法

    void merge(int *arr,int left,int mid,int right)//单步
    {
    	int len=right-left+1;
    	int result[len];//最终的排序数组
    	int k=0;
    	int i=left;
    	int j=mid+1;
    	//此时将数组分成两个部分:left->mid 和 mid+1->right
    	while(i<=mid && j<=right)//循环直至一个数组全部填入
    	{	//将进行比较的小的数组元素填入result[]
    		if(arr[i]<=arr[j]) result[k++]=arr[i++];
    		else result[k++]=arr[j++];
    	}
    	//前一半数组已经全部填入
    	if(i==mid+1) while(j<=right) result[k++]=arr[j++];//将后一半数组依次按序填入
    	//后一半数组已经全部填入
    	if(j==right+1) while (i<=mid) result[k++]=arr[i++];//将前一半数组依次按序填入
    	//将排好序的结果重新填入arr[]
    	for(i=left,j=0;j<k;i++,j++) arr[i]=result[j];
    }
    

    2.递归分治归并的过程

    void mergeSort(int *arr,int left,int right)//递归实现
    {
    	int mid=(left+right)/2;//中间位置
    	if(left>=right) return;//左大于等于右,递归结束
    	//将数组分成两部分进行归并排序
    	mergeSort(arr,left,mid);
    	mergeSort(arr,mid+1,right);
    	//将排好序的两部分合并
    	merge(arr,left,mid,right);
    }
    

    2.完整代码

    #include <stdio.h>
    
    /*	@author:Yingchen Liu
    	归并排序算法
    	采用递归的思路:
    		先考虑一步
    	1.此时仅需要比较两个数组,设为arr1[],arr2[]
    	2.比较arr1[0]和arr2[0],小的填入result[0],大的不动与另一组的下一个比较
    	3.循环下去,直至其中一个数组全部填入result[]
    	4.再将另一个数组剩下的部分依次按序填入result即可
    		剩下的部分递归实现
    	1.首先判断左是否大于等于右,是则递归结束,否则继续
    	2.将需要排序的数组分治
    	3.分治过后进行归并排序  */
    void merge(int *arr,int left,int mid,int right)//单步
    {
    	int len=right-left+1;
    	int result[len];//最终的排序数组
    	int k=0;
    	int i=left;
    	int j=mid+1;
    	//此时将数组分成两个部分:left->mid 和 mid+1->right
    	while(i<=mid && j<=right)//循环直至一个数组全部填入
    	{	//将进行比较的小的数组元素填入result[]
    		if(arr[i]<=arr[j]) result[k++]=arr[i++];
    		else result[k++]=arr[j++];
    	}
    	//前一半数组已经全部填入
    	if(i==mid+1) while(j<=right) result[k++]=arr[j++];//将后一半数组依次按序填入
    	//后一半数组已经全部填入
    	if(j==right+1) while (i<=mid) result[k++]=arr[i++];//将前一半数组依次按序填入
    	//将排好序的结果重新填入arr[]
    	for(i=left,j=0;j<k;i++,j++) arr[i]=result[j];
    }
    
    void mergeSort(int *arr,int left,int right)//递归实现
    {
    	int mid=(left+right)/2;//中间位置
    	if(left>=right) return;//左大于等于右,递归结束
    	//将数组分成两部分进行归并排序
    	mergeSort(arr,left,mid);
    	mergeSort(arr,mid+1,right);
    	//将排好序的两部分合并
    	merge(arr,left,mid,right);
    }
    
    int main()
    {
    	int i;
    	int testArr[]={10,9,1,4,13,6,7,9,21,0};
    	mergeSort(testArr,0,9);
    	for(i=0;i<10;i++) printf("%d ",testArr[i]);
    	return 0;
    }
    

    四、总结评价

    时间复杂度为O(nlogn)
    空间复杂度为O(n)
    归并排序比较占用内存,但却是一种效率高且稳定的算法。

    有问题欢迎各位大佬指出
    算法系列将持续更新,欢迎关注,一起学习

    更多相关内容
  • 本文实例讲述了C++实现自顶向下的归并排序算法。分享给大家供大家参考,具体如下: 一. 算法描述 自顶向下的归并排序:采用分治进行自顶向下的程序设计方式,分治的核心思想就是分解、求解、合并。 1. 先将长度...
  • 归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治(Divide and Conquer)的一个非常典型的应用。 算法步骤: 1. 申请空间,使其大小为两个已经排序序列之...
  • C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。
  • 归并排序算法

    千次阅读 2021-01-12 10:17:42
    归并排序(merge sorting)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide and conquer)策略。分治策略将问题分解(divide)分解为一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段...

    一、归并排序介绍

    归并排序(merge sorting)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide and conquer)策略。分治策略将问题分解(divide)分解为一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案合并在一起,即分而治之。

    归并排序的时间复杂度为 O(nlogn)。

    二、归并排序的思想

    2.1 归并排序的基本思想

    归并排序的基本思想如下图所示:

    在这里插入图片描述

    从上图可以看出来:归并排序主要分为两个部分——分、治。

    对于分的部分,没有什么好研究的,简单来说就是把 n 个元素组成的一个序列最终分解为 n 个序列,每个序列只有一个元素。

    对于治(也即合并)的部分,则是归并排序中最复杂的内容。

    从上图可以看出来,由 8 个元素组成的序列分解完毕之后,在治的部分共合并了 7 次。那么这 7 次合并过程究竟是如何进行的呢?下面将具体讲解。

    2.2 归并的基本步骤

    从归并排序的基本思想图中我们可以得知:合并都是发生在相邻的两个有序子序列之间的。因此,我们只需要掌握有序子序列的合并过程,便可以推出完整的归并过程。

    对于两个有序子序列的合并过程,基本都是按照以下步骤进行的:

    1. 首先为左子序列附设一个指针 left 指向左子序列的第一个元素,为右子序列附设一个指针 right 指向右子序列的第一个元素;
    2. 附设一个临时数组 temp 用于临时存储排序后的结果;
    3. 右子序列的指针 right 向右移动,在移动的过程中如果指向的元素小于 left 指向的元素,则将 arr[right] 记录在临时数组 temp 中;
    4. 若右子序列的指针 right 移动过程指向的元素大于 left 指向的元素,则将 arr[left] 追加到临时数组 temp 中;
    5. 左子序列的指针 left 再向右移动,若移动过程中指向的元素小于 right 指向的元素,则将 arr[left] 追加到 temp 中;
    6. 若左子序列的指针 left 向右移动过程中指向的元素大于 right 指向元素,则将 arr[right] 追加到 temp 中;
    7. 循环执行 3~6步,直到其中一个子序列中的元素都被记录完毕;然后将尚存在元素的子序列按顺序追加在 temp 数组中,
    8. temp 数组中的元素复制到原序列 arr 中,则两个有序子序列的合并正式完成。

    从上面的步骤我们不难看出:它和两个有序链表的合并思想基本是一致的

    【举例说明】

    下面将用两个例子来具体描述一下两个有序序列的合并的过程。

    以两个有序子序列 [4,8][5,7] 合并为例,过程如下:

    在这里插入图片描述

    再以两个有序子序列 [4,5,7,8][1,2,3,6] 合并为例,过程如下:

    在这里插入图片描述

    三、归并排序的代码实现

    【案例需求】

    假设待排序序列如下:

    int[] arr = {8,4,5,7,1,3,6,2};
    

    要求将上面的序列使用归并排序算法按照从小到大顺序排序。

    【思路分析】

    我们知道,归并排序中最复杂的代码就是两个有序子序列的合并过程,根据 2.2 示例中的图解,我们可以写出两个有序子序列合并的代码如下:

    /**
         * 合并两个有序序列
         * @param arr   两个子序列组成的原始数组,arr[left]~arr[mid] 为左子序列、arr[mid+1]~arr[last] 为右子序列
         * @param left  指向左子序列的首个元素
         * @param mid   指向左子序列的末尾元素
         * @param last  指向待归并序列的最后一个元素
         * @return void
         */
    public static void merge(int[] arr, int left, int mid, int last){
        int i = left, j = mid + 1;  // i 为左子序列起点,j 为右子序列起点
        int m = mid, n = last;      // m 为左子序列终点,n 为右子序列终点
        int t = 0;                  // 临时数组索引
    	int[] temp = new int[arr.length];	// 临时数组
        /*
           把两个子序列组成的数组元素按照规则放入到 temp 数组中,
           直到有一个子序列的元素被读完。
         */
        while(i<=m && j<=n) {
            if (arr[j] <= arr[i]) {
                temp[t] = arr[j];
                t += 1;
                j += 1;
            } else {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            }
        }
        /* 哪个子序列元素有剩余,就都读取到 temp 中 */
        while(i<=mid){  // 如果是左子序列还有剩余元素
            /* 把剩余元素都填充到 temp */
            temp[t]=arr[i];
            t+=1;
            i+=1;
        }
        while(j<=last){    // 如果是右边的序列元素有剩余
            /* 把剩余元素都填充到 temp */
            temp[t]=arr[j];
            t+=1;
            j+=1;
        }
        /* 从 temp 数组中 copy 数据到原数组 */
        for (i=0; i<t; i++){
            arr[left + i] = temp[i];
        }
    }
    

    合并的代码如上面所示。对于分解的代码则比较简单,就是递归调用归并方法,最后调用合并方法。

    【代码实现】

    完整的归并排序代码如下:

    /**
     * 归并排序
     * @param arr   待归并排序序列
     * @param left  左子序列的起点
     * @param last  右子序列的终点
     */
    public static void mergeSort(int[] arr, int left, int last) {
        if(left < last) {
            int mid = (left + last) / 2;        	// 中间索引
            mergeSort(arr, left, mid);			// 左子序列递归 
            mergeSort(arr, mid + 1, last );	// 右子序列递归
            merge(arr, left, mid, last);		// 合并
        }
    }
    
    /**
     * 合并两个有序序列
     * @param arr   两个子序列组成的原始数组,arr[left]~arr[mid] 为左子序列、arr[mid+1]~arr[last] 为右子序列
     * @param left  指向左子序列的首个元素
     * @param mid   指向左子序列的末尾元素
     * @param last  指向待归并序列的最后一个元素
     * @return void
     */
    public static void merge(int[] arr, int left, int mid, int last){
        int i = left, j = mid + 1;  // i 为左子序列起点,j 为右子序列起点
        int m = mid, n = last;      // m 为左子序列终点,n 为右子序列终点
        int t = 0;                  // 临时数组索引
    	int[] temp = new int[arr.length];	// 临时数组
        /*
        	把两个子序列组成的数组元素按照规则放入到 temp 数组中,直到有一个子序列的元素被读完。
         */
        while(i<=m && j<=n) {
            if (arr[j] <= arr[i]) {
                temp[t] = arr[j];
                t += 1;
                j += 1;
            } else {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            }
        }
        /* 哪个子序列元素有剩余,就都读取到 temp 中 */
        while(i<=mid){  // 如果是左子序列还有剩余元素
            /* 把剩余元素都填充到 temp */
            temp[t]=arr[i];
            t+=1;
            i+=1;
        }
        while(j<=last){    // 如果是右边的序列元素有剩余
            /* 把剩余元素都填充到 temp */
            temp[t]=arr[j];
            t+=1;
            j+=1;
        }
        /* 从 temp 数组中 copy 数据到原数组 */
        for (i=0; i<t; i++){
            arr[left + i] = temp[i];
        }
        
        System.out.println("第" + ++x + "次合并后:" + Arrays.toString(temp));
    }
    

    最终运行结果如下:

    在这里插入图片描述

    从运行结果可以看到,8 个元素的序列最终进行了 7 次合并,其中每次合并的结果可以对照归并排序的基本思想自行体会。

    展开全文
  • 主要介绍了C语言实现排序算法归并排序,对归并排序的原理及实现过程做了非常详细的解读,需要的朋友可以参考下
  • 根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
  • 十大经典排序算法-归并排序算法详解

    万次阅读 多人点赞 2020-06-19 15:23:51
    归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法归并排序对序列的元素进行逐层折半分组,然后从最小分组开始比较排序,合并成一个大的分组,逐层进行,最终所有的元素都是有序的 2.算法原理 这是一...
    十大经典排序算法

    一、什么是归并排序

    1.概念

    归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法,归并排序对序列的元素进行逐层折半分组,然后从最小分组开始比较排序,合并成一个大的分组,逐层进行,最终所有的元素都是有序的

    2.算法原理

    这是一个无序数列:4、5、8、1、7、2、6、3,我们要将它按从小到大排序。按照归并排序的思想,我们要把序列逐层进行拆分
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WPmtncWG-1592551094225)(./快速1.png)]
    序列逐层拆分如下
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nvJMNUvk-1592551094228)(./归并1.png)]
    然后从下往上逐层合并,首先对第一层序列1(只包含元素4)和序列2(只包含元素5)进行合并

    创建一个大序列,序列长度为两个小序列长度之和,p1、p2指针分别指向两个小序列的第一个元素,p指向大序列的第一个元素
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oHexl6py-1592551094230)(./归并2.png)]
    比较p1、p2指向的元素,4小于5,将4填入p指向的元素,p、p1往右移一位
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-51zK7Ns2-1592551094231)(./归并3.png)]
    此时,序列1已经没有元素,将序列2的元素依次填入大序列中
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3QMWsy0X-1592551094232)(./归并4.png)]
    序列8和1,序列7和2,序列6和3,用同样的方式填入新的序列
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rWPH114Z-1592551094235)(./归并5.png)]
    接着,以4、5为序列1,1、8为序列2,继续进行合并

    创建一个序列长度为4的大序列,p1指向序列1的第一个元素4,p2指向序列2的第一个元素1,p指向大序列的第一个元素
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oNDu9TdZ-1592551094236)(./归并6.png)]
    4和1比较,4大于1,1填入p指向的元素,p、p2往右移一位
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nnIhGQnf-1592551094237)(./归并7.png)]
    4和8比较,4小于8,4填入p指向的元素,p、p1往右移一位
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YQxfZV0b-1592551094239)(./归并8.png)]
    5和8比较,5小于8,5填入p指向的元素,p、p1往右移一位
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wFyyXNrc-1592551094240)(./归并9.png)]
    自此,序列1已经没有元素,将序列2的元素依次填入大序列中
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Kiyj3tbz-1592551094241)(./归并10.png)]
    序列2、7和序列3、6以同样的方式合并成新的序列
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-u26c0pOr-1592551094244)(./归并11.png)]
    最后,将序列1、4、5、8和序列2、3、6、7以同样的方式继续合并成新的序列
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tK2Rw29s-1592551094245)(./归并12.png)]
    至此所有的元素都是有序的

    3.算法实现

    function sort(arr, startIndex = 0, endIndex = arr.length - 1) {
        // 递归结束条件:startIndex大于等于endIndex的时候
        if (startIndex >= endIndex) {
            return;
        }
    
        // 折半递归
        let midIndex = parseInt((startIndex + endIndex) / 2);
        sort(arr, startIndex, midIndex);
        sort(arr, midIndex + 1, endIndex);
        // 将两个有序的小数组,合并成一个大数组
        merge(arr, startIndex, midIndex, endIndex);
    }
    
    function merge(arr, startIndex, midIndex, endIndex) {
        // 新建一个大数组
        let tempArr = [];
        let p1 = startIndex;
        let p2 = midIndex + 1;
        let p = 0;
    
        // 比较两个有序小数组的元素,依次放入大数组中
        while (p1 <= midIndex && p2 <= endIndex) {
            if (arr[p1] <= arr[p2]) {
                tempArr[p++] = arr[p1++];
            } else {
                tempArr[p++] = arr[p2++];
            }
        }
    
        // 右侧小数组已排序完毕,左侧小数组还有剩余,将左侧小数组元素依次放入大数组尾部
        while (p1 <= midIndex) {
            tempArr[p++] = arr[p1++];
        }
        // 左侧小数组已排序完毕,右侧小数组还有剩余,将右侧小数组元素依次放入大数组尾部
        while (p2 <= endIndex) {
            tempArr[p++] = arr[p2++];
        }
    
        for (let i = 0; i < tempArr.length; i++) {
            arr[i + startIndex] = tempArr[i];
        }
    }
    
    let arr = [4, 5, 8, 1, 7, 2, 6, 3];
    sort(arr);
    console.log(arr);
    

    二、归并排序算法特点

    1.时间复杂度

    归并排序算法每次将序列折半分组,共需要logn轮,因此归并排序算法的时间复杂度是O(nlogn)

    2.空间复杂度

    归并排序算法排序过程中需要额外的一个序列去存储排序后的结果,所占空间是n,因此空间复杂度为O(n)

    3.稳定性

    归并排序算法在排序过程中,相同元素的前后顺序并没有改变,所以归并排序是一种稳定排序算法

    展开全文
  • 本文实例讲述了Python实现的归并排序算法。分享给大家供大家参考,具体如下: 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治(Divide and Conquer)的一个非常典型的应用。 将已有序的子序列...
  • java实现归并排序算法

    2020-09-03 20:00:23
    归并排序:是建立在归并操作上的一种有效的排序算法。该算法是采用分治(Divide and Conquer)的一个非常典型的应用。 本文我们就来详细的探讨下。
  • 归并排序是建立在归并操作上的一种有效、稳定的排序算法,该算法采用非常经典的分治(分治可以通俗的解释为:把一片领土分解,分解为若干块小部分,然后一块块地占领征服,被分解的可以是不同的政治派别或是其他...

    归并排序是建立在归并操作上的一种有效、稳定的排序算法,该算法采用非常经典的分治法(分治法可以通俗的解释为:把一片领土分解,分解为若干块小部分,然后一块块地占领征服,被分解的可以是不同的政治派别或是其他什么,然后让他们彼此异化),归并排序的思路很简单,速度呢,也仅此于快速排序,接下来我们详细的看看归并排序的过程。
    基本思路:
    第一步:将序列中待排序数字分为若干组,每个数字分为一组。
    第二步:将若干组两两合并,保证合并的组都是有序的。
    第三步:重复第二步的操作,直到剩下最后一组即为有序数列。
    详细步骤:
    首先将数组中待排序数字分成若干组,每个数字为一组

    相邻的两组进行对比,并且两两合并,保证合并后都是有序的数列,i(数字8)>  j(数字4)需要交换位置(最终呈现一个升序的数组),经过比较合并后两个数存入一个空的指针里


    其他组按照此方法依次合并,从8个组合并成4个组

     继续相邻的两个组进行合并

      定义两个变量i,j分别代表P1里的第一个值(4)和P2里的第一个值(5),i和j进行比较,i < j(4 < 5),将数字4移入p中,i向后移动一位

     i和j进行比较,i > j(8 > 5 ),将数字5移动到p中(4的后一位),j后移一位

    i 和j继续进行比较,i > j (8 > 7),将数字7移动到p中(5的后一位),p2中没有待排序的数字,所以比较结束,p1中剩下的数字移动到p中(7的后一位),合并结束。旁边两个序列按照同样的方式进行合并,最后得到两个有序序列,将这两个有序序列通过上面的方式继续进行合并

     i和j进行比较,i > j(4 > 1),i不动,p2中的数字1移动到p中,j向后移动一位

     i继续和j比较,i > j(4 > 2),数字2移动到p中(1的后一位),j向后移动一位

    i继续和j比较,i > j(4 > 3),数字3移动到p中(2的后一位),j向后移动一位

     i继续和j比较,i < j(4 <6),数字4移动到p中(3的后一位),i向后移动一位

     i继续和j比较,i < j(5 < 6),数字5移动到p中(4的后一位),i向后移动一位


    i继续和j比较,i > j(7 >6),数字6移动到p中(5的后一位),p2中已经没有待排序的数字,所以比较结束,p1中剩下的数字移动到p中(6的后面)


    最后得到一个有序的数列 ,归并排序结束源代码 如下:

    #include <stdio.h>
    #include <stdlib.h>
    
    void G_qsort(int *a,int first,int mid,int last,int *temp)
    {
        int n = mid,m = last;
        int k = 0;
        int i = first,j = mid+1;
        while(i <= n && j <= m)  // 两边同时进行
        {
            if(a[i] <= a[j])  //  i和j进行比较
            {
                temp[k++] = a[i++];  // 如果i <= j,则i的值移动到temp里面
            }
            else
            {
                temp[k++] = a[j++];   // 如果i > j,则j的值移动到temp里面
            }
        }
        while(i <= n) // 学到牛牛 www.xuedaon.com
        {
            temp[k++] = a[i++];
        }
        while(j <= m)
        {
            temp[k++] = a[j++];    
        }
        for(i = 0; i < k; i++)
        {
            a[first+i] = temp[i];
        }
    }
    
    void G_sort(int *a,int first,int last,int *temp)
    {
        if(first < last)  //  当同时到达一个数时结束判断
        {
            int mid = (first+last)/2;  // 找到中间值
            G_sort(a,first,mid,temp);  //  递归函数左边
            G_sort(a,mid+1,last,temp);   // 右边
            G_qsort(a,first,mid,last,temp);  // 进行排序
        }
    }
    
    int sort(int *a,int n)
    {
        int *p = malloc(n);  // 分配内存大小
        if(p == NULL) 
        {
            return -1;
        }
        else
        {
            free(p);  
            G_sort(a,0,n-1,p);  // 调用函数传参,0和n-1为第一个数和最后一个数下标
            p = NULL;
            return 1;
        }
        
    }
    int main()
    {
        int a[8]={8,4,5,7,1,3,6,2};
        int i;
        sort(a,8); // 调用函数传参
        for(i = 0; i < 8; i++)
        {
            printf("%d",a[i]);
        }
        printf("\n");
    
        return 0;
    }
    展开全文
  • 归并排序算法实现

    2017-03-16 16:01:16
    根据算法导论实现的归并排序算法
  • 今天学了折半查找算法,折半查找是蛮简单的,但是归并排序我就挺懵比,看教材C语言写的归并排序看不懂,后来参考了别人的博客,终于搞懂了。 折半查找 先看下课本对于 折半查找的讲解。注意了,折半查找是对于有序...
  • 本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治分为若干个有序子序列,然后每两个子序列合并...
  • 关于python的算法一直都是让我们又爱又恨,但是如果可以灵活运用起来,对我们的编写代码过程,可以大大提高效率,针对算法之一“归并排序”的灵活掌握,一起来看下吧~ 归并算法——小试牛刀 实例内容: 有 1 个无序...
  • 主要介绍了C语言演示对归并排序算法的优化实现,归并排序的最差时间复杂度为(nlog n),最优时间复杂为(n),存在可以改进的空间,需要的朋友可以参考下
  • C语言归并排序算法

    千次阅读 2022-02-05 22:17:31
    今天我要和大家分享的是一个排序算法——归并算法。 如果说快速排序是让一个数组分成很多小集体进行排序,那么归并排序就是让很多有序的小集体合成一个有序数组。 思路: 如果是升序,对于每一个数字来说其本身是...
  • 主要介绍了C++实现自底向上的归并排序算法,结合实例形式较为详细的分析总结了自底向上的归并排序算法的原理与具体实现技巧,需要的朋友可以参考下
  • 归并排序左半边,归并排序右半边,合并 void merge_sort(vector<int> &nums,vector<int> reg,int start,int end){ if(start>=end) return ; int mid=(end-start)/2+start; int start1=start,...
  • 二分归并排序算法

    千次阅读 2021-03-29 15:29:39
    二分归并排序算法原理(假设数组A中共有n个元素): 将数组A中n个元素看成n个独立的子序列,因此每个子序列的长度为1,然后两两合并,得到[n/2]个长度为2或1(注意如果n为奇数时,就会出现多出一个元素无法与其他元素...
  • 本文实例讲述了Java分治归并排序算法。分享给大家供大家参考,具体如下: 1、分治 许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些...
  • 归并排序算法(C语言实现)

    千次阅读 2021-03-01 10:43:06
    归并排序的步骤: 1.将序列分成左右两部分 2.排序左序列,排序右序列 3.合并两个有序的序列 需要申请额外的空间放临时的有序序列 #include<stdio.h> #include<string.h> #include<stdlib.h> ...
  • 详解归并排序算法

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

    2020-12-20 18:15:53
    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段...
  • 主要介绍了Python编程中归并排序算法的实现步骤详解,归并排序的平均时间复杂度为(nlog n),需要的朋友可以参考下
  • 所以归并排序属于稳定的排序算法。 每次分别排左半边和右半边,不断递归调用自己,直到只有一个元素递归结束,开始回溯,调用 merge 函数,合并两个有序序列,再合并的时候每次给末尾追上一个最大 int 这样就不怕...
  • 归并排序算法一、归并排序的概念二、原地归并的抽象方法(一)、原地归并的抽象方法的概念(二)、原地归并的抽象方法的代码示例三、自顶向下的归并排序(一)、自顶向下的归并排序的概念(二)、自顶向下的归并排序...
  • Python实现归并排序算法归并排序1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。分治的基本思想将原问题分解为若干个规模更小但...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 125,965
精华内容 50,386
关键字:

归并排序算法

友情链接: SAR-imaging.rar