算法基础之归并排序-创新互联

本文概述:
  • 文章以归并排序为题,向读者介绍了其整体思路、时间复杂度分析、核心代码算法思路,并提供了完整实现代码(C++ & Java)。
样例展示:

image-20221223151949764

创新互联专注于耿马企业网站建设,响应式网站,商城建设。耿马网站建设公司,为耿马等地区提供建站服务。全流程按需规划网站,专业设计,全程项目跟踪,创新互联专业和态度为您提供的服务整体思路:先分治,再合并
  • 算法整体上:

    • 将原数组,以数组下标中点为分界点,一分为二
  • 递归的每一层:

    • 数据来源:nums[left,right],分出的两部分nums[left,mid]nums[mid + 1,right]

    • 排序操作:遍历两部分,按照大小,将其放入临时数组temp[],注意下标从0 开始;

    • 放回操作:将排好序的临时数组元素放回本层原数组

      • 遍历的区间的对应关系应为

        • nums:[left,right]
        • temp:从零开始,因为在每一层的排序时,temp 都是从0 开始的
时间复杂度分析
  • 归并是稳定的,在递归排序时,每一趟会将原数组划分为两份,对于N 个数据,总计为logN层;
  • 对每一层,均会进行合并(扫描一遍,每一次会扫描right - left + 1个数),因此总体为N * logN
核心代码算法思路:一共四步
  • 第一步:确定分界点下标

    int mid = (left + right) >>1;

  • 第二步:向下递归,将本层数据以分界点为线,一分为二

    merge_sort(nums,left,mid),merge_sort(nums,mid + 1,right);

  • 第三步:将由本层分裂出的左右两部分数组按照大小进行合并

    • 注意:第二步是递归向下的过程,此时递归深度不断加深,第三步是递归向上,此时为递归回溯操作
    //开始合并两个数组
    int k = 0,startA = left,startB = mid + 1;
    while(startA<= mid && startB<= right)
    {if(nums[startA]< nums[startB]) temp[k++] = nums[startA++];
        else(temp[k++] = nums[startB++]);
    }
    ​
    while(startA<= mid)    temp[k++] = nums[startA++];
    while(startB<= right)    temp[k++] = nums[startB++];
  • 第四步:将本层存放在临时数组中的元素,放回原数组

    • 注意:此时,处理的是递归中的某一层,且临时数组中保存的数据是排好序的;

    • 因此,遍历的区间的对应关系应为

      • nums:[left,right]
      • temp:从零开始,因为在每一层的排序时,temp 都是从0 开始的

    for(int startA = left,startB = 0;startA<= right;startA++,startB++) nums[startA] = temp[startB];

代码实现:C++
#include​
using namespace std;
​
const int N  = 1e6 + 10;
​
int n;
int nums[N], temp[N];
​
void merge_sort(int nums[],int left,int right)
{if(left >= right)   return;//递归出口
​
    //本层递归逻辑
    int mid = (left + right) >>1;//确定分界点下标
    merge_sort(nums,left,mid),merge_sort(nums,mid + 1,right);//向下递归
​
    //开始合并两个数组
    int k = 0,startA = left,startB = mid + 1;
    while(startA<= mid && startB<= right)
    {if(nums[startA]< nums[startB]) temp[k++] = nums[startA++];
        else(temp[k++] = nums[startB++]);
    }
​
    while(startA<= mid)    temp[k++] = nums[startA++];
    while(startB<= right)    temp[k++] = nums[startB++];
​
    //将本段区间的有序结果放回原数组
    for(int startA = left,startB = 0;startA<= right;startA++,startB++) nums[startA] = temp[startB];
​
    //for (int i = 0;i< n;i++)   nums[i] = temp[i];注意,放回的是本段区间[left,right] 不是整个区间
​
}
​
int main()
{scanf("%d",&n);
    for(int i = 0;i< n;i++) scanf("%d",&nums[i]);//处理IO
​
    merge_sort(nums,0,n - 1);//进行归并排序
​
    for(int i = 0;i< n;i++)    printf("%d ",nums[i]);
​
}
​
​
​
作者:WAsbry
链接:https://www.acwing.com/activity/content/code/content/353277/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
代码实现:Java
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Scanner;
​
public class MergeSort {​
    //核心函数:使用归并排序对给定数组的指定区间进行升序排序
    public void merge_sort(int[] nums, int left, int right){//递归出口
        if (left >= right)  return;
​
        //本层递归逻辑
        int mid = (left + right) >>1;//选择本层递归数组下标中点作为分界
        merge_sort(nums,left,mid);
        merge_sort(nums,mid + 1,right);//向下递归
​
        //将本层原数组分裂出的两部分升序合并在临时数组中
        int startA = left,startB = mid + 1;//确定两部分起点
        ArrayListtemp = new ArrayList<>();//临时集合
​
        while (startA<= mid &&startB<= right){if(nums[startA]< nums[startB]){temp.add(nums[startA++]);
            }else {temp.add(nums[startB++]);
            }
        }
        while (startA<= mid){temp.add(nums[startA++]);
        }
        while (startB<= right){temp.add(nums[startB++]);
        }
​
        //将临时数组中的升序序列放回原数组
        for(startA = left,startB = 0;startA<= right;startA++,startB++){nums[startA] = temp.get(startB);
        }
    }
​
    //辅助函数:打印给定数组所有元素
    public void printArray(int[] nums){for (int i = 0;i< nums.length;i++){System.out.print(nums[i] + " ");
        }
    }
​
    //辅助函数:根据键盘输入初始化数组nums,并返回nums;输入:1,2,3;返回nums{1,2,3}
    public int[] dealIO(){Scanner sc = new Scanner(new BufferedInputStream(System.in));
        String str = sc.next();
        String[] strArray = str.split(",");
​
        int[] nums = new int[strArray.length];
        for (int i = 0;i< strArray.length;i++){nums[i] = Integer.valueOf(strArray[i]);
        }
​
        return nums;
    }
​
​
    public static void main(String[] args) {MergeSort ma = new MergeSort();
        int[] nums = ma.dealIO();
        ma.merge_sort(nums,0,nums.length - 1);
        ma.printArray(nums);
    }
}
​
运行截图:Java

image-20221224135817213

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文题目:算法基础之归并排序-创新互联
当前路径:http://pwwzsj.com/article/jsegc.html