美文网首页
C++编写算法(三) ——排序问题进阶，归并排序

C++编写算法(三) ——排序问题进阶，归并排序

作者: 俊仔系滑翔机 | 来源:发表于2018-10-23 21:17 被阅读0次

    (一)文讲到了选择排序、插入排序和希尔排序等基本排序问题。但人们并不满足于这几类排序，提出了一些排序算法。

    一、归并排序

    归并排序的思路如下：

    1. 先将一个数组分为两个子数组，
    2. 再对这两个子数组分别进行排序（可用前文将到的基本排序方法）
    3. 再将这两个子数组进行归并。

    所以，个人理解的归并排序是指第2步的排序完成后，对这两个有序的子数组进行归并为一个数组的方法。

    1、原地归并的抽象方法

    原地归并的抽象方法是指重新建立一个与数组大小相符的内存空间，然后将两个子有序数组中的元素从小到大放入这个数组当中。

    #include <iostream>
#include <vector>
using namespace std;
vector<int> SORT(int arr[], int Size);
int main()
{
    int SIZE;
    cout << "输入数组大小: ";
    cin >> SIZE;
    int *arr = new int[SIZE];
    vector<int> Result(SIZE);
    for (int i = 0; i < SIZE; i++)
    {
        cin >> arr[i];
    }
    cout << "数组为：";
    for (int j = 0; j < SIZE; j++)
    {
        cout << arr[j] << " ";
    }
    cout << endl;
    Result = SORT(arr, SIZE);
    cout << "排序后数组为：";
    for (int j = 0; j < SIZE; j++)
    {
        cout << Result[j] << " ";
    }
    cout << endl;
    delete[] arr;
    system("pause");
    return 0;
}

vector<int> SORT(int arr[], int Size)
{
    vector<int> result(Size);
    int mid = Size / 2;
    int i = 0;
    int j = mid;
    vector<int> temp(Size);
    for (int k = 0; k < Size; k++)
    {
        if (i >= mid)
        {
            temp[k] = arr[j];
            j++;
        }
        else if (j >= Size)
        {
            temp[k] = arr[i];
            i++;
        }
        else if (arr[i] > arr[j])
        {
            temp[k] = arr[j];
            j++;
        }
        else
        {
            temp[k] = arr[i];
            i++;
        }

    }
    for (int i = 0; i < Size; i++)
    {
        result[i] = temp[i];
    }
    return result;
}

    2、自顶向下的归并排序

    当然， 如果将前面的原地归并的方法，加上递归的思想后，就可以用于各种数组的排序中了。递归的思想在归并排序中显得十分重要。

    基本的思路如下：

    1. 需要写出原地归并的抽象方法merge()，
    2. 再通过递归的思想，写出SORT()函数。
    #include <iostream>
#include <vector>
const int SIZE = 16;
using namespace std;
void SORT(int *arr, int begin, int end);
void merge(int arr[], int begin, int middle, int end);
int main()
{
    int *arr = new int[SIZE];
    for (int i = 0; i < SIZE; i++)
    {
        cin >> arr[i];
    }
    cout << "数组为：";
    for (int j = 0; j < SIZE; j++)
    {
        cout << arr[j] << " ";
    }
    cout << endl;
    SORT(arr, 0, SIZE-1);
//  merge(arr, 2, 2, 3);
    cout << "排序后数组为：";
    for (int j = 0; j < SIZE; j++)
    {
        cout << arr[j] << " ";
    }
    cout << endl;
    delete[] arr;
    system("pause");
    return 0;
}

void SORT(int *arr, int begin, int end)
{
    if (begin >= end)
        return;
    int middle = begin + (end - begin) / 2;
    SORT(arr, begin, middle);              // 递归的思想
    SORT(arr, middle+1, end);            // 递归的思想
    merge(arr, begin, middle, end);
}

void merge(int arr[], int begin, int middle, int end)  // 原地归并抽象方法
{
    int i = begin;
    int j = middle+1;
    vector<int> temp(SIZE);
    for (int m = begin; m <= end; m++)
        temp[m] = arr[m];
    for (int k = begin; k <= end; k++)
    {
        if (i > middle)
        {
            arr[k] = temp[j];
            j++;
        }
        else if (j > end)
        {
            arr[k] = temp[i];
            i++;
        }
        else if (temp[i] > temp[j])
        {
            arr[k] = temp[j];
            j++;
        }
        else
        {
            arr[k] = temp[i];
            i++;
        }
    }
}

    归并排序可用于处理数百万甚至更大规模的数组。
    分析：由上述所说，归并排序使用的是递归的思想进行排序。如果在小规模的数组中频繁使用归并排序，将会影响算法的性能。所以，我们可以在对小规模数组进行简单的基础排序，如插入排序，就可以降低算法的运行时间。插入排序对一些比较小型的数组，有较好的排序效果，这体现在排序时间上。

    据书上所说，使用插入排序处理小规模的子数组(比如长度小于15)一般可以将归并排序的运行时间缩短10%~15%

    如何来让子数组自动地在我们规定的长度上进行插入排序呢？其实一开始我也没有想明白这个问题。但后来书上一词提醒了我——“改进”。所以，我们需要在前面的递归归并排序的基础上，改进算法，缩短归并排序的时间。
    首先，我想到的第一个想法就是减少递归的次数。减少递归次数，就需要在一下代码段中修改，修改跳出递归函数的条件！

    void SORT(int *arr, int begin, int end)
{
    if (begin >= end)                  //需修改递归结束的条件，以尽早结束递归
        return;
    int middle = begin + (end - begin) / 2;
    SORT(arr, begin, middle);              
    SORT(arr, middle+1, end);            
    merge(arr, begin, middle, end);
}

    因此，可以将子数组的长度设定为4，之前的(begin>=end)条件可以改写为((end-begin) > 4-1)，再在条件判断体中加入插入排序算法，即可完成改进。

    #include <iostream>
#include <vector>
const int SIZE = 16;
const int SpiltSize = 4;   //子数组的长度
using namespace std;
void SORT(int *arr, int begin, int end);
void merge(int arr[], int begin, int middle, int end);
void InsertSort(int *arr, int begin, int end);
int main()
{
    int *arr = new int[SIZE];
    for (int i = 0; i < SIZE; i++)
    {
        cin >> arr[i];
    }
    cout << "数组为：";
    for (int j = 0; j < SIZE; j++)
    {
        cout << arr[j] << " ";
    }
    cout << endl;
    SORT(arr, 0, SIZE-1);
    cout << "排序后数组为：";
    for (int j = 0; j < SIZE; j++)
    {
        cout << arr[j] << " ";
    }
    cout << endl;
    delete[] arr;
    system("pause");
    return 0;
}

void SORT(int *arr, int begin, int end)
{
    if (end - begin > (SIZE / SpiltSize) - 1)
    {
        InsertSort(arr, begin, end);
        return;
    }
        
    int middle = begin + (end - begin) / 2;
    SORT(arr, begin, middle);
    SORT(arr, middle+1, end);
    merge(arr, begin, middle, end);
}

void merge(int arr[], int begin, int middle, int end)
{
    int i = begin;
    int j = middle+1;
    vector<int> temp(SIZE);
    for (int m = begin; m <= end; m++)
        temp[m] = arr[m];
    for (int k = begin; k <= end; k++)
    {
        if (i > middle)
        {
            arr[k] = temp[j];
            j++;
        }
        else if (j > end)
        {
            arr[k] = temp[i];
            i++;
        }
        else if (temp[i] > temp[j])
        {
            arr[k] = temp[j];
            j++;
        }
        else
        {
            arr[k] = temp[i];
            i++;
        }
    }
}

void InsertSort(int *arr, int begin, int end)
{
    int Length = (end - begin) + 1;
    int temp;
    for (int i = 0; i < Length; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (arr[j - 1] > arr[j])
            {
                temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
            else
            {
                continue;
            }
        }
    }
}

    3、自底向上的归并排序

    自底向上的归并排序思路与自顶向上相反，即先从大小为2的两个子数组进行二二归并，再从大小为4的两个子数组进行四四归并，以此类推。自底向上的代码量明显减少，而且无需用到自顶向上的递归，仅有一个循环嵌套即可完成排序。

    #include <iostream>
#include <vector>
const int SIZE = 20;
using namespace std;
void SORT(int *arr, int begin, int end);
void merge(int arr[], int begin, int middle, int end);
int min(int a, int b);
int main()
{
    int *arr = new int[SIZE];
    for (int i = 0; i < SIZE; i++)
    {
        cin >> arr[i];
    }
    cout << "数组为：";
    for (int j = 0; j < SIZE; j++)
    {
        cout << arr[j] << " ";
    }
    cout << endl;
//  InsertSort(arr,0,SIZE-1);
    SORT(arr, 0, SIZE-1);
//  merge(arr, 0, 0, 1);

    cout << "排序后数组为：";
    for (int j = 0; j < SIZE; j++)
    {
        cout << arr[j] << " ";
    }
    cout << endl;
    delete[] arr;
    system("pause");
    return 0;
}

void SORT(int *arr, int begin, int end)
{
    for (int Rate = 1; Rate < SIZE; Rate += Rate)
    {
        for (int lo = 0; lo < SIZE - Rate; lo += 2 * Rate)
        {
            merge(arr, lo, lo + Rate - 1, min(SIZE - 1, lo + 2 * Rate - 1));
        }
    }
}

void merge(int arr[], int begin, int middle, int end)
{
    int i = begin;
    int j = middle+1;
    vector<int> temp(SIZE);
    for (int m = begin; m <= end; m++)
        temp[m] = arr[m];
    for (int k = begin; k <= end; k++)
    {
        if (i > middle)
        {
            arr[k] = temp[j];
            j++;
        }
        else if (j > end)
        {
            arr[k] = temp[i];
            i++;
        }
        else if (temp[i] > temp[j])
        {
            arr[k] = temp[j];
            j++;
        }
        else
        {
            arr[k] = temp[i];
            i++;
        }
    }
}

void InsertSort(int *arr, int begin, int end)
{
    int Length = (end - begin) + 1;
    int temp;
    for (int i = 0; i < Length; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (arr[j - 1] > arr[j])
            {
                temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
            else
            {
                continue;
            }
        }
    }
}

int min(int a, int b)
{
    return a > b ? b : a;
}

    自底向上的归并排序比较适合用链表组织的数组。这种方法只需要重新组织链表链接就能将链表原地排序，并且它无需创建任何新的链表节点。

    这些算法还能在一些小问题上进行优化。例如，对已经排序的两个子数组进行归并时，可以判断第一个子数组的末位数A1[end]与第二个子数组的首位A2[0]的大小关系，若A1[end]小于A2[0]，则两子数组合成的数组已经为有序数组了，无需再进行归并排序，这样就可以进一步节省排序的时间。

    相关文章

      网友评论

          本文标题：C++编写算法(三) ——排序问题进阶，归并排序

          本文链接：https://www.haomeiwen.com/subject/lchdzftx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|C++编写算法(三) ——排序问题进阶，归并排序|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！