归并排序与分治法

目录

• 分治法的思想
• 分治模式的步骤
• 归并排序算法
  • 算法步骤
  • 注意事项
  • 伪代码
    • 归并排序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.