数据结构&算法 合并排序
-
合并排序
合并排序是一种基于分治法的排序技术。最坏情况下的时间复杂度为Ο(nlogn),它是最受人遵从的算法之一。合并排序首先将数组分成相等的两半,然后以排序的方式将它们合并。 -
合并排序如何工作?
为了理解合并排序,我们采用未排序的数组,如下所示:我们知道合并排序首先将整个数组迭代地分成相等的一半,除非获得原子值。我们在这里看到一个由8个项目组成的数组分为两个大小为4的数组。这不会更改原件中项目出现的顺序。现在我们将这两个数组分为两半。我们进一步划分这些数组,并获得无法再划分的原子值。现在,我们将它们分解时的方式完全相同。请注意提供给这些列表的颜色代码。我们首先比较每个列表的元素,然后以排序的方式将它们组合到另一个列表中。我们看到14和33处于排序位置。我们比较27和10,在2个值的目标列表中,我们先放置10,然后是27。我们更改19和35的顺序,而将42和44顺序放置。在合并阶段的下一个迭代中,我们比较两个数据值的列表,然后将它们合并为找到的数据值的列表,将所有数据按排序顺序放置。最终合并后,列表应如下所示:现在,我们应该学习合并排序的一些编程方面的知识。 -
算法
合并排序会继续将列表分为相等的一半,直到无法再对其进行划分为止。根据定义,如果它只是列表中的一个元素,则会对其进行排序。然后,合并排序将合并较小的排序列表,并将新列表也保持排序。步骤 1 − 如果它只是列表中已经排序的一个元素,返回。 步骤 2 − 递归地将列表分成两半,直到不能再被分割为止。 步骤 3 − 将较小的列表按照排序顺序合并到新的列表中。
-
伪码
现在我们将看到合并排序函数的伪代码。正如我们的算法指出的两个主要功能-分和合并。合并排序与递归一起工作,我们将以相同的方式看到实现。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
-
实现
以下是C语言的实现
尝试一下#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]); }