归并排序

  1. —归并排序—
    1. 算法描述
    2. 代码实现
    3. 算法分析
    4. 稳定性

—归并排序—

​ 作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  • 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
  • 自下而上的迭代;

MergeSort

算法描述

具体算法描述如下:

  • <1>.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

  • <2>.设定两个指针,最初位置分别为两个已经排序序列的起始位置;

  • <3>.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

  • <4>.重复步骤 3 直到某一指针达到序列尾;

  • <5>.将另一序列剩下的所有元素直接复制到合并序列尾。

mergeSort

代码实现

//合并
void Merge(int a[],int temp[], int left, int mid, int right)
{
    //左第一个数游标
    int l_pos = left;  
    //右第一个数游标
    int r_pos = mid + 1;
    //全局游标
    int cur = left;

    while (l_pos <= mid && r_pos <= right)   // 当左游标小于中间值 并且 右游标小于末位置
    {
        if (a[l_pos] > a[r_pos])         // 如果 左边第一个元素 大于 右边第一个元素
            temp[cur++] = a[r_pos++];    // 则 将右边的第一个元素放入临时列表里面
        else
            temp[cur++] = a[l_pos++];     // 否则将左边的第一个元素放入临时列表里面
    }
    while (l_pos <= mid)                 // 比较完后若左边有剩余 则将左边的数依次放入临时列表
        temp[cur++] = a[l_pos++];
    while (r_pos <= right)
        temp[cur++] = a[r_pos++];      // 比较完后若右边有剩余 则将右边的数依次放入临时列表
    
    while (left <= right)              // 把临时列表的值赋给原先的列表
    {
        a[left] = temp[left];
        left++;
    }

}

//递归接口
void MergeSort(int a[],int temp[],int left,int right)
{
    if (left < right)      // 递归的终止条件
    {
        int mid = (left + right) / 2;     

    //拆分
    //左半部分拆分
    MergeSort(a, temp, left, mid);
    //右半部分拆分
    MergeSort(a, temp, mid+1, right);

    //合并
    Merge(a, temp, left, mid, right);   

    }

}

void Merge_Sort(int a[],int n)
{
    int* temp = new int[n];
    MergeSort(a,temp, 0, n-1);
    delete[] temp;
}

算法分析

  • 平均情况:T(n) = O(n2)

  • 最佳情况:输入数组按升序排列。T(n) = O(n)

  • 最坏情况:输入数组按降序排列。T(n) = O(n2)

稳定性

  • 稳定

    采用的是比较左右两边的最小值依次放入临时数组,故顺序不变


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 351134995@qq.com

×

喜欢就点赞,疼爱就打赏