首页 > 编程语言 >【算法】排序算法之归并排序

【算法】排序算法之归并排序

时间:2023-02-26 23:33:39浏览次数:53  
标签:归并 int start1 len start 算法 排序

原文网址:https://zhuanlan.zhihu.com/p/124356219

前几回,在前面已经对冒泡排序直接插入排序希尔排序选择排序快速排序做了说明分析。这回,将对归并排序进行相关说明分析。


一、排序算法系列目录说明

  • 冒泡排序(Bubble Sort)
  • 插入排序(Insertion Sort)
  • 希尔排序(Shell Sort)
  • 选择排序(Selection Sort)
  • 快速排序(Quick Sort)
  • 归并排序(Merge Sort)
  • 堆排序(Heap Sort)
  • 计数排序(Counting Sort)
  • 桶排序(Bucket Sort)
  • 基数排序(Radix Sort)

二、归并排序(Merge Sort)

归并排序,是创建在归并操作上的一种有效的排序算法。算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。归并排序思路简单,速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。

1. 基本思想

归并排序是用分治思想,分治模式在每一层递归上有三个步骤:

  • 分解(Divide):将n个元素分成个含n/2个元素的子序列。
  • 解决(Conquer):用合并排序法对两个子序列递归的排序。
  • 合并(Combine):合并两个已排序的子序列已得到排序结果。

2. 实现逻辑

2.1 迭代法

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

2.2 递归法

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

3. 动图演示

动图封面   归并排序演示

具体的我们以一组无序数列{14,12,15,13,11,16}为例分解说明,如下图所示:

上图中首先把一个未排序的序列从中间分割成2部分,再把2部分分成4部分,依次分割下去,直到分割成一个一个的数据,再把这些数据两两归并到一起,使之有序,不停的归并,最后成为一个排好序的序列。

4. 复杂度分析

平均时间复杂度:O(nlogn)
最佳时间复杂度:O(n)
最差时间复杂度:O(nlogn)
空间复杂度:O(n)
排序方式:In-place
稳定性:稳定

不管元素在什么情况下都要做这些步骤,所以花销的时间是不变的,所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为:O( nlogn )

归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间:n + logn;所以空间复杂度为: O(n)。

归并排序算法中,归并最后到底都是相邻元素之间的比较交换,并不会发生相同元素的相对位置发生变化,故是稳定性算法。

5. 代码实现

5.1 C版本

迭代法:

// 归并排序(C-迭代版)
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int* a = arr;
    int* b = (int*) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

递归法:

// 归并排序(C-递归版)
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

5.2 C++版本

迭代法:

// 归并排序(C++-迭代版)
template<typename T>
void merge_sort(T arr[], int len) {
    T* a = arr;
    T* b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T* temp = a;
        a = b;
        b = temp;
    }

    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }

    delete[] b;
}

递归法:

// 归并排序(C++-递归版)
template<typename T>
void merge_sort_recursive(T arr[], T reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

// merge_sort
template<typename T>
void merge_sort(T arr[], const int len) {
    T reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

5.3 Java版本

迭代法:

// 归并排序(Java-迭代版)
public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    int block, start;

    // 原版代码的迭代次数少了一次,没有考虑到奇数列数组的情况
    for(block = 1; block < len*2; block *= 2) {
        for(start = 0; start <len; start += 2 * block) {
            int low = start;
            int mid = (start + block) < len ? (start + block) : len;
            int high = (start + 2 * block) < len ? (start + 2 * block) : len;
            //两个块的起始下标及结束下标
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            //开始对两个block进行归并排序
            while (start1 < end1 && start2 < end2) {
            result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            }
            while(start1 < end1) {
            result[low++] = arr[start1++];
            }
            while(start2 < end2) {
            result[low++] = arr[start2++];
            }
        }
    int[] temp = arr;
    arr = result;
    result = temp;
    }
    result = arr;       
}

递归法:

// 归并排序(Java-递归版)
static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, result, start1, end1);
    merge_sort_recursive(arr, result, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        result[k++] = arr[start1++];
    while (start2 <= end2)
        result[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = result[k];
}

public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    merge_sort_recursive(arr, result, 0, len - 1);
}

6. 优化改进

在规模较小时,合并排序可采用直接插入,避免递归调用; 在写法上,可以在生成辅助数组时,俩头小,中间大,这时不需要再在后边加俩个while循环进行判断,只需一次比完。 为了节省将元素复制到辅助数组作用的时间,可以在递归调用的每个层次交换原始数组与辅助数组的角色。


总结

归并排序和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。

下一篇预告:堆排序(Heap Sort)。欲知详情,且听下回分解。


PS: 更多资源,欢迎关注微信公众号:developer1024

标签:归并,int,start1,len,start,算法,排序
From: https://www.cnblogs.com/bruce1992/p/17158230.html

相关文章

  • 每日算法--2023.2.26
    1.面试题59-II队列的最大值classMaxQueue{//该题的重点在于以o(1)的时间复杂度找到队列中最大的元素,如果只单纯维护当前队列一个最大的值,当该值出队后第二大的值找......
  • python的排序问题
    python的排序方法有两个1nums.sort()#原数组上排序,没有返回值,nums变为有序2#或者3nums=sorted(nums)#原数组不变,会返回一个排好序的新数组 那么如何......
  • 数据结构与算法概述
     一、数据结构与算法简介从广义上讲,数据结构是指一组数据的存储结构。算法是操作数据的一组方法。从狭义上讲,数据结构与算法是指某些著名的数据结构和算法,比如数组、列......
  • 4.10-替换算法
    需要替换算法的原因程序运行一段时间后,Cache存储空间被占满,当再有新的数据要调入时,就需要通过某种机制决定替换的对象集中常见的替换算法先进先出-FIFO最不经常使用......
  • 03:成绩排序
     描述给出班里某门课程的成绩单,请你按成绩从高到低对成绩单排序输出,如果有相同分数则名字字典序小的在前。输入第一行为n(0<n<20),表示班里的学生数目;接下来的n行,......
  • 回调函数和如何使用qsort函数以及最后如何运用冒泡排序完成一个各类型数据都适用的排
    首先回调函数就是通过一个函数指针调用的函数。简言之就是如果你把函数的指针作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,我们就说这就是回调函数。回调......
  • java的排序问题
    普通排序对于基础数据类型的排序,基本只是调用一下方法如java的 1Arrays.sort(nums);那么如何自定义排序规则呢?自定义排序规则:假设现在有这么个问题,有n个学生, 每......
  • 常见聚类算法
    聚类算法KMeansKmeans算法,也被称为K-平均或K-均值,是一种得到最广泛使用的聚类算法,主要思想是:首先将各个聚类子集内的所有数据样本的均值作为该聚类的代表点,然后把每个数......
  • 衡量算法的性能-时空复杂度分析
    算法即存在输入输出,由有限步骤结束的程序.因此,显而易见,算法并不是指一个单一的标准答案,而是一切能够完成要求的程序都可以称之为算法.但是算法之间根据性能的不同存......
  • 数据结构(借鉴408)-排序
    数据结构排序分冶稳定性时间复杂度空间复杂度1.插入类排序直接插入排序折半插入排序希尔排序分组(间距d--),直接插入排序2.交换类排序起泡排序快速排序......