`
sam_kee
  • 浏览: 19918 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

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

J# 
阅读更多
我的希尔排序代码 
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

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

分享到：
| 各种排序
评论
16 楼 raojl 2011-06-01  
典型得杀鸡有牛刀！
15 楼 ifan1314 2011-06-01  
没错，对数据的处理方式得看具体的环境和需求，各个算法都仅仅只是一种解决手段而已，我们要具体对待
14 楼 hyj1254 2011-05-31   
public void shellSort(Integer[] data, int group) {
		long start=System.currentTimeMillis();
		for (int inc = data.length / group; inc > 0; inc /= 2) {
			for (int i = inc; i < data.length; i++) {
				int temp = data[i];
				int j = i;
				for (; j >= inc && temp < data[j - inc]; j -= inc) {
					data[j] = data[j - inc];
				}
				data[j] = temp;
			}
		}
		long end=System.currentTimeMillis();
		System.out.println("shell:"+(end-start));
	}

Integer arr[]=new Integer[100000];
		for(int i=0;i<100000;i++){
			arr[i]=(int)(Math.random()*100000+1);
		}
		sSort.shellSort(arr,2);

怎么我的测了下shell明显快了很多，400毫秒左右，插入只支持到10000，否则慢得不行了。
13 楼 sam_kee 2011-05-23  
yizhilong28 写道
希尔排序的复杂度理论上还无法计算出来，但肯定比插入小。
衡量算法的是平均复杂度，lz不要用某个例子来否定一个算法。

嗯，明白
12 楼 yizhilong28 2011-05-23  
希尔排序的复杂度理论上还无法计算出来，但肯定比插入小。
衡量算法的是平均复杂度，lz不要用某个例子来否定一个算法。
11 楼 sam_kee 2011-05-21  
ujnlu 写道
其实希尔就是改进的插入排序。
速度根据数据初始的结构来的 还有距离因素，如果两个数据之间相差不大 希尔比插入好不了哪里去

对于数据量非常大的时候，希尔排序是要比插入排序高效。不过对于数据量很大的时候，一般都用快排了。
10 楼 sam_kee 2011-05-21  
zzy198772 写道
/**
*插入排序
**/

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;
}
}

谢谢，的确要考虑数字的随机性
9 楼 lffsonic 2011-05-20  
你看下希尔排序和插入排序的时间复杂度，然后看看，对于多大数据量值来判断效率的高低
8 楼 zzy198772 2011-05-20  
/**
*插入排序
**/

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;
}
}
7 楼 ujnlu 2011-05-20  
其实希尔就是改进的插入排序。
速度根据数据初始的结构来的 还有距离因素，如果两个数据之间相差不大 希尔比插入好不了哪里去
6 楼 realvalkyrie 2011-05-19  
纯数字？BitSet
5 楼 sam_kee 2011-05-19  
dennis_zane 写道
这才几个元素。

恩恩，谢谢，我尝试用了随机数，发现希尔排序确实比插入排序高效
4 楼 dennis_zane 2011-05-19  
你要测试，也要分场景啊，数据规模，数据是否无序，数据是否倒序或者正序，这些因素组合起来，再排除下JIT和GC的因素，才能得出一个有说服力的结论。
3 楼 sam_kee 2011-05-19  
sam_kee 写道
dennis_zane 写道
这才几个元素。

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

但是我现在把程序改为了
int[] data = new int [10000001];
for (int i = 10000000 ; i >=0 ; i--)
	data[i] = i ;

然后把排序循环次数去掉
依然发现插入排序比希尔排序快
插入排序所用时间:0
希尔排序所用时间:3
2 楼 sam_kee 2011-05-19  
dennis_zane 写道
这才几个元素。

恩恩，谢谢回答，也就是说如果数量比较大的时候希尔排序比插入排序还要快吗？而不是在于循环的次数的多少？
1 楼 dennis_zane 2011-05-19  
这才几个元素。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics