`
sam_kee
  • 浏览: 19246 次
  • 性别: 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  
这才几个元素。
发表评论

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

相关推荐

    c常用排序法：冒泡＋选择＋插入＋快速＋希尔...

    插入排序：对一个队列里的数据，从第二个开始，与此位置之前的数据进行比较，形成局部有序的队列，循环此操作，直到队尾，运算时间复杂度依然为N平方，但他由于保证了局部的有序性，所以比较的次数会更少一些，相对...

    希尔排序算法的C语言实现示例

    希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即...

    数据结构课程设计(排序综合)

    要求： 1)至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并...更多&gt;&gt; 利用随机函数产生N个随机整数(20000以上),对这些数进行多种方法进行排序...

    数据结构—八种排序效率比较代码

    直接插入排序，折半插入排序，希尔排序，冒泡排序，一趟快速排序，快速排序，直接选择排序，堆排序相关代码及效率的比较

    JavaScript中几种常见排序算法小结

    这是一个非常快的排序方式，V8的sort方法就使用快速排序和插入排序的结合 希尔排序：在非chrome下数组长度小于1000，希尔排序比快速更快 系统方法：在forfox下系统的这个方法非常快 算法源码 代码如下: /

    详细总结C++的排序算法

    排序算法经过了很长时间的演变，产生了很多种不同的方法。对于初学者来说，对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合，很难通用...最坏时间复杂度：冒泡，选择，插入，快排是O(n2)，其他是O

    算法第四版-PDF-网盘链接

    　1.4.5　设计更快的算法　118 　1.4.6　倍率实验　121 　1.4.7　注意事项　123 　1.4.8　处理对于输入的依赖　124 　1.4.9　内存　126 　1.4.10　展望　129 　1.5　案例研究：union-find算法　136 　1.5.1　动态...

    leetcode凑硬币-Arithmatic:算术

    概要的讲解timsort的实现以及timsort的bugs，因为是视频，所以相比论文我觉得更快看得懂，没字幕，听不懂怎么办，没事，演讲者有一个文章重新梳理视频内容 2，Tim peters自己写的论文 二维“有序数组查找” —...

    算法-第4版-完整版

    1.4.5　设计更快的算法　118 1.4.6　倍率实验　121 1.4.7　注意事项　123 1.4.8　处理对于输入的依赖　124 1.4.9　内存　126 1.4.10　展望　129 1.5　案例研究：union-find算法　136 1.5.1　动态连通性　136 ...

    算法 第4版-谢路云译-带完整书签

    1.4.5 设计更快的算法 118 1.4.6 倍率实验 121 1.4.7 注意事项 123 1.4.8 处理对于输入的依赖 124 1.4.9 内存 126 1.4.10 展望 129 1.5 案例研究：union-find算法 136 1.5.1 动态连通性 136 1.5.2 ...

    《算法》中文版，Robert Sedgewick，塞奇威克

    1.4.5　设计更快的算法 1.4.6　倍率实验 1.4.7　注意事项 1.4.8　处理对于输入的依赖 1.4.9　内存 1.4.10　展望 1.5　案例研究：union-find算法 1.5.1　动态连通性 1.5.2　实现 1.5.3　展望 第2章　排序 2.1　初级...

    算法,4th,塞奇威克 (Robert Sedgewick)韦恩 (Kevin Wayne), 谢路云 译.azw3

    1.4.5 设计更快的算法 1.4.6 倍率实验 1.4.7 注意事项 1.4.8 处理对于输入的依赖 1.4.9 内存 1.4.10 展望 1.5 案例研究：union—find算法 1.5.1 动态连通性 1.5.2 实现 1.5.3 展望 第2章 排序 2.1 初级...

    算法 第4版 高清中文版

    1.4.5 设计更快的算法 118 1.4.6 倍率实验 121 1.4.7 注意事项 123 1.4.8 处理对于输入的依赖 124 1.4.9 内存 126 1.4.10 展望 129 1.5 案例研究:union-find算法 136 1.5.1 动态连通性 136 1.5.2 实现 140 ...

    数据结构与算法研究（强烈推荐）

    对以下四种算法详细地进行了分析：插入排序、希尔排序、堆排序以及快速排序。堆排序平均情形运行时间的分析对于这一版来说是新的内容。本章末尾讨论了外部排序。 第8章讨论不相交集算法并证明其运行时间。这是短且...

    数据结构（C++）有关练习题

    内容及步骤: 编写一个类Complex，定义复数的加法、减法、乘法和除法运算，要求在编写该类时重载这些运算操作符，并重载I/O操作符，以便输入和输出复数； 实验报告要求: 按要求写出完整的实验代码； ...

    java 面试题 总结

    ArrayList和Vector都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢，Vector...

    超级有影响力霸气的Java面试题大全文档

    　ArrayList 和Vector都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢，...

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