归并排序与分治法

2022/9/6 23:22:54

本文主要是介绍归并排序与分治法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 分治法的思想
  • 分治模式的步骤
  • 归并排序算法
    • 算法步骤
    • 注意事项
    • 伪代码
      • 归并排序MergeSort()
      • 辅助函数: 合并Merge()
  • 归并排序代码实例
    • 函数声明
    • 函数定义
      • 归并排序
      • 辅助函数:合并
    • 注意事项

分治法的思想

将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。

分治模式的步骤

  1. 分解原问题为若干子问题;

  2. 解决子问题;

  3. 合并子问题的解,形成原问题的解。

归并排序算法

归并排序算法就是使用了分治的思想。

算法步骤

  1. 分解:将待排序的\(n\)个元素的序列分解成各具有\(\frac{n}{2}\)个元素的两个子序列;

  2. 解决:使用归并排序递归地排序两个子序列;

  3. 合并:合并两个已排序好的子序列,最终产生已排序的答案。

注意事项

  1. 当递归到子序列的长度为1时,无需再分解,与对应的子序列合并。因为长度为1的序列可以视为已排序好的序列,即已解决

  2. 函数名声明:下文中,MergeSort()表示归并排序的函数,Merge()表示辅助函数,即实现合并步骤的函数。

伪代码

归并排序MergeSort()

//arr: 待排序的序列(始终为原始主序列)
//head: 第一个元素的下标
//tail: 最后一个元素的下标
//length: 当前(子)序列的长度
MergeSort(arr, head, tail, length){
//特殊情况:长度为1
    //此时是终止条件:当第一个元素和最后一个元素是同一个元素
    //说明递归到此时的子序列是一个长度为1的序列,直接返回。
    if(head == tail)return

//常规处理步骤:分解、解决、合并
    // 分解成两个子问题
    // 1.计算中点
    mid = (head + tail)/2           
    // 2.已中点为界,前后分为两个子序列,分别排序
    MergeSort(arr,head,mid,mid-head+1)
    MergeSort(arr,mid+1,tail,tail-mid)    

    // 合并分别排序好后的子序列,形成原问题的解
    Merge(arr,head,mid+1,length)
}

辅助函数: 合并Merge()

// arr: 待排序的序列(始终为原始主序列)
// head1: 第一个子序列的起始下标
// head2: 第二个子序列的起始下标
// length: (子)序列长度,也就是这两个子序列合并后总的长度
Merge(arr,head1,head2,length){
    //创建一个临时数组,用于暂时存放合并后的子序列
    temp[length]    
    //开始合并
    i = head1
    j = head2
    while(i<=子序列1尾部 && j<=子序列2尾部){
        // 两个子序列是分别排序好了的
        // 依次将较小的数按顺序排放在临时数组temp中
        // 直到有一个子序列已全部进入temp
        if(arr[i]<arr[j]){
            temp.push(arr[i++])
        }else{
            temp.push(arr[j++])
        }        
    }
    //只要有一个序列排完了,就会跳出上面的循环
    //接下来就把另一剩下的序列全部排入temp中
    if(i==head2){
        //1.如果i到达第二子序列头部,说明第二子序列有剩余
        temp.push(rest of subArr2)
    }else{
        //2.这种情况对应:第一子序列有剩余
        temp.push(rest of subArr1)
    }

    // 最后将临时数组temp中已排序好的序列,覆盖掉原始数组arr中的部分
    // 即完成两个子序列的合并
    for i=0 to length{
        arr[head1+i] = temp[i]
    }

    //合并完毕
}

归并排序代码实例

使用C++实现

函数声明

// Merge_sort 归并排序
void Merge_sort(vector<int> &arr,int head, int tail, int length);
// 归并排序 中的 合并操作
void Merge(vector<int> &arr, int head1, int head2, int length);

函数定义

归并排序

void Merge_sort(vector<int> &arr,int head, int tail, int length){
    if(head != tail){
        // 分解成两个子问题
        int m = (head + tail)/2;
        // 两个子问题分别完成操作
        Merge_sort(arr, head, m, m-head+1);
        Merge_sort(arr, m+1, tail, tail-m);
        // 合并两个子问题的解,得到原问题的解
        Merge(arr, head, m+1, length);
    }
}

辅助函数:合并

void Merge(vector<int> &arr, int head1, int head2, int length){
    int i = head1;
    int j = head2;
    vector<int> temp;

    while(i<head2 && j<head1+length){
        if(arr[i]<arr[j]){
            temp.push_back(arr[i++]);
        }else{
            temp.push_back(arr[j++]);
        }
    }

    if(i==head2){
        while(j<head1+length){
            temp.push_back(arr[j++]);
        }
    }else{
        while(i<head2){
            temp.push_back(arr[i++]);
        }
    }

    for(int i = 0; i<length; i++){
        arr[i+head1] = temp[i];
    }
}

注意事项

  1. arr作为原数组,任何排序后重写覆盖的操作都是对arr直接作用的,作为函数参数,应使用引用传递.

  2. 在合并操作Merge函数中,length表示当前(子)序列的长度。因此判断数组是否遍历到结尾处的依据不能是index < length应该是head1+index < length.



这篇关于归并排序与分治法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程