合并排序是一种基于分而治之的排序技术,最坏情况下的时间复杂度为Ο(n log n),合并排序首先将数组分成相等的两半,然后以排序的方式将它们合并。
为了理解合并排序,我们采用未排序的数组,如下所示:
我们知道合并排序首先将整个数组迭代地分成相等的一半,除非获得原子值。我们在这里看到一个由8个元素组成的数组分为两个大小为4的数组。
这不会更改原件中元素出现的顺序。现在我们将这两个数组分为两半。
我们进一步划分这些数组,并获得无法再划分的原子值。
现在,我们将它们分解时的方式完全相同。请注意提供给这些列表的颜色代码。
我们首先比较每个列表的元素,然后以排序的方式将它们组合到另一个列表中。我们看到14和33处于排序位置。我们比较27和10,在2个值的目标列表中,我们先放置10,然后是27。我们更改19和35的顺序,而将42和44顺序放置。
在合并阶段的下一个迭代中,我们比较两个数据值的列表,然后将它们合并为找到的数据值的列表,将所有数据按排序顺序放置。
最终合并后,列表应如下所示:
现在,我们应该学习合并排序的一些编程方面的知识。
链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/merge-sort-algorithm.html
来源:LearnFk无涯教程网
现在我们将看到合并排序函数的伪代码,正如我们的算法指出的两个主要函数-分和合并。
合并排序与递归一起工作,我们将以相同的方式看到实现。
procedure mergesort( var a as array ) if ( n == 1 ) return a var l1 as array = a[0] ... a[n/2] var l2 as array = a[n/2+1] ... a[n] l1 = mergesort( l1 ) l2 = mergesort( l2 ) return merge( l1, l2 ) end procedure procedure merge( var a as array, var b as array ) var c as array while ( a and b have elements ) if ( a[0] > b[0] ) add b[0] to the end of c remove b[0] from b else add a[0] to the end of c remove a[0] from a end if end while while ( a has elements ) add a[0] to the end of c remove a[0] from a end while while ( b has elements ) add b[0] to the end of c remove b[0] from b end while return c end procedure
#include <stdio.h> #define max 10 int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 }; int b[10]; void merging(int low, int mid, int high) { int l1, l2, i; for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) { if(a[l1] <= a[l2]) b[i] = a[l1++]; else b[i] = a[l2++]; } while(l1 <= mid) b[i++] = a[l1++]; while(l2 <= high) b[i++] = a[l2++]; for(i = low; i <= high; i++) a[i] = b[i]; } void sort(int low, int high) { int mid; if(low < high) { mid = (low + high) / 2; sort(low, mid); sort(mid+1, high); merging(low, mid, high); } else { return; } } int main() { int i; printf("List before sorting\n"); for(i = 0; i <= max; i++) printf("%d ", a[i]); sort(0, max); printf("\nList after sorting\n"); for(i = 0; i <= max; i++) printf("%d ", a[i]); }
List before sorting 10 14 19 26 27 31 33 35 42 44 0 List after sorting 0 10 14 19 26 27 31 33 35 42 44
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)