算法导论之归并排序

Myth丶恋晨 2022-03-21 11:12 193阅读 0赞

归并排序的思想就是分治法；

分治法：为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。

分治模式在每层递归时都有三个步骤：

一，**分解**原问题为若干子问题。

二，**解决**这些子问题，递归求解各子问题。

三，**合并**这些子问题的解成原问题的解。

***了解了分治法之后，我们再来看下归并排序：***

1，**分解：分解待排序的n**个元素的序列各具n/2个元素的两个子序列。

**2，解决：**使用归并排序递归地排序两个子序列。

**3，合并：**合并两个已排序的子序列以产生已排序的答案。

下面先附上代码：

//
    //  main.cpp
    //  算法导论
    //
    //  Created by SJCHEN on 2019/1/19.
    //  Copyright © 2019 SJCHEN. All rights reserved.
    //
    #include <iostream>
    using namespace std;
    #define MAX 100000//定义哨兵
    int A[] = {5,2,4,7,1,3,2,6};
    int len = sizeof(A)/sizeof(A[0]);
    void printA()
    {
        for (int i = 0; i < len); ++i) {
            cout << A[i] << " ";
        }
        cout << endl;
    }
    
    void Merge(int start,int mid, int end)
    {
        int LeftSortLen = mid - start + 1;//左边需要排序的个数
        int RightSortLen = end - mid;//右边------
        int *ALeft = new int[LeftSortLen + 1];//增加一个1用来存放哨兵
        int *ARight = new int[RightSortLen + 1];//右边数组
        for (int i = 0; i < LeftSortLen; ++i)
            ALeft[i] = A[start + i];
        for (int j = 0; j < RightSortLen; ++j)
            ARight[j] = A[mid + j + 1];
        ALeft[LeftSortLen] = MAX;//哨兵
        ARight[RightSortLen] = MAX;
        int i = 0, j = 0;
        for (int k = start; k <= end; ++k) {
            if (ALeft[i] <= ARight[j]) {
                A[k] = ALeft[i];
                i++;
            }
            else {
                A[k] = ARight[j];
                j++;
            }
        }
        delete[] ALeft;
        delete[] ARight;
    }
    
    void MergeSort(int start, int end)
    {
        if (start >= end) return;
        int mid = (start + end) / 2;
        MergeSort(start, mid);
        MergeSort(mid + 1, end);
        Merge(start, mid, end);
    }
    
    int main()
    {
        MergeSort(0,len - 1);
        printA();
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70][]

下面是不使用哨兵的做法

void Merge(int start,int mid, int end)
    {
        int LeftSortLen = (mid - start + 1);
        int RightSortLen = end - mid;
        int *ALeft = new int[LeftSortLen];
        int *ARight = new int[RightSortLen];
        for (int i = 0; i < LeftSortLen; ++i)
            ALeft[i] = A[start + i];
        for (int j = 0; j < RightSortLen; ++j)
            ARight[j] = A[mid + 1 + j];
        int i = 0, j = 0;
        for (int k = start; k <= end; ++k) {
            if (i < LeftSortLen && j < RightSortLen) {
                if (ALeft[i] <= ARight[j]) {
                A[k] = ALeft[i];
                i++;
                continue;
                }
                else {
                    A[k] = ARight[j];
                    j++;
                    continue;
                }
            }
            if (i >= LeftSortLen && j < RightSortLen) {
                A[k] = ARight[j];
                j++;
                continue;
            }
            if (i < LeftSortLen && j >= RightSortLen) {
                A[k] = ALeft[i];
                i++;
                continue; 
            }
        }
        delete[] ALeft;
        delete[] ARight;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70]: /images/20220321/4064e60f50484407a3b9450ac1ba1ba4.png