分治法的经典运用归并排序(Merge Sort)

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

简介

归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

 

一个归并排序的例子:对一个随机点的链表进行排序

一个归并排序的例子:对一个随机点的链表进行排序

 

一个归并排序的例子:对一个随机点的链表进行排序

一个归并排序的例子:对一个随机点的链表进行排序

分类 排序算法
数据结构 数组
最差时间复杂度 \Theta (n\log n)
最优时间复杂度 \Theta(n)
平均时间复杂度 \Theta (n\log n)
最差空间复杂度 \Theta(n)

归并操作

归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

迭代法

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

递归法

原理如下(假设序列共有n个元素):

  1. 将序列每相邻两个数字进行归并操作,形成floor(n/2)个序列,排序后每个序列包含两个元素
  2. 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
  3. 重复步骤2,直到所有元素排序完毕

案例(C++)

 

#include <iostream>
#include <cstdlib>

void merge(int source_arr[], int temp_arr[], int start_index, int mid_index, int end_index)
{
    int i = start_index, j = mid_index + 1, k = start_index;
    while (i != mid_index + 1 && j != end_index + 1)
    {
        if (source_arr[i] <= source_arr[j])
        {
            temp_arr[k++] = source_arr[i++];
        } else {
            temp_arr[k++] = source_arr[j++];
        }
    }
    while (i != mid_index + 1)
    {
        temp_arr[k++] = source_arr[i++];
    }
    while (j != end_index + 1)
    {
        temp_arr[k++] = source_arr[j++];
    }
    for (i = start_index; i <= end_index; i++)
    {
        source_arr[i] = temp_arr[i];
    }
}

void merge_sort(int source_arr[], int temp_arr[], int start_index, int end_index)
{
    int mid_index;
    if (start_index < end_index)
    {
       mid_index = (start_index + end_index) / 2;
       merge_sort(source_arr, temp_arr, start_index, mid_index);
       merge_sort(source_arr, temp_arr, mid_index + 1, end_index);
       merge(source_arr, temp_arr, start_index, mid_index, end_index);
    }
}

int main(int argc, char * argv[])
{
    int a[12] = {12, 3, 212, 42, 50, 10, 20, 30, 70, 40, 80, 60};
    int i, b[12];
    merge_sort(a, b, 0, 11);
    for(i=0; i<12; i++)
    {
        std::cout<<a[i]<<std::endl;
    }
    return 0;
}

这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: 技术, 算法 | 标签: , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。 必填项已用*标注