Shellsort and Sorting Networks
Shellsort and Sorting Networks
复制标题
希尔排序和排序网络
DOI：
--
复制
发表时间：
1972
期刊：
影响因子：
--
通讯作者：
V. Pratt
中科院分区：
文献类型：
--
作者：
V. Pratt
翻译后摘要：Shellsort是一种特殊的方法对数字计算机上的数据进行排序。与Shellsort的每个变体相关联的是表征该变体的整数序列。在本文中，作者回答了一些开放的问题，壳排序的速度与某些特征序列，并提出了一个新的应用壳排序，即排序网络。对于任何一个近似于几何级数的特征序列，并且具有短的互质连续性的壳排序都需要O（n sup 3/2）个时间单位。对于任何以整数公比逼近几何级数的数列，这个界是最好的可能界。然而，如果序列由小于n的正整数的降序序列组成，并且只有2和3作为素因子，那么Shellsort只需要O（n log squared n）个时间单位。基于Shellsort的排序网络与此序列的操作速度大约是以前方法的1.5倍。
Abstract : Shellsort is a particular method of sorting data on digital computers. Associated with each variant of Shellsort is a sequence of integers that characterizes that variant. In the paper the author answers some open questions about the speed of Shellsort with certain characteristic sequences, and suggests a novel application of Shellsort, namely to sorting networks. Shellsort with any characteristic sequence that approximates a geometric progression and that has short coprime subsequences through takes O(n sup 3/2) units of time. For any sequence that approximates a geometric progression with an integer common ratio, this bound is the best possible. However, if the sequence consists of the descending sequence of positive integers less than n and having only 2 and 3 as prime factors, then Shellsort takes only O(n log squared n) units of time. Sorting networks based on Shellsort with this sequence operate approximately 1.5 times as fast as with previous methods.