根据Marcin Ciura的最佳(最着名的)shell排序算法的增量序列,shellsort的最佳序列是1,4,10,23,57,132,301,701 ......,但是如何生成这样的序列？在Marcin Ciura的论文中,他说:
Knuth和Hibbard的序列都相对较差,因为它们是由简单的线性递归定义的.
但我发现的大多数算法书都倾向于使用Knuth的序列:k = 3k + 1,因为它很容易生成.你生成一个弹壳序列的方法是什么？
Shellsort是一个有趣的排序算法,我刚才遇到过.最令人惊讶的是,不同的间隙序列可以显着提高算法的速度.我做了一些阅读(不广泛),似乎Tokuda的序列被推荐用于实际应用.
另一个有趣的部分是比率2.20~2.25的顺序往往更有效.所以我做了一个小搜索,考虑了从2.20到2.50的比率序列,并尝试搜索哪个比率可以表现平均好.我遇到了这个比例:2.48在许多不同的试验中看起来平均表现良好.
然后,我想出了序列发生器:2.48 k-1(让它称之为248序列)并试图将它与Tokuda的序列进行比较.事实证明,它们的平均速度相等.248个序列倾向于使用稍多的比较数.
我知道我可能错了,这就是为什么我来这里寻求更有经验的程序员的更多意见.如果你没有得到问题,这是我的问题:
248 Sequence: ROUNDUP ( 2.48(k-1) ) eg: 1, 3, 7, 16, 38, 94, 233, 577, 1431, 3549, 8801, 21826, ... Tokuda's Sequence ROUNDUP ( (9k - 4k) / (5 * 4k - 1) ) eg: 1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, …
我正在做一个实验来比较Thomas Hibbard的shell排序(间隙大小= 2 ^ k-1)和Donald Shell的shell排序(n/2 ^ k)如何在同一个阵列上执行.当阵列的大小从10到1000时,Hibbard的性能优于shell.但是当大小达到10000或更高时,shell排序比Hibbard快.
根据大O符号,Hibbard是O(N ^ 1.5),Shell是O(N ^ 2),这使我认为Hibbard应该比Shell增加更大的改进.谁能告诉我为什么我的结果可能不如预期？
我理解O符号是最坏的情况复杂性,但似乎性能应该更符合符号.
这是我用JAVA编写的代码:(注意:unsortedArray是先前声明和初始化的)
{
int temp;
int[] sortedArray = unsortedArray.clone();
printArray();
int k = (int)(Math.log(sortedArray.length)/Math.log(2));
int gap = (int)(Math.pow(2,k)-1);
int count = 0;
long endTime;
long startTime = System.nanoTime();
while (gap > 0)
{
for (int g = 0; g < gap; g++)
{
for (int d = g + gap; d < sortedArray.length; d = d + gap)
{
for (int i = d; i - gap …首先,这是我的Shell排序代码(使用Java):
public char[] shellSort(char[] chars) {
int n = chars.length;
int increment = n / 2;
while(increment > 0) {
int last = increment;
while(last < n) {
int current = last - increment;
while(current >= 0) {
if(chars[current] > chars[current + increment]) {
//swap
char tmp = chars[current];
chars[current] = chars[current + increment];
chars[current + increment] = tmp;
current -= increment;
}
else { break; }
}
last++;
}
increment /= 2;
}
return chars;
}
这是Shell排序的正确实现(暂时忘记最有效的间隙序列 - 例如,1,3,7,21 …
我正在阅读关于在Sedgewick的"算法"中进行排序的章节.在此过程中,我编写了3种基本排序算法:选择,插入和shell排序.该书说,尽管所有三个都具有二次最坏情况复杂性,但shell排序应该比随机数据上的插入排序快得多.在本书中,他们获得了600倍的性能提升.
但是我的笔记本电脑上有以下乘法器(几乎不随数组大小的增加而改变):
困扰我的问题是 - 为什么shell排序几乎比插入排序慢两倍？!
我想,我的shellort实现有问题.但我几乎从书中复制了它:
class ShellSort extends Sort {
//precalculate sequence: 1, 4, 13, 40, 121, 364, 1093, ...
//(3^20 - 1)/2 is enough for any array I sort
private static final int[] SEQUENCE = new int[20];
static {
for(int i = 1; i <= SEQUENCE.length; i++)
SEQUENCE[i - 1] = (int)(Math.pow(3, i) - 1) / 2;
}
public void sort(int[] a) {
int length = a.length;
int seqLen = SEQUENCE.length;
int nth;
int j; …谁能给我一个shell排序的例子？我是这里的新人,他必须学习shell排序,但首先我必须找到一个Java shell排序示例.我在谷歌找到了一个例子,但这太难了.
有人可以提供一个使用 Knuth 序列的 Java 中 shellsort 的简单工作示例吗？我在互联网上查看了几个地方，但找不到适合我的解释。我在概念层面上理解 shellsort - 因为它是一种插入排序，它是在一个间隙上完成的，这个间隙随着时间的推移而缩小，直到达到 1 的间隙 - 这本质上是一种插入排序。然而，Knuth 序列是 (k * 3 - 1)/2 并且前几个间隙的列表通常表示为 [1, 4, 13, 40, 121.. 等等]。
我的问题是这将如何实施？起始间隙实际上是 1，还是这个序列在它大于被排序列表的大小之前生成的值？如果差距从 1 开始，如果我正确理解 shell 排序，目的就会失败。有人可以解释一下吗？我觉得我错过了一些对理解这件事至关重要的东西。
提前致谢。
我需要在C中实现Shell排序并使用优化版本(其中间隙首先设置为数组/ 2的大小,然后将此数字重复除以2.2).问题是答案并不总是完全排序,我不确定这是因为我的代码中的某些逻辑错误还是Shell排序的一些缺点.
这是我的代码:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define MAX 7
void shellSort(int *a, int size);
void insert(int *a, int next_pos, int gap);
void shellSort(int *a,int size)
{
int gap = floor(size/2);
int next_pos;
while (gap>0)
{
for(next_pos = gap; next_pos < size; next_pos++)
insert(a, next_pos, gap);
if(gap == 2)
gap = 1;
else
gap = (int)(gap/2.2);
}
}
void insert(int *a, int next_pos, int gap)
{
int value = a[next_pos];
while(next_pos >= gap && a[next_pos] < …我需要一个简单的方法在c#中使用ShellSort对数组进行排序,请帮助我