二进制合并排序自然合并排序 [英] Binary Merge sort & Natural Merge sort

问题描述

我知道作业问题在这里不是最受欢迎的，但是我完全不知所措.我正在做一项作业，需要我们进行多种排序算法.其中之一使我发疯.我在任何地方都找不到在线的示例，他在课堂上也没有完全讲解它.我们必须进行如下所示的合并排序:

I know that homework questions are not the most popular on here, but I am at a total loss. I am doing an assignment which requires us to make multiple sorting algorithms. One of them however, is driving me insane. I can find no examples of it online anywhere, and he did not go over it fully in class. We have to make a merge sort that looks like this:

void mergeSort(int * a, int s, bool n = false)

其中a是数组，s是所述数组的大小，n对于二进制合并排序为false，对于自然合并排序为true.问题是，我找不到自然合并排序和二进制合并排序.我只是找到mergesort.他们都要求更多的变量.

Where a is the array, s is the size of said array, and n is false for binary merge sort, and true for natural merge sort. The problem is, I cant find what natural merge sort and binary merge sort are. I just find mergesort. And all of them ask for far more variables.

我只是在问是否有人知道在哪里可以找到关于这两种不同类型的mergesort的很好的解释.

I am simply asking if anyone knows where I can find a good explanation of those two different types of mergesort.

推荐答案

我不是该主题的专家，但是Wikipedia页面似乎是一个不错的起点 http://en.wikipedia.org/wiki/Merge_sort

I'm no expert on the topic, but the wikipedia page seems to be a good starting point http://en.wikipedia.org/wiki/Merge_sort

它包含一个有关自然合并排序的部分，并带有一个示例.

It contains a section on natural merge sort with an example.

关于二进制合并排序:

名为二进制合并排序的变体使用二进制插入排序进行排序 每组32个元素，然后进行归并排序(使用归并排序).它 将小数据集上插入排序的速度与速度相结合 大数据集上的归并排序

A variant named binary merge sort uses a binary insertion sort to sort groups of 32 elements, followed by a final sort using merge sort. It combines the speed of insertion sort on small data sets with the speed of merge sort on large data sets

有关插入排序的信息，请参见: http://en.wikipedia.org/wiki/Insertion_sort

And insertion sort may be read about here: http://en.wikipedia.org/wiki/Insertion_sort

其中包含有关二进制插入排序的选择.

which contains a selection on binary insertion sorting.

关于变量. Wikipedia示例自底向上合并排序"(自然合并排序是其变体)具有以下签名:

About the variables. The wikipedia example of 'bottom up merge sort' (of which natural merge sort is a variant) has this signature:

void BottomUpSort(A[], B[], n)

其中A是要排序的数组，其长度为n. B是一个工作数组，如果正确读取算法，它的长度也应为n.无论如何，它可以在算法的开头创建，并在结尾删除.

where A is the array to be sorted, n its length. B is a work array, and if a read the algoritm right it needs be of length n too. Anyway, it can be created in the beginning of the algoritm and deleted in the end.

这篇关于二进制合并排序自然合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！