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

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

一、归并排序

归并排序的思路如下：

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

所以，个人理解的归并排序是指第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、自顶向下的归并排序

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

基本的思路如下：

需要写出原地归并的抽象方法merge()，
再通过递归的思想，写出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;
}

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

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

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,324评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,356评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,328评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,147评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,160评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,115评论 1赞 296
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,025评论 3赞 417
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,867评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,307评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,528评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,688评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,409评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,001评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,657评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,811评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,685评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,573评论 2赞 353