插入排序比shell排序快得多
我正在读Sedgewick的“算法”中关于排序的章节。在此过程中，我编写了3种基本的排序算法:选择、插入和shell排序。书中说，尽管这三种情况都有二次最坏的情况复杂性，但shell排序应该比对随机数据的插入排序快得多。在这本书中，他们获得了600倍的性能提升。
但在我的笔记本电脑上，我得到了以下乘数(几乎不会随着阵列大小的增加而改变)：
- 选择: 5.5x
- 插入: 1x
- 外壳: 1.8x！
困扰我的问题是-为什么shell排序比插入排序慢两倍？！
我想，我的shellsort实现有问题。但我差点把它从书上抄下来：
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;
for(int seqi = seqLen - 1; seqi >= 0; seqi--) {
if(SEQUENCE[seqi] < length / 3) {
nth = SEQUENCE[seqi];
for(int n = 0; n < length; n+=nth) {
j = n;
while(j > 0 && a[j] < a[j - nth]) {
exch(a, j, j-nth);
j -= nth;
}
}
}
}
}
}对于那些想要在机器上运行测试的人，剩下的代码(用JVM热加倍数组大小测试对结果没有明显的影响，所以这个简单的测试对N> 200 000是足够好的)。
main:
int N = 500_000;
Random rand = new Random();
int[] a = new int[N];
for(int i = 0; i < N; i++)
a[i] = rand.nextInt();
//insertion sort
int[] aCopy = Arrays.copyOf(a, a.length);
long start = System.nanoTime();
new InsertionSort().sort(aCopy);
System.out.println("insert:\t" + (System.nanoTime() - start));
//shell sort
aCopy = Arrays.copyOf(a, a.length);
start = System.nanoTime();
new ShellSort().sort(aCopy);
System.out.println("shell:\t" + (System.nanoTime() - start));InsertionSort和排序类：
class InsertionSort extends Sort {
public void sort(int[] a) {
int length = a.length;
int j;
int x;
for(int i = 1; i < length; i++) {
j = i;
x = a[i];
while(j > 0 && x < a[j-1]) {
a[j] = a[--j];
}
a[j] = x;
}
}
}
abstract class Sort {
abstract public void sort(int[] a);
protected static final void exch(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}回答 4
Stack Overflow用户
发布于 2014-02-27 08:15:24
您的实现被破坏并输出排序数组，这是因为最后一步是1，而当步骤为1时，两个内部循环执行基本插入排序。当步骤大于1时，实现中的两个内部循环只执行步骤排序，所以实现所做的是在外部循环的所有迭代中对数组进行洗牌，然后插入-在外部循环的最后一次迭代中对其进行排序。当然，它将花费更长的时间，而只是插入-排序它一次。
重用您的序列，适当的shell排序实现应该如下所示：
public void sort( int[] a ) {
int length = a.length;
int stepIndex = 0;
while ( stepIndex < SEQUENCE.length - 1 && SEQUENCE[ stepIndex ] < length / 3 ) {
stepIndex++;
}
while ( stepIndex >= 0 ) {
int step = SEQUENCE[ stepIndex-- ];
for ( int i = step; i < length; i++ ) { // DIFF: i++ instead of i+=step
for ( int j = i; j >= step && a[ j ] < a[ j - step ]; j -= step ) {
exch( a, j, j - step );
}
}
}
}这种实现与您的实现之间有两个主要区别：
- 两个内循环的适当初始指标
- 中间周期的适当索引增量(代码中的+1而不是+步骤)
另外，检查http://algs4.cs.princeton.edu/21elementary/Shell.java.html是否有一个良好的实现和良好的步骤序列。
Stack Overflow用户
发布于 2014-02-27 07:24:09
通过快速的浏览，您可以看到shell排序看起来更慢，因为有更多的循环。蛮力，您可以将一个system.out.println放在最内部的循环中，以查看进行了多少次比较。
3圈贝壳类
- (int seqi = seqLen - 1；seqi >= 0；seqi-)
- for(int n= 0；n< length；n+=nth)
- 而(j>0 && aj < aj )
2圈插入
- for(int i= 1；i< length；i++)
- 而(j>0&x< aj-1)
Stack Overflow用户
发布于 2014-02-27 07:29:57
我相信理由应该是缓存。Shell排序有很多(有点)随机访问，因此更多的缓存丢失。我相信用较新的硬件，它的性能会更差。插入排序几乎总是适用于相同的内存区域，因此它的性能更好。
https://stackoverflow.com/questions/22061461
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号