希尔排序和插入排序，哪个更快些

我的希尔排序代码

package sort;

import static print.Print.printhh;
import static print.Print.printsz;

public class ShellSort {

	public static void main(String[] args) {
		int[] data = {9,8,7,6,5,4,3,2,1,0};
		ShellSort shellSort = new ShellSort();
		long begin = System.currentTimeMillis();
		for (int i = 0 ; i < 100000000 ; i++){
			shellSort.sort(data);
		}
		long end = System.currentTimeMillis();
		printhh ("希尔排序所用时间:"+(end-begin)/1000);
		printsz (data);
	}
	
	public void sort(int[] data){
		for (int i = data.length/2 ; i > 0 ; i/=2)
			for (int j = 0 ; j < i ; j++)
				insertSort (data,j,i);
	}
	
	public void insertSort(int[] data , int start , int inc){
		for (int i = start + inc ; i < data.length ; i += inc)
			for (int j = i ; (j >= inc) && (data[j] < data[j-inc]) ; j -= inc)
				swap(data,j,j-inc);
	}
	
	public void swap(int[] data , int i , int j){
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}
	
}

我的插入排序代码

package sort;
import static print.Print.*;
public class InsertSort {

	public static void main(String[] args){
		int[] data = {9,8,7,6,5,4,3,2,1,0};
		InsertSort insertSort = new InsertSort();
		long begin = System.currentTimeMillis();
		for (int i = 0 ; i < 100000000 ; i++){
			insertSort.sort(data);
		}
		long end = System.currentTimeMillis();
		printhh ("插入排序所用时间:"+(end-begin)/1000);
		printsz (data);
	}
	
	public void sort(int[] data){
		for (int i = 1 ; i < data.length ; i++)
			for (int j = i ; (j>0) && (data[j]<data[j-1]) ; j--)
				swap(data,j,j-1);
	}
	
	public void swap(int[] data , int i , int j){
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

}

运行结果如下：
希尔排序所用时间:26
0 1 2 3 4 5 6 7 8 9
===============
插入排序所用时间:5
0 1 2 3 4 5 6 7 8 9

这结果真让我失望，因为希尔排序就是插入排序的改良版，怎么效率比插入排序还要低呢？是我的程序写错了吗？请指教

这才几个元素。

恩恩，谢谢回答，也就是说如果数量比较大的时候希尔排序比插入排序还要快吗？而不是在于循环的次数的多少？

但是我现在把程序改为了

int[] data = new int [10000001];
for (int i = 10000000 ; i >=0 ; i--)
	data[i] = i ;

然后把排序循环次数去掉
依然发现插入排序比希尔排序快
插入排序所用时间:0
希尔排序所用时间:3

你要测试，也要分场景啊，数据规模，数据是否无序，数据是否倒序或者正序，这些因素组合起来，再排除下JIT和GC的因素，才能得出一个有说服力的结论。

恩恩，谢谢，我尝试用了随机数，发现希尔排序确实比插入排序高效

纯数字？BitSet

其实希尔就是改进的插入排序。
速度根据数据初始的结构来的 还有距离因素，如果两个数据之间相差不大 希尔比插入好不了哪里去

/**
*插入排序
**/

package com.util;

public class InsertSort {

public static void main(String[] args) {
int[] data = new int[100000];
for (int i = 0; i < 100000; i++) {
int temp = (int) (Math.random() * 100000);
System.out.println("temp==" + temp);
data[i] = temp;
}
InsertSort insertSort = new InsertSort();
long begin = System.currentTimeMillis();
insertSort.sort(data);
long end = System.currentTimeMillis();
System.out.println("插入排序所用时间:" + (end - begin) / 1000);
}

public void sort(int[] data) {
for (int i = 1; i < data.length; i++) {
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
}

public void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}







/**
*希尔排序
**/
package com.util;

public class ShellSort {

public static void main(String[] args) {
int[] data = new int[100000];
for (int i = 0; i < 100000; i++) {
int temp = (int) (Math.random() * 100000);
//System.out.println("temp==" + temp);
data[i] = temp;
}
ShellSort shellSort = new ShellSort();
long begin = System.currentTimeMillis();
shellSort.sort(data);
long end = System.currentTimeMillis();
System.out.println("希尔排序所用时间:" + (end - begin) / 1000);

for(int i=0;i<data.length;i++){
System.out.println(data[i]);
}
}

public void sort(int[] data) {
for (int i = data.length / 2; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
insertSort(data, j, i);
}
}
}

public void insertSort(int[] data, int start, int inc) {
for (int i = start + inc; i < data.length; i += inc) {
for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) {
swap(data, j, j - inc);
}
}
}

public void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}

你看下希尔排序和插入排序的时间复杂度，然后看看，对于多大数据量值来判断效率的高低