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

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

一、归并排序

归并排序的思路如下：

  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]，则两子数组合成的数组已经为有序数组了，无需再进行归并排序，这样就可以进一步节省排序的时间。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容